Valid Brackets Sequence

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. An input string is valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

For example, (), ()[] {} and {[]} are valid, while (] and ([)] are not valid.

The problem can be formally expressed as checking whether the string is a valid sequence of brackets. A valid expression satisfies the condition: \[ S = \begin{cases} \\ \epsilon, & \text{if } S \text{ is empty}\\ A \oplus B, & A, B \text{ are valid sequences}\\ (A), \{A\}, \[A\], & A \text{ is a valid sequence} \end{cases} \]

inputFormat

A single line containing a string consisting solely of the characters '(', ')', '{', '}', '[' and ']'. The string may be empty.

outputFormat

Print a single line: 'True' if the string is a valid bracket sequence, and 'False' otherwise.## sample

()

True