Iron Stick

Problem

I am trying to cut several iron rods with a laser. For efficient operation, the iron rods are stacked from the bottom up, and the laser is fired vertically from above to cut the iron rods. The arrangement of the iron rod and laser satisfies the following conditions.

• An iron rod can only be placed on an iron rod that is longer than itself. - If an iron rod is placed on top of another iron rod, place it so that it is completely covered, but the end points do not overlap
• There is at least one laser that cuts each iron rod.
• The laser does not overlap either end of any iron rod

The figure below shows an example that satisfies the above conditions. The thick solid line drawn horizontally is the iron rod, the dot is the position of the laser, and the dotted arrow drawn vertically is the direction of the laser.

The arrangement of the laser and the iron bar can be expressed in order from left to right using parentheses as follows.

1. Lasers are represented by adjacent pairs of opening and closing parentheses ‘( )’. Also, all ‘( )’ must represent laser.
2. The left end of the iron rod is expressed as an opening parenthesis ‘ ( ’, and the right end is expressed as a closing parenthesis ‘) ’.

The parenthetical representation of the above example is given above the figure.

The iron rod is cut into several pieces by the laser. In the example above, the top two iron rods are cut into 3 and 2 pieces respectively, and the iron rods given in this way are cut into 17 pieces in total.

Write a program to find the total number of pieces of iron rod cut, given parentheses indicating the placement of the iron rod and the laser.

input

A parenthesis expression indicating the placement of the iron rod and laser on a single line is given without spaces. The maximum number of parentheses characters is 100,000.

()(((()())(())()))(())

(((()(()()))(())()))(()())

output

Prints an integer representing the total number of cut pieces per line.

17

24

Solution

use count

function solution(s) {
	let answer = 0,
		count = 0;

	for (let i in s) {
		if (s[i] === '(') count++;
		else {
			count--;

			if (s[i - 1] === '(') answer += count;
			else answer += 1;
		}
	}

	return answer;
}

use stack array

function solution(s) {
	let answer = 0,
		stack = [];

	for (let i = 0; i < s.length; i++) {
		if (s[i] === '(') stack.push(s[i]);
		else {
			stack.pop();

			if (s[i - 1] === '(') answer += stack.length;
			else answer += 1;
		}
	}

	return answer;
}