You are given a string s consisting of characters: ( , ) , [ , ] , { and } . Write a program to check whether the characters in the string s are valid or not.

Problem Note:

  • A string if said to be valid if an open parenthesis is closed by the same type of parenthesis.
  • Also, the open parenthesis must be closed in the correct order.
  • Return 1 , if the string is valid, else return 0.

Example 1

Input: "(([](){}))"
Output: 1
Explanation: In the above example, every parenthesis and bracket has opening and closing in the correct order. Thus, we get 1(true) as output.

Example 2

Input: "([)]"
Output: 0
Explanation: In the above example, the brackets are closed but not in the correct order. Thus, we get 0(false) as output.

Example 3

Input: "()[]({})"
Output: 1
Explanation: In the above example, every parenthesis and bracket has opening and closing in the correct order. Thus, we get 1(true) as output.