[알고리즘 PS] Stack을 이용해서 Java로 수식 내 괄호 유효성 검사하기

문제

괄호( ), { }, [ ]가 포함된 수식을 입력 받고 해당 수식의 괄호가 잘 닫혀 있는지 확인하라.

예제 입력 & 출력

$ 2 * (3 + 10)) - 1 + [(10 + 10 + {20 + 1})]
$ 정답

$ (3 + 10) * ((3) * 2 / 4) - 1 + [{(10 + 10 + {20 + 1})]
$ 오류

 

정답 코드

 

접근 방법

여는 괄호들을 만날 때 마다 stack에 추가하고 닫는 괄호를 만날 때 마다 stack에서 pop한다.

단, 이 과정에서 stack에서 pop 한 괄호가 닫는 괄호의 짝이 맞는지를 검증한다.

 

오답 후보

오답인 경우의 후보를 미리 정해보자.

1. 예외 후보 : stack 이 비어있는데 )}]를 만나서 pop 하려는 경우
2. 예외 후보 : 문자열 검증이 끝났는데 stack 이 비어있지 않은 경우
3. 예외 후보 : stack 에서 pop 한 값과 예상 값이 다른 경우

import java.util.Stack;

public class Main {

    /* 예외 1 : stack 이 비어있는데 )}]를 만나서 pop 하려는 경우
    *  예외 2 : 문자열 검증이 끝났는데 stack 이 비어있지 않은 경우
    *  예외 3 : stack 에서 pop 한 값과 예상 값이 다른 경우
    **/

    public static void main(String[] args) {
        Stack<Character> stack = new Stack<>();
        String correct = "2 * (3 + 10)) - 1 + [(10 + 10 + {20 + 1})]";
        String incorrect = "[(({(])}))";
        int answer = 0;
        char[] arr = correct.toCharArray();

        for(char iter : arr) {
            pushStack(stack, iter);
            answer = checkCondition(stack, iter);
            if(answer != 0) break;
        }
        if(stack.isEmpty() && answer == 0) System.out.println("정답"); // 예외 2 검증
        else System.out.println("오답");
    }

    private static void pushStack(Stack<Character> stack, char c) {
        if((c == '(') || (c == '{') || (c == '[')) {
            stack.push(c);
        }
    }

    private static int checkCondition(Stack<Character> stack, char c) {
        if((c == ')') || (c == '}') || (c == ']')) {
            if(stack.isEmpty()) return 1; // 예외 1
            else { // 예외 3
                char pop = stack.pop();
                if( (pop == '(' && c == ')')
                        || (pop == '{' && c == '}')
                        || (pop == '[' && c == ']')) return 0;
                else return 3;
            }
        }
        return 0;
    }
}