假设一个算术表达式中包含圆括号、方括号、花括号这三种类型的括号,编写一个算法判断表达式中的括号是否配对。
时间: 2024-05-08 22:15:36 浏览: 96
可以使用栈来解决这个问题。遍历表达式,当遇到左括号时将其压入栈中,当遇到右括号时将其与栈顶元素进行匹配,如果匹配成功则将栈顶元素弹出,继续遍历表达式,如果匹配失败或者栈为空,则表达式中的括号不配对。
具体实现步骤如下:
1. 创建一个空栈。
2. 遍历算术表达式中的每一个字符,如果是左括号则将其压入栈中。
3. 如果是右括号,则与栈顶元素进行匹配,如果匹配成功则将栈顶元素弹出,继续遍历表达式;如果匹配失败或者栈为空,则表达式中的括号不配对。
4. 遍历完表达式后,如果栈为空,则表达式中的括号全部配对;否则表达式中的括号不配对。
以下是一个Python实现:
```python
def is_balanced(expr):
stack = []
for char in expr:
if char in ['(', '[', '{']:
stack.append(char)
elif char in [')', ']', '}']:
if not stack:
return False
if char == ')' and stack[-1] == '(':
stack.pop()
elif char == ']' and stack[-1] == '[':
stack.pop()
elif char == '}' and stack[-1] == '{':
stack.pop()
else:
return False
return not stack
```
测试一下:
```python
>>> is_balanced("2 * (3 + 5) - [7 - {4 + 1}]")
True
>>> is_balanced("2 * (3 + 5 - [7 - {4 + 1}]")
False
>>> is_balanced("(2 * 3 + 5) - [7 - {4 + 1}]")
True
>>> is_balanced("(2 * 3 + 5) - [7 - {4 + 1})]")
False
```
阅读全文