Problem A
Balance
Languages
da
en
Decide if a given string of parentheses of two different types is balanced, meaning that the opening and corresponding closing parentheses are properly nested. For instance, “([])()[]” is balanced, but “((” and “)(” and “(]” are not.
To be precise, (i) the empty string is balanced; (ii) if $w$ is balanced then both $\texttt(w\texttt)$ and $\texttt[w\texttt]$ are balanced; and (iii) if $w$ and $x$ are balanced then $wx$ is balanced.
Input
The input consists of a single line containing a nonempty sequence $w$ of symbols from the alphabet $\{ \texttt[, \texttt], \texttt(, \texttt)\} $.
Output
Print “1” if $w$ is balanced, “0” if not.
Test groups
Let $|w|$ denote the length of $w$. In all test groups, we have $1\leq |w|\leq 200\, 000$.
|
Group |
Points |
Additional constraints |
|
1 |
9 |
There are no “[” or “]” |
|
2 |
10 |
$|w|\leq 100$ |
|
3 |
81 |
None |
| Sample Input 1 | Sample Output 1 |
|---|---|
([(())])[] |
1 |
| Sample Input 2 | Sample Output 2 |
|---|---|
)( |
0 |
| Sample Input 3 | Sample Output 3 |
|---|---|
[) |
0 |
| Sample Input 4 | Sample Output 4 |
|---|---|
(( |
0 |
| Sample Input 5 | Sample Output 5 |
|---|---|
[(]) |
0 |
| Sample Input 6 | Sample Output 6 |
|---|---|
[])[]) |
0 |
| Sample Input 7 | Sample Output 7 |
|---|---|
( |
0 |
