"""
https://leetcode-cn.com/problems/valid-parentheses/
《有效的括号》

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:
输入: "()"
输出: true

示例 2:
输入: "()[]{}"
输出: true

示例 3:
输入: "(]"
输出: false

示例 4:
输入: "([)]"
输出: false

示例 5:
输入: "{[]}"
输出: true
"""


class Solution(object):
    def isValid(self, s):
        """
        栈
        :type s: str
        :rtype: bool
        """
        left = ['(','[','{']
        right = [')',']','}']
        stack = list()
        for c in s:
            if c in right:
                idx1 = right.index(c)
                if len(stack) == 0:
                    return False
                idx2 = stack.pop()
                if idx1 != idx2:
                    return False
            else:
                idx1 = left.index(c)
                stack.append(idx1)
        return len(stack) == 0

sol = Solution()
assert (sol.isValid("()") == True)
assert (sol.isValid("()[]{}") == True)
assert (sol.isValid("(]") == False)
assert (sol.isValid("([)]") == False)
assert (sol.isValid("{[]}") == True)
assert (sol.isValid("{") == False)
assert (sol.isValid("}") == False)
assert (sol.isValid("}{") == False)
