Correct bracket expression (CBE below) can be
defined in the following way:
1. () - CBE
2. If A is CBE, then (A) is also CBE
3. If both A and B are CBE, then AB is also CBE
For example, (()()) is CBE, while ())( is not.
One can see from the above, that each opening bracket
has a corresponding closing bracket. A pair from
the opening bracket and corresponding closing bracket
shallbe called block. You are given a correct
bracket expression. Your task is to find the number of
different block pairs, such that one block lies inside another.
Input
The first row of input file contains CBE. It's length
does not exceed one million of symbols.
Output
Output one number - the amount of block pairs in the
given CBE, such that one block lies inside another.
|
Input 1
|
Output 1
|
Input 2
|
Output 2
|
Input 3
|
Output 3
|
Input 4
|
Output 4
|
()()()
|
0
|
()(())
|
1
|
(()())
|
2
|
((()))
|
3
|
|
