백준 9012 괄호

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

public class Main {
	 
	public static void main(String[] args) {
	
		 
		 Scanner sc=new Scanner(System.in);
		 Stack<Character> stack = new Stack<>(); 
		  
		 StringBuilder st=new StringBuilder();
		 BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		 try {
			 int n=Integer.parseInt(br.readLine());		 
			  
			 for(int i=0;i<n;i++) {
				 String s=br.readLine();
				  
				 if(checkVPS(s)) st.append("YES\n");
				 else st.append("NO\n");
				 
			 }
			 System.out.println(st);
		 
		  		 
		 }catch(Exception e) {
			 
		 }
		   
	
	}
	
	
	public static boolean checkVPS(String s) {
		char arr []=new char[s.length()];
		Stack<Character> stack = new Stack<>();
		 
		 for(int i=0;i<s.length();i++) {
			 arr[i]=s.charAt(i);
		 }
		 
		 
		 char open='(';
		 
		 int idx=0;
		 while(idx<s.length()) {
			 if(arr[idx]==open) {
				 stack.push(open);
			 }
			 else {
				 if(!stack.empty()) {
					 stack.pop();
				 }
				 else {
					 break;
				 }
			 }
			 idx++;
		 }
		      if(idx<s.length()) {		    	  
		    	  return false;
		      }
		 	  else if(stack.empty()) {
		 		 return true;
			 }
			 else {						 
				 return false;
			 }		 
	}
}