괄호

25 June 2019

문제 : https://www.acmicpc.net/problem/9012

이번은 주어진 문자열이 올바른 괄호열인지 판단하는 문제를 풀어보도록 하겠습니다. 

import java.util.Scanner;

public class Main {

    public static void main(String args[]) {

        Scanner sc = new Scanner(System.in);

        int size = sc.nextInt();

        Stack stack = new Stack(50);

        for (int i = 0; i < size; i++) {
            String val = sc.next();
            stack.init();
            String ret = solve(stack, val);
            System.out.println(ret);
        }
    }

    private static String solve(Stack stack, String val) {
        for (int k = 0; k < val.length(); k++) {
            if (val.charAt(k) == '(') {
                stack.push(1);
            } else {
                int ret = stack.pop();
                if (ret == -1) {
                    return "NO";
                }
            }
        }

        if (stack.isEmpty()) {
            return "YES";
        } else {
            return "NO";
        }
    }
}

class Stack {
    private int top = -1;
    private int[] queue;

    Stack(int max) {
        queue = new int[max];
    }

    void init() {
        this.top = -1;
    }

    void push(int val) {
        top++;
        queue[top] = val;
    }

    int pop() {
        if (top == -1) {
            return -1;
        }
        int val = queue[top];
        top--;
        return val;
    }

    boolean isEmpty() {
        return top == -1;
    }
}
먼저 class를 통해 stack을 구현해주도록 합니다.
들어오는 string의 값을 읽고, 각 char별로 '('가 들어온 경우는 stack에 push, ')'가 들어온 경우는 stack에 pop을 해줍니다.
이 경우, pop을 할 때 -1이 나오게 되면 앞뒤로 문자열이 맞지 않는 경우니, "NO"를 return 해주도록 합니다.
문자열의 모든 값 체크가 끝난 후, stack의 size가 0이면 "YES", 아닌 경우는 "NO"를 return해주도록 합니다.