设计一个算法,利用栈的特性,判定一个表达式中的园括号是否匹配。
时间: 2024-05-05 11:20:15 浏览: 61
算法思路:
遍历表达式中的每一个字符,如果字符是左括号,则将其压入栈中;如果字符是右括号,则判断栈顶元素是否是与之匹配的左括号,如果是则将栈顶元素出栈,否则表达式不合法。
算法步骤:
1. 初始化一个空栈。
2. 遍历表达式中的每一个字符,如果字符是左括号,则将其压入栈中。
3. 如果字符是右括号,则判断栈顶元素是否是与之匹配的左括号,如果是则将栈顶元素出栈,否则表达式不合法。
4. 如果遍历完成后栈中还有元素,则表达式不合法。
5. 如果遍历完成后栈中没有元素,则表达式合法。
算法实现:
```python
def is_valid_expression(exp):
stack = []
for c in exp:
if c == '(':
stack.append(c)
elif c == ')':
if len(stack) == 0 or stack[-1] != '(':
return False
stack.pop()
return len(stack) == 0
```
测试样例:
```python
assert is_valid_expression('()') == True
assert is_valid_expression('(()())') == True
assert is_valid_expression('((()))') == True
assert is_valid_expression(')(') == False
assert is_valid_expression('(()') == False
```
阅读全文