设表达式中允许包含3种括号:圆括号、方括号和大括号。即小括号、中括号和大括号。 编写一个算法来判断表达式中的括号是否正确配对,要求利用栈的结构实现。
时间: 2023-04-20 17:02:29 浏览: 235
可以使用栈来实现括号匹配的判断。具体步骤如下:
1. 定义一个栈,用来存储左括号。
2. 遍历表达式中的每个字符,如果是左括号,则将其入栈;如果是右括号,则弹出栈顶元素,判断是否与当前右括号匹配。如果不匹配,则表达式中的括号不正确配对;如果栈为空,则表达式中的括号不正确配对。
3. 遍历完表达式后,如果栈为空,则表达式中的括号正确配对;否则,表达式中的括号不正确配对。
具体实现可以参考以下代码:
```
def is_valid_expression(expression):
stack = []
for char in expression:
if char in ['(', '[', '{']:
stack.append(char)
elif char in [')', ']', '}']:
if not stack:
return False
top = stack.pop()
if (char == ')' and top != '(') or \
(char == ']' and top != '[') or \
(char == '}' and top != '{'):
return False
return not stack
```
其中,`stack` 用来存储左括号,遍历表达式中的每个字符,如果是左括号,则将其入栈;如果是右括号,则弹出栈顶元素,判断是否与当前右括号匹配。如果不匹配,则表达式中的括号不正确配对;如果栈为空,则表达式中的括号不正确配对。最后,如果栈为空,则表达式中的括号正确配对;否则,表达式中的括号不正确配对。
阅读全文