def is_valid(string):
  stack = []  # The stack to keep track of brackets
  hashmap = {")": "(", "}": "{", "]": "["}

  for char in string:
      # If the character is an opening bracket
      if char not in hashmap:
          # Simply push it onto the stack
          stack.append(char)
      else:
          # Pop the element from the stack, if it is not empty
          if stack:
              popped_element = stack.pop()
          # Otherwise assign a dummy value of '*' to the popped_element variable
          else:
              popped_element = "*"

          # If the mapping for the opening bracket in our hashmap and the popped
          # element of the stack don't match, return False
          if hashmap[char] != popped_element:
              return False

  # If the stack is empty, we will return True otherwise False
  return not stack


# Driver code
def main():
    inputs = ["(){}[]", "{}[]{}[{}])", "(){[{()}]}", "))){{}}}]]", "{[()}"]

    for i in range(len(inputs)):
        print(i + 1, ". Input string = ", inputs[i], sep="")
        print("   Valid parentheses = ", is_valid(inputs[i]), sep="")
        print("-" * 100)


if __name__ == "__main__":
    main()