Peter is preparing slides for his lecture on parsing arithmetic expressions. In
the first part of the lecture he wants to focus just on parsing brackets. He
invented an interesting geometric representation of a correct bracket sequence
for his students, because one image is better than a thousand words:
Formally, the definition of the geometric representation looks as follows. The
simplest correct bracket sequence () is represented by a 1 ¡Á1 square. If A is a
correct bracket sequence and g(A) its represenation, then the representation for
(A) is g(A) surrounded by a rectangle two units wider than g(A) and one unit
taller than the highest point of g(A). If A and B are two correct bracket
sequences and g(A) and g(B) are their representations, then we get g(AB) by
placing g(B) one unit to the right of g(A).
After he finished his slides, Peter started to play with the images he prepared.
He painted the bounded areas of the images alternately black and white, in such
a way that the outermost areas are all painted black. For the example above
this coloring looks as follows:
You are given a correct bracket sequence. Calculate the area that is colored
black.
