[알고리즘] LeetCode - Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation - LeetCode

문제 설명

• 역 폴란트 표기법이라고 하지만 쉽게 말해 후위 표기법이다.
• 후위 표기법으로 주어진 식이 문자형 배열로 주어진다.
• 후위표기법으로 표기된 식을 계산한 결과 값을 반환해야 한다.
• 유효한 연산자는 +, -, *, / 가 있다.
• 두 정수 사이의 나눗셈에서 소숫점은 버린다.

문제 해결

• token값이 숫자가 아니면 stack에서 2개의 값을 pop한 후 주어진 연산 기호로 계산 후 다시 stack에 push한다.
• token값이 숫자라면 그대로 stack에 push한다.
• 반복문을 다 돌고 마지막에 stack에 남은 값이 최종 연산 값이므로 그대로 반환한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String now = tokens[i];

            if (now.equals("+") || now.equals("-") || now.equals("*") || now.equals("/")) {
                int B = stack.pop();
                int A = stack.pop();
                stack.push(getResult(A, B, now));
            } else {
                stack.push(Integer.parseInt(now));
            }
        }

        return stack.pop();
    }

    int getResult(int A, int B, String now) {
        switch(now) {
            case "+": 
                return A + B;
            case "-":
                return A - B;
            case "*":
                return A * B;
            default:
                return A / B;
        }
    }
}

결과

시간	메모리
6 ms	42.9 MB