[LeetCode] 150. Evaluate Reverse Polish Notation

Evaluate Reverse Polish Notation - LeetCode

역 폴란드어 표기법(후위 표기법)으로 산술식을 나타내는 문자열 토큰 배열이 주어집니다.

산술식을 계산하여 최종값을 리턴하는 문제입니다.

 

Example 1:

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
Output: 22
Explanation: ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

 

문제접근

Stack을 이용해서 풀이했습니다.

이 문제는 전형적인 Stack문제로 실제 CPU로 계산식이 가기전에 후위연산으로 바꿀때

Stack을 사용한다고 합니다. 

 

HashSet<String> OPERATERS = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
    public int evalRPN(String[] tokens) {
        Stack<Integer> stk = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            if (OPERATERS.contains(tokens[i])) {
                Integer first = stk.pop();
                Integer sec = stk.pop();

                stk.push(culcurate(first, sec, tokens[i].charAt(0)));
            } else {
                stk.push(Integer.valueOf(tokens[i]));
            }
        }
        Integer result = stk.pop();
        return result;
    }

    private Integer culcurate(final Integer first, final Integer sec, char token) {
        Integer sum = 0;
        if (token == '+') {
            sum = first + sec;
        } else if (token == '-') {
            sum = sec - first;
        } else if (token == '*') {
            sum = first * sec;
        }else if (token == '/') {
            sum = sec / first;
        }
        return sum;
    }

 

시간복잡도

For-loop를 tokens의 길이만큼 하고있습니다.

그안에서 Stack메서드와 단순한 연산은 모두 O(1)입니다.

따라서 O(n)의 시간복잡도가 필요합니다. 

 

느낀점

Stack은 실제로 아주 많이 쓰이는 자료구조이기 때문에 잘 활용해야겠습니다.