设计一个判别表达式中括号是否配对的算法,采用什么数据结构最佳
时间: 2024-03-10 08:47:55 浏览: 195
可以使用栈这种数据结构来实现括号匹配的算法。具体的实现过程如下:
1. 遍历表达式中的每一个字符,如果是左括号(包括小括号、中括号和大括号)则将其入栈。
2. 如果是右括号,取出栈顶元素进行匹配,如果匹配成功则弹出栈顶元素,否则表达式中括号不配对。
3. 遍历完整个表达式后,如果栈为空,则表达式中括号配对,否则表达式中括号不配对。
在这个算法中,栈的作用是记录左括号,在遇到右括号时进行匹配。因此使用栈这种数据结构最为合适。
以下是一个使用栈实现括号匹配的 Python 代码示例:
```python
def is_valid_expression(exp):
stack = []
for c in exp:
if c in ['(', '[', '{']:
stack.append(c)
elif c in [')', ']', '}']:
if not stack:
return False
top = stack.pop()
if (c == ')' and top != '(') or \
(c == ']' and top != '[') or \
(c == '}' and top != '{'):
return False
return not stack
```
该算法的时间复杂度是 O(n),其中 n 表示表达式的长度。
阅读全文