[LeetCode/Top Interview 150] [Stack] 150. Evaluate Reverse Polish Notation

문제 링크: https://leetcode.com/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150
사용 언어: Java(OpenJDK 17. Java 8)

난이도: medium

문제:

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.

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

Constraints:

1 <= tokens.length <= 104
tokens[i] is either an operator: "+", "-", "*", or "/", or an integer in the range [-200, 200].

전략:

숫자(-200~200 사이의 정수) 또는 연산자(+,-,*,/)인 토큰을 받아서 폴란드식 연산을 통해 숫자값을 리턴해야한다. (2 3 + 가 2 + 3 으로 계산되는 방식)

코드 구현:

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> s = new Stack<Integer>();
        for (int i=0;i<tokens.length;i++) {
            if ("+-*/".contains(tokens[i])) {
                int e2 = s.pop();
                int e1 = s.pop();
                int ne = 0;
                if (tokens[i].equals("+")) {
                    ne = e1+e2;
                } else if (tokens[i].equals("-")) {
                    ne = e1-e2;
                } else if (tokens[i].equals("*")) {
                    ne = e1*e2;
                } else if (tokens[i].equals("/")) {
                    ne = e1/e2;
                }
                s.push(ne);
            } else {             
                s.push(Integer.parseInt(tokens[i]));   
            }
        }
        return s.pop();
    }
}

실행결과:
Time: 5 ms (98.1%), Space: 42.9 MB (94.68%) - LeetHub
https://github.com/1-vL/LeetCode/blob/main/0150-evaluate-reverse-polish-notation/0150-evaluate-reverse-polish-notation.java

개선 방안:

이 이상 가는 개선은 딱히 떠오르지 않는다. 굳이 꼽는다면 연산자를 구분하는데에 지금의 if-else if 문 보다 더 짧은 구현방식이 존재하지 않을까 정도?

Discuss 탭의 타인 코드:

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

        for(String s : tokens){
            if(s.equals("+") || s.equals("*") || s.equals("/") || s.equals("-")){
                int b = st2.pop();
                int a = st2.pop();
                int res = cal(a, b, s.charAt(0));
                st2.push(res);
                
            } else {
                st2.push(Integer.parseInt(s));
            }
        }
        return st2.pop();
    }
    private int cal(int a, int b, char oprtr){
        if(oprtr == '+'){
            return a + b;
        } else if(oprtr == '-'){
            return a - b;
        } else if(oprtr == '*'){
            return a * b;
        } else {
            return a / b;
        }
    }
}
7 ms (58.32%), Space: 42.6 MB (99.06%) - LeetHub

회고:

역시 로직 자체는 동일한 만큼 오차 범위 내에서 동일한 수준의 결과가 나온 것 같다.
이번 문제는 간단한 편이었고, 기존 사용하던 leethub 플러그인 대신 처음으로 leethub v2 플러그인과 새 UI로 풀어본 문제였는데 확실히 더 편해진 부분이 있는 것 같다.