假设表达式中允许包含3种括号:圆括号、方括号和大括号。即小括号、中括号和大括号。 编写一个算法来判断表达式中的括号是否正确配对,要求利用栈的结构实现。 输入格式: 输入一行带上述括号字符串 输出格式: 若匹配,输出yes。若不匹配,输出no。
时间: 2024-11-09 09:22:24 浏览: 49
为了检查一个由圆括号 (, ), 方括号 [, ], 和大括号 {, } 组成的表达式的括号是否正确配对,你可以使用栈数据结构。这里是一个简单的算法步骤:
1. 初始化一个空栈。
2. 遍历输入的括号字符串,对于每个字符:
a. 如果它是一个左括号 (, [, 或 {,将其压入栈中。
b. 如果它是一个右括号 ),[, 或 }:
- 检查栈顶元素是否是相应的左括号(例如,如果当前是 ),则检查栈顶是 (;如果是 ],则检查是 [;如果是 },则是 {)。
- 如果是,则弹出栈顶元素;如果不是,说明括号配对错误,返回 "no"。
c. 如果遍历完整个字符串且栈为空,表示所有左括号都有正确的对应右括号,返回 "yes";否则,栈不为空,意味着还有未关闭的左括号,返回 "no"。
以下是Python代码示例:
```python
def is_bracket_pair(expression):
brackets = {'(': ')', '[': ']', '{': '}'}
stack = []
for char in expression:
if char in brackets.values():
# 来到一个闭合括号,检查是否匹配
if not stack or stack.pop() != brackets[char]:
return "no"
else:
# 来到一个开放括号,直接压入栈
stack.append(char)
# 如果所有的括号都已处理,且栈为空,表示正确配对
return "yes" if not stack else "no"
# 示例用法
expression = input("请输入括号表达式: ")
result = is_bracket_pair(expression)
print(result)
```
阅读全文