编写一个算法判断输入的表达式中括号是否配对(假设只含有左右圆括号)
时间: 2024-11-09 09:28:23 浏览: 21
编写一个算法来判断输入的表达式中括号是否配对,可以采用栈数据结构来解决这个问题。这个过程通常被称为括号匹配或平衡检查。以下是步骤:
1. 初始化一个空栈 `stack`。
2. 遍历输入表达式的每个字符:
a. 如果当前字符是左括号(如 '(', '[', '{'),将其压入栈 `stack`。
b. 如果当前字符是右括号:
- 检查栈顶元素是否与其对应:
- 对于圆括号,`('`, ')` 对应;`['`, ']` 对应;`{'`, '}' 对应。
- 若匹配,则将栈顶的左括号弹出;
- 若不匹配,说明括号不配对,返回 `false`。
3. 遍历结束后,如果栈为空,表示所有括号都已配对,返回 `true`。
4. 否则,表示还有未匹配的左括号,返回 `false`。
下面是一个伪代码示例:
```python
def is_balanced(expression):
stack = []
open_brackets = {')': '(', ']': '[', '}': '{'}
for char in expression:
if char in open_brackets:
stack.append(char)
elif stack and stack[-1] == open_brackets[char]:
stack.pop()
else:
return False
return stack == [] # 判断栈是否为空
expression = "(([]))"
if is_balanced(expression):
print("括号配对")
else:
print("括号不配对")
```
阅读全文