#2077 괄호 문자열

45  2 s   128 MB  

Description

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

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

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

Input

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

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

Output

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

Sample Input

Sample Output

6 
(())()) 
(((()())() 
(()())((())) 
((()()(()))(((())))() 
()()()()(()()())() 
(()((())()( 
NO 
NO 
YES 
NO 
YES 
NO 

Source

ACM-ICPC 2012 인터넷 예선 G번