设计一个算法利用顺序栈检查用户输入的表达式中括号是否配对(假设表达式中 可能含有圆()号、中括号[]和大括号{} 输入格式: 输入一行包含括号的表达式如:[2 (33)],([]),{ewe [42]kk},[{}]等 输出格式: 输出“括号匹配”或“括号不匹配 输入样例: 在这里给出一组输入。例如。 [2 (33)]
时间: 2023-10-09 13:12:08 浏览: 341
以下是基于顺序栈实现括号匹配检查的算法:
1. 初始化一个空的顺序栈S。
2. 从左到右扫描表达式中的每个字符,遇到左括号时,将其压入栈S中。
3. 遇到右括号时,若栈S为空,则说明该右括号没有匹配的左括号,表达式中的括号不匹配,算法结束;否则,弹出栈顶元素,若弹出的左括号与该右括号不匹配,则表达式中的括号不匹配,算法结束。
4. 遍历完整个表达式后,若栈S为空,则说明表达式中的括号全部匹配,输出“括号匹配”;否则,说明表达式中存在未匹配的左括号,输出“括号不匹配”。
以下是该算法的 Python 代码实现:
```python
def bracket_matching(expression):
stack = []
for ch in expression:
if ch in '([{':
stack.append(ch)
elif ch in ')]}':
if not stack:
return '括号不匹配'
left = stack.pop()
if left == '(' and ch != ')' or \
left == '[' and ch != ']' or \
left == '{' and ch != '}':
return '括号不匹配'
if not stack:
return '括号匹配'
else:
return '括号不匹配'
expression = input().strip()
print(bracket_matching(expression))
```
示例输入:[2 (33)]
示例输出:括号匹配
阅读全文