백준-9012 괄호

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main_9012{
	
    // 괄호 문자열의 유효성 검사
    public static String isValid(String s) {//String s="(())())"
    	                                    //s.toCharArray() ==> {"(","(",")",")","(",")")};
        Stack<Character> stack = new Stack<>();
        
        for (char c : s.toCharArray()) {
            if (c == '(') { //여는 괄호는 스택에~~~
                stack.push(c); // 여는 괄호면 push
            } else { //닫는 괄호는 검사~~~~~
                if (stack.isEmpty()) return "NO"; // 짝이 없으면 NO
                stack.pop(); // 짝이 맞는 괄호 제거
            }
        }
        return stack.isEmpty() ? "YES" : "NO"; // 스택이 비었으면 YES
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine()); // 테스트케이스 수

        while (testCase-- > 0) {
            System.out.println(isValid(br.readLine())); // 결과 출력
//                                        "(())())"
        }
    }//main
}