10032 괄호 검사 Silver IV

문제

괄호 문자열이 주어졌을 때, 올바른 괄호 문자열인지 판별하는 프로그램을 작성하시오.

올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. S가 올바른 괄호 문자열이면 (S)도 올바른 괄호 문자열이다.
3. S와 T가 올바른 괄호 문자열이면 ST도 올바른 괄호 문자열이다.

입력

첫째 줄에 테스트 케이스의 수 T (1 ≤ T ≤ 100)가 주어진다. 각 테스트 케이스는 괄호 문자열로 이루어져 있으며, 길이는 2 이상 1,000 이하이다.

출력

각 테스트 케이스마다 올바른 괄호 문자열이면 YES, 아니면 NO를 출력한다.

3
(())()
(()(
))((

YES
NO
NO