150. Evaluate Reverse Polish Notation

haaaalin·2023년 8월 29일

알고리즘 코테

LeetCode

목록 보기

15/31

문제 링크: https://leetcode.com/problems/evaluate-reverse-polish-notation/?envType=study-plan-v2&envId=top-interview-150

문제

역 폴란드어 표기법으로 산술식을 나타내는 아래와 같은 문자열 토큰 배열이 주어진다.

tokens = ["2","1","+","3","*"]

연산자: +, -, *, /
각 피연산자는 정수 또는 다른 표현식
0으로 나누는 일은 없다.
입력은 역연산 표기법으로 유효한 산술식 나타냄
답과 모든 중간 계산은 32비트 정수로 표현 가능

입력

역 폴란드어 표기법으로 산술식을 나타내는 아래와 같은 문자열 토큰 배열 tokens

출력

int 계산 결과

나의 풀이

접근

숫자와 연산자가 일반 계산식처럼 숫자와 연산자가 계산 순서대로 섞여 있는 게 아니라, 숫자 따로, 연산자 따로 있기 때문에, 숫자만 모아야 한다고 생각했다.

숫자를 모으고, 그 후에 연산자를 만나면, 제일 최근 숫자를 사용해야 했기 때문에, 바로 stack을 생각했다.

아래의 두 가지 생각으로 구현했다

숫자를 한 곳에 모은다.
최근 숫자를 사용해야 한다. → stack

구현 코드

class Solution {
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        // 숫자 스택 사용
        for (String token: tokens) {
            if (token.matches("[-+]?\\d*\\.?\\d+")) {
                stack.push(Integer.parseInt(token));
                continue;
            }
            int first = stack.pop();
            int second = stack.pop();
            switch(token) {
                case "+":
                    stack.push(first+second);
                    break;
                case "-":
                    stack.push(second-first);
                    break;
                case "*":
                    stack.push(first*second);
                    break;
                case "/":
                    stack.push(second/first);
                    break;                                                        
            }
        }
        return stack.peek();
    }
}

tokens의 token을 탐색한다.
만약, 숫자면 stack에 넣고
만약, 연산자면 stack에 최상위 2개 숫자를 꺼내서 연산한 후, 그 결과를 다시 stack에 넣는다
stack 최상위 값 return

결과

하지만 너무 느리고, 너무 공간을 많이 사용했다.

다른 풀이

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;
        }
    }
}