# coding: utf-8
# 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
#
# 有效字符串需满足：
#
# 左括号必须用相同类型的右括号闭合。
# 左括号必须以正确的顺序闭合。
# 注意空字符串可被认为是有效字符串。
#
# 示例 1:
#
# 输入: "()"
# 输出: true
# 示例 2:
#
# 输入: "()[]{}"
# 输出: true
# 示例 3:
#
# 输入: "(]"
# 输出: false
# 示例 4:
#
# 输入: "([)]"
# 输出: false
# 示例 5:
#
# 输入: "{[]}"
# 输出: true

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        list = []

        dict = {
            "(": ")",
            "[": "]",
            "{": "}"
        }

        for item in s:
            if item in ["{","[","("]:
                list.append(item)
            elif item in ["}","]",")"]:
                if list:
                    if item == dict[list[len(list)-1]]:
                        list.pop()
                    else:
                        return False
                else:
                    return False

            elif item != " ":
                return False

        if not list:
            return True

s = "]"
print Solution().isValid(s)