백준 9012번 괄호 Parenthesis

Problem

Parenthesis String (PS) consists of two parenthesis symbols ‘(’ and ‘)’ only. In parenthesis strings, some strings are called a valid PS (shortly, VPS). Let us give the formal definition of VPS. A single “( )” is a member of VPS, called the base VPS. Let x and y be a member of VPS. Then “(x)”, a VPS which encloses a VPS x with a single pair of parenthesis, is also a member of VPS. And xy, the concatenation of two VPS x and y, is a member of VPS. For example, “(())()” and ((()))” are all VPS, but “(()(”, “(())()))” and “(()” are not VPS. You are given a set of PS. You should decide if the input string is VPS or not.

Input

Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. Then PS’s are given in the following T lines one by one. The length of each PS is between 2 and 50, inclusively.

Output

Your program is to write to standard output. Print the result in each line. If the input string is a VPS, then print “YES”. Otherwise print “NO”.

Example

Input 1

6
(())())
(((()())()
(()())((()))
((()()(()))(((())))()
()()()()(()()())()
(()((())()(

Output 1

NO
NO
YES
NO
YES
NO

Input 2

3
((
))
())(()

Output 2

NO
NO
NO

Answer

1

Using a stack method,

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

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));

        String inputStr;
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            inputStr = br.readLine();
            Stack<Character> openStack = new Stack<>(); // store open parentheses
            boolean shortOfOpen = false;

            for (int j = 0; j < inputStr.length(); j++) {
                if (inputStr.charAt(j) == '(') {
                    openStack.push('(');
                } else {
                    // ')'
                    if (openStack.isEmpty()) {
                        shortOfOpen = true;
                        break;
                    }
                    openStack.pop();
                }
            }
            if (openStack.isEmpty() && !shortOfOpen) {
                bw.write("YES");
            } else {
                bw.write("NO");
            }
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

2

Use a count variable instead of stack since we know every element in the stack will be an open parenthesis ‘(,’ and we only need to know whether the stack is empty or not in the end.

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));

        String inputStr;
        int n = Integer.parseInt(br.readLine());

        for (int i = 0; i < n; i++) {
            inputStr = br.readLine();
            int countOpen = 0;
            boolean shortOfOpen = false;

            for (int j = 0; j < inputStr.length(); j++) {
                if (inputStr.charAt(j) == '(') {
                    countOpen++;
                } else {
                    // ')'
                    if (countOpen == 0) {
                        shortOfOpen = true;
                        break;
                    }
                    countOpen--;
                }
            }
            if (countOpen == 0 && !shortOfOpen) {
                bw.write("YES");
            } else {
                bw.write("NO");
            }
            bw.newLine();
        }
        bw.flush();
        bw.close();
    }
}

Reference

The problem is taken from baekjoon