1. 简答题 括号匹配问题是计算机程序设计中常见的问题之一。假设表达式中有3种括号:圆括号、方括号、花括号。请编写一个程序来判断表达式中的括号是不是匹配。
时间: 2024-10-10 11:10:37 浏览: 33
考研备考资料真题-2019年贵州大学831计算机考研真题.pdf
括号匹配问题通常通过栈数据结构来解决。算法步骤如下:
1. 创建一个空栈。
2. 遍历输入表达式的每个字符:
a. 如果遇到左括号(如'('、'['或'{'),将其压入栈中。
b. 如果遇到右括号(如')'、']'或'}'):
- 如果栈为空,则返回false,因为没有对应的左括号。
- 否则,弹出栈顶元素并与当前右括号比较。如果类型不匹配(例如,')' 和 '{'),则返回false。
- 匹配成功则继续检查下一个字符。
3. 遍历结束后,如果栈为空,说明所有括号都已成对出现,返回true;否则返回false,表示有未匹配的左括号。
以下是用Python实现的一个简单版本:
```python
def is_bracket_matched(expression):
bracket_map = {")": "(", "]": "[", "}": "{"}
stack = []
for char in expression:
if char in bracket_map.values():
stack.append(char)
elif char in bracket_map.keys() and not stack or stack.pop() != bracket_map[char]:
return False
return len(stack) == 0
# 测试示例
print(is_bracket_matched("()[]{}")) # True
print(is_bracket_matched("({[})")) # False
```
阅读全文