Valid Parentheses Checker

You are given a string s consisting solely of the characters '(', ')', '{', '}', '[' and ']'. Your task is to determine whether the input string is a valid parentheses expression.

A valid expression satisfies the following conditions:

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets must be closed in the correct order.

In mathematical terms, if we denote open brackets as O and their corresponding closing brackets as C, the string is valid if it can be fully reduced by repeatedly removing matching pairs. For example, the expression can be described by the condition $$ \text{Valid}(s) \iff s = \varepsilon \; \vee \; s = \text{concat}(\text{Valid}(s_1),\,\text{Valid}(s_2)) \; \vee \; s = O\,C $$ where \(\varepsilon\) denotes the empty string.

inputFormat

The input is provided via stdin and consists of a single line string s containing only the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Print True if the parentheses expression is valid; otherwise, print False. The output must be written to stdout.

()

True