原题
给定一个字符串所表示的括号序列，包含以下字符：'(', ')', '{', '}', '[' and ']'， 判定是否是有效的括号序列。
样例
括号必须依照 "()" 顺序表示， "()[]{}" 是有效的括号，但"([)]"则是无效的括号。
解题思路
- 经典的利用一个栈进行匹配校验。
- 如果current是左符号，入栈
- 如果current是右符号
- 此时栈空，返回False
- 栈顶出栈与current比较，不相等则返回False
- 最后检查栈是否为空，返回True
完整代码
class Solution(object):
def isValid(self, s):
"""
:type s: str
:rtype: bool
"""
stack = []
balanced = True
index = 0
while index < len(s) and balanced:
symbol = s[index]
if symbol in "([{":
stack.append(symbol)
else:
if len(stack) == 0:
balanced = False
else:
top = stack.pop()
if not self.matches(top,symbol):
balanced = False
index = index + 1
if balanced and len(stack) == 0:
return True
else:
return False
def matches(self, open, close):
opens = "([{"
closers = ")]}"
return opens.index(open) == closers.index(close)
