[JAVA] 백준 9012 : 괄호

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int count = Integer.parseInt(br.readLine());
        Character[][] ps = new Character[count][];
        for (int i = 0; i < count; i++) {
            String line = br.readLine();
            Character[] charArray = new Character[line.length()];
            for (int j = 0; j < line.length(); j++) {
                charArray[j] = line.charAt(j);
            }
            ps[i] = charArray;
        }
        for (int i = 0; i < count; i++) {
            NodeManager<Character> nodeManager = new NodeManager<>();
            boolean flag = false;
            for (int j = 0; j < ps[i].length; j++) {
                if (ps[i][j] == '(') {
                    nodeManager.push(new StackNode<>(ps[i][j]));
                } else {
                    if (nodeManager.pop() == null) {
                        bw.write("NO" + "\n");
                        flag = true;
                        break;
                    }
                }
            }
            if (!nodeManager.isEmpty()) {
                bw.write("NO" + "\n");
            } else if (!flag) bw.write("YES" + "\n");
        }


        br.close();
        bw.flush();
        bw.close();
    }
}

class StackNode<T> {
    StackNode<T> underNode;
    T value;

    public StackNode(T value) {
        this.value = value;
        underNode = null;
    }

    public T getValue() {
        return value;
    }

    public StackNode<T> getUnderNode() {
        return underNode;
    }

    public void setUnderNode(StackNode<T> underNode) {
        this.underNode = underNode;
    }
}

class NodeManager<T> {
    int size;
    StackNode<T> top;

    public NodeManager() {
        size = 0;
        top = null;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public void push(StackNode<T> node) {
        if (isEmpty()) {
            top = node;
        } else {
            node.setUnderNode(top);
            top = node;
        }
        size++;
    }

    public T pop() {
        StackNode<T> node = top;
        if (isEmpty()) return null;
        else if (top.getUnderNode() == null) {
            top = null;
        } else {
            top = top.getUnderNode();
        }
        size--;
        return node.getValue();
    }
}