3. 括号匹配实验:学习括号匹配的基本原理,基于栈实现对文本中的括号匹配,并编写测试用例进行验证。
时间: 2024-03-24 17:41:03 浏览: 212
利用栈实现括号匹配
括号匹配是指在一个字符串中,括号必须成对出现,左括号与右括号之间可能会有其他字符,但是左右括号的数量必须相等且匹配。例如,"((()))"、"()()"都是合法的括号匹配,而"((())"、")()("则不是。
基于栈的括号匹配算法的思路如下:
1. 遍历字符串中的每一个字符,如果是左括号('(', '[', '{'),则将其入栈;如果是右括号(')', ']', '}'),则需要判断栈顶元素是否与之匹配。
2. 如果栈顶元素与当前字符匹配,则将栈顶元素出栈,继续遍历下一个字符;否则括号匹配失败,返回false。
3. 如果字符串遍历结束后,栈为空,则括号匹配成功,返回true;否则括号匹配失败,返回false。
下面是使用 Python 实现基于栈的括号匹配算法的代码:
```python
def is_valid_parentheses(s: str) -> bool:
stack = []
mapping = {')': '(', ']': '[', '}': '{'}
for c in s:
if c in mapping:
if not stack or stack[-1] != mapping[c]:
return False
stack.pop()
else:
stack.append(c)
return not stack
```
其中,mapping字典用于记录每个右括号与其对应的左括号。
测试用例可以包括以下几个场景:
1. 空字符串,返回True。
2. 只包含左括号或者右括号的字符串,返回False。
3. 字符串中括号不匹配的情况,返回False。
4. 字符串中括号匹配的情况,返回True。
例如:
```python
assert is_valid_parentheses("") == True
assert is_valid_parentheses("(") == False
assert is_valid_parentheses(")") == False
assert is_valid_parentheses("()") == True
assert is_valid_parentheses("(()") == False
assert is_valid_parentheses("()[]{}") == True
assert is_valid_parentheses("([)]") == False
assert is_valid_parentheses("{[]}") == True
```
阅读全文