解析括號
堆疊通常用於解析。一個簡單的解析任務是檢查一串括號是否匹配。
例如,字串 ([])
是匹配的,因為外部和內部括號形成對。()<>)
不匹配,因為最後一個 )
沒有夥伴。([)]
也不匹配,因為對必須完全位於其他對內或外。
def checkParenth(str):
stack = Stack()
pushChars, popChars = "<({[", ">)}]"
for c in str:
if c in pushChars:
stack.push(c)
elif c in popChars:
if stack.isEmpty():
return False
else:
stackTop = stack.pop()
# Checks to see whether the opening bracket matches the closing one
balancingBracket = pushChars[popChars.index(c)]
if stackTop != balancingBracket:
return False
else:
return False
return not stack.isEmpty()