[Stack] Evaluate Reverse Polish Notation

1. 문제

LeetCode - Evaluate Reverse Polish Notation

• 역폴란드 표기법으로 산술 표현식을 나타내는 문자열 배열 tokens가 입력으로 제공(ex. ["2","1","+","3","*"])
• 표현식을 평가하고, 그 결과값을 반환하는 문제(ex. (2 + 1) * 3 -> 9)

2. 접근법

• 결과값을 계속 업데이트하는 방식으로 문제를 해결하기 위해 Stack 자료구조를 활용하기로 결정
• tokens 배열 안의 문자열 token이 숫자이면 일단 stack에 집어넣기
• 각 연산자마다 처리 방법을 다르게 정의(특히 '-'는 결과를 반대로 저장하고, '/'는 pop()한 뒤에 순서를 조정)
• if문 형식으로 연산자를 구별하여 테스트 통과 후, 개선된 switch문으로 변경하여 가독성 개선

3. 코드

class Solution {
    public int evalRPN(String[] tokens) {
        // 1. Stack 자료구조 활용
        Stack<Integer> stack = new Stack<>();

        // 2. tokens 배열 전체 순회하면서 stack에 연산 결과 업데이트
        for (String token : tokens) {
            // 2-1. token이 "+"일 때
            if (token.equals("+")) {
                stack.push(stack.pop() + stack.pop());
            }
            // 2-2. token이 "-"일 때
            else if (token.equals("-")) {
                stack.push(-(stack.pop() - stack.pop()));
            }
            // 2-3. token이 "*"일 때
            else if (token.equals("*")) {
                stack.push(stack.pop() * stack.pop());
            }
            // 2-4. token이 "/"일 때
            else if (token.equals("/")) {
                int first = stack.pop();
                int second = stack.pop();
                stack.push(second / first);
            }
            // 2-5. token이 단순 숫자일 때
            else {
                stack.push(Integer.valueOf(token));
            }
        }

        // 3. stack에 저장된 마지막 결과 값 리턴
        return stack.pop();
    }
}

4. 성능

- Runtime : 5ms

- Memory : 43.6mb

5. 개선

class Solution {
    public int evalRPN(String[] tokens) {
        // 1. Stack 자료구조 활용
        Stack<Integer> stack = new Stack<>();

        // 2. tokens 배열 전체 순회하면서 stack에 연산 결과 업데이트
        for (String token : tokens) {
            // switch 문으로 가독성 개선
            switch (token) {
                case "+" -> stack.push(stack.pop() + stack.pop());
                case "-" -> stack.push(-(stack.pop() - stack.pop()));
                case "*" -> stack.push(stack.pop() * stack.pop());
                case "/" -> {
                    int first = stack.pop();
                    int second = stack.pop();
                    stack.push(second / first);
                }
                default -> stack.push(Integer.valueOf(token));
            }
        }

        // 3. stack에 저장된 마지막 결과 값 리턴
        return stack.pop();
    }
}