문제

문자열로된 토큰 배열을 입력으로 준다. 각 토큰은 int형 숫자을 문자열로 나타낸 것이거나 연산자 +, -, *, /로 이루어져있다. 또한 토큰의 순서는 후위 표기법으로 표현되어있다. 후위 표기법으로 표현된 토큰들을 계산하는 문제이다.

풀이

후위 표기법의 계산은 Stack 자료구조로 쉽게 할 수 있기 때문에 컴퓨터가 연산하기 좋은 표기법이다.

컴퓨터가 연산하기 좋아 컴파일러에서 사용한다고 한다.

일반적으로 우리가 사용하는 표기법은 중위 표기법이다. 3+5*7과 같이 연산자가 피연사자들의 중간에 위치한다. 반면 후위 표기법은 피연산자들이 먼저 표기한다. 3+5*7를 후위 표기법으로 나타내면 357*+가 된다.

이 후위 표기법의 계산은 간단하다.

1. 연산자를 만나면 Stack에서 피연산자 2개를 pop한다.
2. 피연산자 2개를 연산자로 연산한다.
3. 2번 과정에서 연산한 결과를 다시 Stack에 push한다.
4. Stack에 피연산자가 1개 남을 때까지 반복한다.

계산할 때 주의할 점은 피연산자를 2개 꺼내 연산할 때 push 된 순서로 연산해야 한다는 것이다. +, *는 상관없지만 -, /의 경우 순서가 중요하기 때문이다. 예를들어 num1이 push되고 num2가 푸쉬되었다면 num1 - num2와 같은 순서로 연산해야한다.

이 문제에서는 연산 과정에서 발생하는 예외들은 대부분 테스트 케이스에 존재하지 않기 때문에 단순한 Stack 자료구조에 대한 문제다. 후위 표기법을 Stack으로 계산하는 코드는 다음과 같다.

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if (!isOperator(token)) {
                stack.push(Integer.parseInt(token));
            } else {
                stack.push(calculate(token, stack.pop(), stack.pop()));
            }
        }

        return stack.pop();
    }

    private boolean isOperator(String token) {
        return "+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token);
    }

    private int calculate(String operator, int num2, int num1) {
        switch (operator) {
            case "+":
                return num1 + num2;
            case "-":
                return num1 - num2;
            case "*":
                return num1 * num2;
            default:
                return num1 / num2;
        }
    }
}

이 풀이는 시간복잡도와 공간복잡도 모두 $O(n)$를 갖는다.