20. Valid Parentheses

class Solution:             #这道题用的是Stack这个数据结构的特点
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        if not s:
            return True

        st = []

        for i in range(0, len(s)):
            if s[i] == "(" or s[i] is "{" or s[i] is "[": #如果是左括号就推到stack里面
                st.append(s[i])
            else:
                # 如果是右括号，就把stack尾部的值pop出来进行比较。如果是匹配的就continue （continue就是当前的loop不跑了，进行下一个loop）
                if not st:
                    return False

                temp = st.pop()
                if s[i] is ")" and temp is "(":
                    continue

                elif s[i] is "}" and temp is "{":
                    continue

                elif s[i] is "]" and temp is "[":
                    continue
                # 如果不匹配直接返回FALSE
                else:
                    return False
        # 当所有s里面的都跑完了，还要检查一下stack还有没有剩余的“左括号”，如果有剩余就说明没有足够的“右括号”来匹配。返回False
        return True if not st else False