문제

후위 표기법 문제이다. 스택 알고리즘의 대표적인 문제이다.
Input: tokens = ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

구현 전 예상 풀이

1. 숫자를 스택에 push
2. 연산자를 만나면 2개의 숫자를 pop하여 연산한다. 그리고 다시 스택에 push

주어진 배열의 끝까지 1과 2를 반복하면 결과값이 스택에 남는다.

구현 코드

구현에서 중요한 점은 연산의 순서이다. 스택은 LIFO 자료구조여서 스택에서 먼저 꺼낸 숫자가 2번째 꺼낸 숫자 뒤에서 연산되어야 한다. 특히 '-', '/' 연산자에서

EX)
["3","1","-"] 경우 3 - 1 연산되어야한다.
스택에 push하면 스택에 3,1 순서로 스택에 존재하고
pop하면 1,3 순서로 스택에서 나온다.
따라서 2번째로 꺼낸 3을 앞에적고 먼저 꺼낸 1을 뒤에 연산해야한다.

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

        for (String token : tokens) {

            switch (token) {
                case "+" -> stack.push(String.valueOf(Integer.parseInt(stack.pop()) + Integer.parseInt(stack.pop())));
                case "-" -> {
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
                    String num = String.valueOf(num2 - num1);
                    stack.push(num);
                }                
                case "*" -> stack.push(String.valueOf(Integer.parseInt(stack.pop()) * Integer.parseInt(stack.pop())));
                case "/" -> {
                    int num1 = Integer.parseInt(stack.pop());
                    int num2 = Integer.parseInt(stack.pop());
                    String num = String.valueOf(num2 / num1);
                    stack.push(num);
                }
                default -> stack.push(token);
            }
        }

        return Integer.parseInt(stack.pop());
    }
}

개선점

다른 사람의 풀이를 보고 깨달았는데 스택을 Integer타입으로 생성하면 push할때만 타입 변환을 하면 된다.
지금은 총 2번 타입 변환이 발생한다.
1. 스택에서 pop하여 숫자를 연산하기위해 (String -> int)
2. 연산 후 다시 스택에 push하기 위해 (int -> String)

코드를 수정해보겠다.

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

        for (String token : tokens) {

            switch (token) {
                case "+" -> {
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 + num1);
                }
                case "-" -> {
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 - num1);
                }
                case "*" -> {
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 * num1);
                }
                case "/" -> {
                    num1 = stack.pop();
                    num2 = stack.pop();
                    stack.push(num2 / num1);
                }
                default -> stack.push(Integer.parseInt(token));
            }
        }

        return stack.pop();
    }
}

150. Evaluate Reverse Polish Notation
참고한 풀이 링크