设计一个算法,判断一个可能含有小括号('('与')')、中括号('['与']')和大括号('{'与'}')的表达式中各类括号是否匹配。若匹配,则返回1;否则返回0。。
时间: 2023-08-07 07:07:31 浏览: 51
可以使用栈(stack)来解决这个问题。
遍历表达式的每一个字符,若遇到左括号,则将其入栈,若遇到右括号,则判断栈顶元素是否与之匹配,若匹配则将栈顶元素出栈,继续遍历;若不匹配,则返回0,表示括号不匹配。
最后,若栈为空,则表示所有括号都匹配,返回1,否则返回0。
以下是示例代码:
```python
def is_valid_expression(expression):
stack = []
for char in expression:
if char in {'(', '[', '{'}:
stack.append(char)
elif char in {')', ']', '}'}:
if not stack:
return 0
top = stack.pop()
if (char == ')' and top != '(') or \
(char == ']' and top != '[') or \
(char == '}' and top != '{'):
return 0
return not stack
```
测试一下:
```python
print(is_valid_expression('()')) # 1
print(is_valid_expression('()[]{}')) # 1
print(is_valid_expression('(]')) # 0
print(is_valid_expression('([)]')) # 0
print(is_valid_expression('{[]}')) # 1
```
输出:
```
1
1
0
0
1
```
阅读全文