괄호 속의 별
면접 대비시간 제한2초메모리 제한512 MB
별 하나가 끼어 있는 올바른 괄호 문자열에서 별을 둘러싸는 짝 괄호의 개수를 구합니다.
문제
별 기호 *가 하나 삽입된 올바른 괄호 문자열 가 주어진다.
올바른 괄호 문자열은 다음 규칙으로 만들 수 있다.
- 빈 문자열은 올바른 괄호 문자열이다.
- 올바른 괄호 문자열 두 개를 이어 붙인 것은 올바른 괄호 문자열이다.
- 가 올바른 괄호 문자열이면
(, ,)를 이 순서로 이어 붙인 것은 올바른 괄호 문자열이다.
예를 들어 ()()와 (()())는 올바른 괄호 문자열이다. )(와 )()(()는 올바른 괄호 문자열이 아니다.
별을 둘러싸는 괄호 짝이 몇 개인지 세어야 한다.
문자열 의 번째 문자를 라 하자. 과 의 짝이 짝 맞는 괄호 쌍이라는 것은 이 (, 이 )이고, 별 기호를 무시했을 때 두 문자가 감싸는 문자열이 올바른 괄호 문자열이라는 뜻이다.
입력
입력은 하나의 테스트 케이스로 이루어지며 다음 형식으로 주어진다.
S$S$
는 별 *가 정확히 하나 어딘가에 삽입된 올바른 괄호 문자열이다. 의 길이는 이상 이하이다.
출력
답을 한 줄에 출력한다.