문제2077--괄호 문자열

2077: 괄호 문자열

실행시간 제한: 2 Sec  메모리사용 제한: 128 MB
제출: 203  통과: 82
[제출] [채점기록] [묻고답하기]

문제 설명

괄호 문자열(이하 PS)는 2개의 문자 '('와 ')'로만 구성된다. PS중에서 올바른 PS들의 집합(이하 VPS)은 다음과 같이 정의된다.

PS "()"는 VPS에 속하며, 이를 기본 VPS라 한다. 만약 괄호 문자열 x와 y가 VPS에 속한다면, "(x)"역시 VPS에 속하며, xy 또한 VPS에 속한다.

예로 들어 "(())()"와 "((()))"는 모두 VPS에 속하는 PS다. 하지만 "(()("나 "(())()))", 그리고 "(()"는 VPS에 속하지 않는다. PS가 주어졌을 때 이것이 VPS에 속하는지 아닌지 찾는 프로그램을 작성하라.

입력 설명

입력의 첫 줄에는 테스트 케이스의 개수를 뜻하는 자연수 T가 입력된다. 

그 다음 줄 부터 T개의 PS가 입력된다. PS의 길이는 2이상 50이하의 짝수다. PS는 위의 정의와 같이 '('와 ')'로 만 입력되며, PS사이에 공백 같은 이외의 문자는 입력되지 않는다 가정한다.

출력 설명

각 테스트 케이스로 입력되는 PS에 대해 VPS에 속할 경우 "YES"를 그렇지 않을 경우 "NO"를 한줄에 하나씩, 입력된 순서대로 출력한다.

입력 예시 Copy

6 
(())()) 
(((()())() 
(()())((())) 
((()()(()))(((())))() 
()()()()(()()())() 
(()((())()( 

출력 예시 Copy

NO 
NO 
YES 
NO 
YES 
NO 

출처/분류