[アルゴリズム]Back-9012(括弧)/Java

import java.util.*;
import java.io.*;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Stack<Character> stack = new Stack<Character>();
		
		int T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		for(int t = 0 ; t < T ; t++) {
			String s = br.readLine();
			int len = s.length();
			if(len %2 == 1) {
				sb.append("NO").append("\n");
				continue;
			}
			char c;
			boolean flag = false;
			
			for(int i = 0 ; i < len ;i++ ) {
				c = s.charAt(i);
				
				if(c == '(') {
					stack.push(s.charAt(i));
				}else if(c == ')') {
					if(stack.isEmpty()) {
						flag = true;
						break;
					}
					stack.pop();
				}
			}
			if(!flag && stack.isEmpty()) {
				sb.append("YES").append("\n");
				
			}else if(flag || !stack.isEmpty() ) {
				sb.append("NO").append("\n");
			}
			stack.clear();
		}
		System.out.println(sb);
	}
}