设计一个算法,利用顺序栈判断用户输入的表达式中的括号是否配对(假设表达式中可能含有圆括号、方括号和花括号),并用相关数据进行测试。
时间: 2024-10-01 20:11:29 浏览: 49
设计一个算法判别一个算术表达式的圆括号是否正确配对
设计一个用于检查括号配对的算法,可以采用深度优先搜索(DFS)或广度优先搜索(BFS)。这里我们选择栈的数据结构,因为它非常适合处理这种逐层递归的问题。
**算法步骤:**
1. 定义一个空栈,用于存储左括号。
2. 遍历用户输入的每个字符:
- 如果遇到左括号(如'('、'['或'{'),将其压入栈中。
- 如果遇到右括号(如')'、']'或'}'),从栈顶弹出一个左括号进行匹配:
- 如果弹出的是当前类型的右括号,则继续遍历;如果不匹配,说明括号配对错误。
3. 遍历结束后,如果栈为空,说明所有括号都已配对;否则,存在未配对的左括号。
**伪代码示例:**
```python
def is_bracket_pair(expression):
stack = []
valid_pairs = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in valid_pairs.values():
stack.append(char)
elif char in valid_pairs.keys() and not stack or stack.pop() != valid_pairs[char]:
return False
return stack == [] # 检查剩余栈是否为空
# 测试例子
test_cases = ["()", "({[[]])", "({[()()]})"]
for expr in test_cases:
print(f"Expression {expr}: {'Matched' if is_bracket_pair(expr) else 'Mismatched'}")
```
阅读全文