假设表达式中允许包含3种括号 圆括号方括号和大括号 编写一个算法,判断表达式中的括号是否正确配对
时间: 2024-05-05 21:20:10 浏览: 150
好的,我可以帮你解决这个问题。这个问题可以使用栈来解决,具体的算法如下:
1.遍历表达式中的每个字符。
2.如果当前字符是一个左括号,将其压入栈中。
3.如果当前字符是一个右括号,则从栈中弹出一个元素。
4.如果弹出的元素不是对应的左括号,则表达式中的括号不匹配,返回false。
5.如果遍历完表达式后,栈不为空,则表达式中的括号不匹配,返回false。
6.如果遍历完表达式后,栈为空,则表达式中的括号匹配,返回true。
下面是一个示例代码实现:
```python
def is_valid(expression):
stack = []
for char in expression:
if char in ['(', '{', '[']:
stack.append(char)
elif char in [')', '}', ']']:
if not stack:
return False
left = stack.pop()
if left == '(' and char != ')':
return False
elif left == '{' and char != '}':
return False
elif left == '[' and char != ']':
return False
return not stack
```
这个算法的时间复杂度为O(n),其中n是表达式中字符的个数。
阅读全文