We will use a stack to calculate the result in linear time. The stack is initially empty. Process the bracket sequence from left to right. Each time we encounter an opening bracket ’(’, we push a value on top of the stack. When we encounter a closing bracket ’(’, we pop a value from the stack. We will discuss later what kind of values will be stored in the stack.
Let us assume that we have already processed some part of the sequence. How does the stack look like? Each value in the stack corresponds to an opening bracket that is not yet closed, i.e. the corresponding closing bracket was not yet processed. Since we process the sequence from left to right, the values in the stack are ordered according to the position of their corresponding opening bracket and the lowermost value corresponds to the leftmost opening bracket.
We will call a matching pair of brackets P parent of a matching pair Q, if P was right below Q in the stack. Smilarly, we will call Q son of P, if P is parent of Q. Denote by r(P) the rectangle that corresponds to the matching pair P in the geometric representation and denote by |r(P)| its area.
Suppose that the area between r(P) and all rectangles inside r(P) was coloured black. What is the size of this area? All rectangles inside r(P) correspond to the sons of P, because they had to be just above P in the stack. Therefore to calculate the size of the area that was coloured black we need to substract from |r(P)| the areas of all rectangles corresponding to the sons of P.
How to calculate the value |r(P)|? We need to know the height and the width of the rectangle r(P). The width is just the distance of the opening and closing bracket of the matching pair P. The height is the maximum of the heights of the rectangles corresponding to the sons of P increased by one. To calculate this, the first two values stored in the stack for pair P will be l and h, were l is the position of the opening bracket and h is the maximum of the heights of the rectangles corresponding to already processed sons of P. We will update the value h each time we pop a son of P. When we encounter the closing bracket of pair P, we can directly use the value h as the height and k - l as the width of r(P), where k is the position of the closing bracket. The third value stored in the stack for P will be the sum of the areas of rectangles corresponding to already processed sons of P. When we push P into the stack, we set this value to zero and we update it each time we pop a son of P from the stack.
Each bracket is processed in constant time, therefore the time complexity is linear. Also the memory complexity is linear, since we use just one stack.