在文字处理软件或编译程序设计时,常常需要检查一个字符串或一个表达式中的括号是否相匹配?算法代码
时间: 2024-02-21 18:58:39 浏览: 25
下面是使用堆栈实现括号匹配的算法代码(使用 Python 语言实现):
```python
def is_match(expr):
stack = [] # 创建一个空堆栈
left_parentheses = "([{"
right_parentheses = ")]}"
for ch in expr:
if ch in left_parentheses:
stack.append(ch) # 如果是左括号,将其压入堆栈中
elif ch in right_parentheses:
if not stack: # 如果堆栈为空,说明没有左括号和右括号匹配
return False
top = stack.pop() # 弹出堆栈顶部的元素
if left_parentheses.index(top) != right_parentheses.index(ch):
return False # 如果左右括号不匹配,返回 False
return not stack # 如果堆栈为空,说明所有左括号和右括号都匹配,返回 True;否则返回 False
```
该算法的时间复杂度是 O(n),其中 n 是字符串或表达式的长度。