下面是使用堆栈实现括号匹配的算法代码(使用 Python 语言实现):应用
时间: 2024-02-21 16:58:54 浏览: 82
这个算法可以用来检查一个字符串中的括号是否匹配。它可以在编译器和解释器中用于检查代码中的语法错误,也可以在其他应用程序中用于验证用户输入的表达式是否正确。
代码实现如下:
```
def is_balanced(s):
stack = []
for c in s:
if c in ('(', '[', '{'):
stack.append(c)
elif c in (')', ']', '}'):
if not stack:
return False
elif c == ')' and stack[-1] == '(':
stack.pop()
elif c == ']' and stack[-1] == '[':
stack.pop()
elif c == '}' and stack[-1] == '{':
stack.pop()
else:
return False
return not stack
```
该函数的输入参数是一个字符串 s,它返回一个布尔值,指示括号是否匹配。算法使用一个堆栈来跟踪左括号,并在遇到右括号时弹出相应的左括号。如果字符串中存在未匹配的左括号或右括号,则函数返回 False。如果在遍历完整个字符串后堆栈为空,则函数返回 True。
下面是一个示例:
```
>>> is_balanced('(a+b)*(c-d)') # True
True
>>> is_balanced('((()))') # True
True
>>> is_balanced('(()))') # False
False
>>> is_balanced('({[}])') # False
False
```
阅读全文