Problems
We want to cut several steel rods using a laser.
For efficient work, the rods are stacked from bottom to top, and a laser is fired vertically from above to cut the rods.
The arrangement of rods and lasers must satisfy the following conditions:
A rod can only be placed on top of a rod that is longer than itself.
When placing a rod on top of another rod, it must be fully contained without overlapping the endpoints.
Each rod has at least one laser that cuts it.
Lasers do not overlap with any endpoint of a rod.
The figure below shows an example that satisfies the above conditions.
The thick horizontal lines represent rods.
The dots represent the laser positions, and the vertical dashed arrows show the laser firing direction.
This arrangement of rods and lasers can be represented sequentially from left to right using parentheses:
(a) A laser is represented by a pair of adjacent parentheses
(). All such()pairs must represent a laser.(b) The left end of a rod is represented by an opening parenthesis
(, and the right end by a closing parenthesis).
In the example, the rods are cut into pieces by the lasers. The top two rods are cut into 3 and 2 pieces, respectively, and in total, the rods are cut into 17 pieces.
Given a string representing the arrangement of rods and lasers using parentheses, write a program that calculates the total number of rod pieces after all the cuts.
Input
The input consists of a single line containing a string of parentheses representing the rods and lasers without spaces. The number of parentheses does not exceed 100,000.
Output
Print a single integer: the total number of rod pieces after all cuts.
Example #1
()(((()())(())()))(())
17
Example #2
(((()(()()))(())()))(()())
24
You must sign in to write code.