[스택] 백준 9012

 

import java.util.*;

public class Main {
	
	static Stack<Character> stk = new Stack<Character>();
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);		
		int T = sc.nextInt();	
		
		for (int i = 0; i < T; i++) {
			String str = sc.next();
			if(VPC(str)) {
				System.out.println("YES");
			}else {
				System.out.println("NO");
			}
			stk.clear();	// 다음 VPC검사를 위해 clear
		}
	}
	
	public static boolean VPC(String str) {
		char[] arr = str.toCharArray();
		
		for (int i = 0; i < arr.length; i++) {
			if(arr[i] == '(') {
				stk.push(arr[i]);
			}
			else if (arr[i] == ')') {
				if(stk.empty()) {	// 비어있으면
					return false;
				}else {	// 비어있지 않으면
					char tmp = stk.peek();
					if(tmp == ')') {
						return false;
					}else {
						stk.pop();						
					}
				}
			}
		}
		
		if(stk.empty()) {
			return true;
		}else {
			return false;
		}
	}
}