Problem B
Balanced Tree Path
You are given a tree where each node is annotated with a character from ()[]{}. A path is a sequence of one or more nodes where no node is repeated and every pair of adjacent nodes is connected with an edge. A path is balanced if the characters at each node, when concatenated, form a balanced string. A string is balanced if it satisfies the following definition:
-
An empty string is balanced.
-
If
is a balanced string, then ( ), [ ], and { } are balanced strings. -
if
and are balanced strings, then ( concatenated with ) is a balanced string.
Compute the number of balanced paths over the entire tree.
Input
The first line of input contains a single integer
The next line contains a string of
Each of the next
Output
Output a single integer, which is the number of balanced paths over the entire tree.
Sample Input 1 | Sample Output 1 |
---|---|
4 ()() 1 2 2 3 3 4 |
4 |
Sample Input 2 | Sample Output 2 |
---|---|
4 [[]] 1 2 2 3 3 4 |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
6 ([]{}) 1 2 2 3 3 4 4 5 5 6 |
4 |