栈

借助栈结构，遍历字符串：

• 遇到左括号，则入栈
• 遇到右括号，跳出栈顶元素，与右括号进行比较，判断是否匹配。若匹配，则继续；若不匹配，则不合法。

此外，要特别注意两种情况： A.开始就遇到右括号，直接判断不合法；

B.结束时，栈内还存在左括号，也不合法；

# 
# @param s string字符串 
# @return bool布尔型
#
class Solution:
    def isValid(self , s: str) -> bool:
        stack = []
        for i in range(len(s)):
            # 遇到左括号加入
            if s[i] in ['(','[','{']:
                stack.append(s[i])
            # 遇到右括号
            else:
                # 如果开始为空，不合法
                if not stack:
                    return False
                # 如果开始不为空，与栈顶元素比较
                else:
                    if s[i] == ')':
                        # 若相同，则抵消，继续
                        if stack.pop() == '(':
                            continue
                        # 若不同，则不合法
                        else:
                            return False
                    elif s[i] == ']':
                        if stack.pop() == '[':
                            continue
                        else:
                            return False
                    elif s[i] == '}':
                        if stack.pop() == '{':
                            continue
                        else:
                            return False
        if not stack:
            return True
        else:
            return False