数据结构--栈的应用--符号匹配算法
针对符号匹配算法问题，可以采用数据结构中的“栈“来实现。匹配符号是指正确的匹配和嵌套左右对应的符号。废话不多说，先来看代码：
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self,item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def matches(open,close):
opens = "({["
closes = ")}]"
return opens.index(open) == closes.index(close)
def StrPiPei(str):
s = Stack()
banlaced = True
index = 0
while index < len(str) and banlaced:
symbol = str[index]
if symbol in "({[":
s.push(symbol)
else:
if s.isEmpty():
banlaced = False
else:
top = s.pop()
if not matches(top,symbol):
banlaced = False
index = index + 1
if banlaced and s.isEmpty():
return True
else:
return False
print(StrPiPei("[][][]{}()"))
print(StrPiPei("{}{)[}"))
首先我们要定义一个栈，根据栈的特性，列出Stack（），再往下是一个匹配符号的函数，针对"（{[ "中的符号是否匹配，函数返回True或者False，检测每一个从栈顶移除的符号是否与当前右符号匹配，如果
匹配，布尔型变量banlaced就被设为False。
