数据结构括号匹配的检验
时间: 2023-05-26 22:05:50 浏览: 50
数据结构中的括号匹配检验是一种常见的问题,它可以通过栈这种数据结构来实现。栈是一种后进先出的数据结构,可以用来存储待匹配的左括号,并在遇到右括号时进行匹配。
具体实现过程如下:
1. 遍历给定字符串中的每个字符,如果遇到左括号就将其入栈,如果遇到右括号就先判断栈是否为空,如果为空则表示前面没有对应的左括号,匹配失败;如果栈不为空,则将栈顶元素弹出,如果弹出的元素和当前的右括号不匹配,则匹配失败。
2. 如果遍历完字符串后栈中仍有元素,也表示匹配失败,因为还有未匹配的左括号。
3. 如果字符串中的所有括号都匹配成功,则匹配成功。
代码实现如下(使用Python语言):
```python
def is_matched(str):
stack = []
left_brackets = ['(', '{', '[']
right_brackets = [')', '}', ']']
for c in str:
if c in left_brackets:
stack.append(c)
elif c in right_brackets:
if len(stack) == 0:
return False
top = stack.pop()
if left_brackets.index(top) != right_brackets.index(c):
return False
return len(stack) == 0
```
我们可以对以下四种情况进行测试:
1. 输入字符串中包含有不匹配的括号。例如:'((])'
2. 输入字符串中只包含左括号。例如:'[['
3. 输入字符串中只包含右括号。例如:'}]}'
4. 输入字符串中包含有匹配的括号。例如:'(([{()}]))'
测试结果:
1. 返回False
2. 返回False
3. 返回False
4. 返回True