有效的括号

题目

给定一个只包含'('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

思路

对于左括号，暂时不能判断，需要存起来；
对于右括号，判断离其最近的括号是不是相应的左括号。
典型的后入先出，需要借助栈来实现。

遍历所有字符ch，左括号入栈，如果是右括号则弹出栈顶元素判断是否是对应的左括号。
结束时所有元素出栈，栈应该为空，则说明是有效的括号。

class Solution:
    def isValid(self, s: str) -> bool:
        matches = {'}':'{', ']':'[', ')':'('}
        stack = []
        for ch in s:
            if ch not in matches:
                stack.append(ch)
            else:
                if stack and stack.pop() == matches[ch]:
                    continue
                else:
                    return False
        return not stack