Problem D
Bracket Matching
Given a bracket sequence $s$ of length $n$, you are to determine if it is valid!
A valid bracket sequence is defined recursively as:
-
“”
-
$(x)$ where $x$ is a valid bracket sequence
-
$[x]$ where $x$ is a valid bracket sequence
-
$\{ x\} $ where $x$ is a valid bracket sequence
-
$xy$, where $x$ and $y$ are valid bracket sequences
Input
The first line of each contains one integer $n$ $(2\leq n\leq 100\, 000)$ — the length of the bracket sequence.
The second line of each test case contains a string $s$ — the bracket sequence in the question. It is guaranteed that $s$ only contains $()[]\{ \} $ as characters.
Output
Output Valid if the sequence is a valid bracket sequence, otherwise output Invalid.
| Sample Input 1 | Sample Output 1 |
|---|---|
6
([]{})
|
Valid |
| Sample Input 2 | Sample Output 2 |
|---|---|
8 (())((() |
Invalid |
| Sample Input 3 | Sample Output 3 |
|---|---|
6
([}{])
|
Invalid |
