[ Top Interview 150 ] 150. Evaluate Reverse Polish Notation

문제

150. Evaluate Reverse Polish Notation

You are given an array of strings tokens that represents an arithmetic expression in a Reverse Polish Notation

Evaluate the expression. Return an integer that represents the value of the expression.

• Note that:
  • The valid operators are '+', '-', '*', and '/'.
    Each operand may be an integer or another expression.
    The division between two integers always truncates toward zero.
  • There will not be any division by zero.
  • The input represents a valid arithmetic expression in a reverse polish notation.
  • The answer and all the intermediate calculations can be represented in a 32-bit integer.

문제 정리

• Input : Reverse Polish Notation으로 되어 있는 계산식
• Output : 계산 결과
• Example
  • Input: tokens = ["2","1","+","3","*"]; Output: 9
    • Explanation: ((2 + 1) * 3) = 9
  • Input: tokens = ["4","13","5","/","+"]; Output: 6
    • Explanation: (4 + (13 / 5)) = 6

Reverse Polish Notation

• 역폴란드 표기법(RPN, reverse Polish notation) 또는 후위 표기법(후치 표기법)이라고 불림
• 연산 기호를 두 수의 중간에 쓰는 중위 표기법과 달리, 연산 기호를 두 수의 뒤에 쓴다.
• 예시
  • 중위 표기법 2 + 3
  • 후위 표기법 2 3 +
• 장점
  • 수식을 계산할 때 특별한 변환이 필요없이, 수식을 앞에서부터 읽어 나가면서 스택에 저장하면 된다
  • 연산 순서를 가로를 이용해서 표기하지 않아도 헷갈리지 않는다.

알고리즘 전략

• 위에서 알아본 이론적인 내용에서와 같이, Stack을 이용한다.
• tokens을 앞에서부터 순회하면서
  • 해당 token이 숫자일 경우, Stack에 쌓아 놓는다.
  • 해당 token이 연산자일 경우, Stack 안에 있는 두 수를 꺼내서 연산을 하고 해당 결과값을 Stack에 쌓아 놓는다.
• 마지막에 Stack에 남은 하나의 결과값을 return 한다.

답안

• Time complexity : $O(n)$
• Space complexity: $O(n)$

class Solution {

    private static final String[] notations = new String[]{"+", "-", "*", "/"};

    public int evalRPN(String[] tokens) {

        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String token = tokens[i];
            if (!isNotation(token)) {
                stack.add(Integer.parseInt(token));
                continue;
            }

            int tempResult = calculate(stack.pop(), stack.pop(), token);
            stack.add(tempResult);
        }

        return stack.pop();
    }

    private boolean isNotation(String token) {
        for (int i = 0; i < notations.length; i++) {
            if (notations[i].equals(token)) {
                return true;
            }
        }
        return false;
    }

    private int calculate(int num1, int num2, String notation) {
        if ("*".equals(notation)) {
            return num2 * num1;
        }
        if ("/".equals(notation)) {
            return num2 / num1;
        }
        if ("+".equals(notation)) {
            return num2 + num1;
        }
        if ("-".equals(notation)) {
            return num2 - num1;
        }
        throw new IllegalArgumentException();
    }
}