假设表达式中允许包含3种括号:圆括号、方括号和大括号。即小括号、中括号和大括号。 编写一个算法来判断表达式中的括号是否正确配对,要求利用栈的结构实现。
时间: 2024-11-22 07:46:31 浏览: 42
为了判断一个包含三种括号的表达式中括号是否正确配对,我们可以采用栈数据结构来辅助我们。栈是一种后进先出(LIFO)的数据结构,非常适合处理括号匹配问题,因为当我们遇到左括号时就将其压入栈中,当遇到右括号时检查栈顶元素是否与其匹配,如果匹配则弹出栈顶元素,如果不匹配则表示括号配对错误。
以下是步骤描述:
1. 遍历输入的表达式的每个字符。
2. 对于每个字符:
- 如果是左括号(圆括号、方括号或大括号),将它压入栈中。
- 如果是右括号:
- 检查栈顶元素是否对应当前的右括号类型。例如,如果是'(' 和 ')' 的匹配,或者 '[' 和 ']' 的匹配,或者是 '{' 和 '}' 的匹配。
- 如果匹配,则将栈顶的左括号弹出;如果不匹配,返回 false 表示括号配对错误。
3. 遍历结束后,如果栈为空,说明所有左括号都已找到对应的右括号,括号配对正确;否则,存在未匹配的左括号,返回 false。
```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(): # 遇到右括号,检查是否匹配
if not stack or stack.pop() != bracket_map[char]: # 匹配则继续,不匹配则返回False
return False
return not stack # 没有剩余的左括号,说明括号配对正确
# 测试
expression = "[([]{})"
print(is_bracket_matched(expression)) # 输出:True
```
阅读全文