python 数据结构括号匹配
时间: 2023-11-09 16:00:40 浏览: 77
Python数据结构中,括号匹配可以使用栈来实现。具体实现过程如下:
1. 遍历括号串,如果是左括号就压入栈中,如果是右括号就弹出栈顶元素,并判断是否匹配。
2. 如果匹配就继续遍历,如果不匹配就返回False,表示匹配失败。
3. 如果遍历完整个括号串,栈为空,表示匹配成功,返回True。
参考代码如下:
from pythonds.basic.stack import Stack
def matches(left, right):
"""
判断左右括号是否匹配
"""
if left == '(' and right == ')':
return True
elif left == '[' and right == ']':
return True
elif left == '{' and right == '}':
return True
else:
return False
def parChecker(symbolString):
"""
判断括号串是否匹配
"""
s = Stack()
balanced = True
index = 0
while index < len(symbolString) and balanced:
symbol = symbolString[index]
if symbol in '([{':
s.push(symbol)
else:
if s.isEmpty():
balanced = False
else:
top = s.pop()
if not matches(top, symbol):
balanced = False
index = index + 1
if balanced and s.isEmpty():
return True
else:
return False
print(parChecker('{{([])}}')) # True
print(parChecker('([)]')) # False
#
阅读全文