class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []
        for char in s:
            if char in {'(', '[', '{'}:
                stack.append(char)
            elif len(stack) == 0:
                return False
            elif char == ')':
                if stack[-1] == '(':
                    stack = stack[:-1]
                else:
                    return False
            elif char == ']':
                if stack[-1] == '[':
                    stack = stack[:-1]
                else:
                    return False
            elif char == '}':
                if stack[-1] == '{':
                    stack = stack[:-1]
                else:
                    return False

        if len(stack) == 0:
            return True
        else:
            return False