[Leetcode] 150. Evaluate Reverse Polish Notation - JS

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

 

1. 문제 분석

문제분석
--------------------
- 역폴란드 표기법으로 산술표현식을 나타내는 문자열 토큰 배열이 주어진다.
- 표현식을 평가하여 정수를 반환하라.
- 유효한 연산자는 '+', '-', '*' 및 '/'입니다.
- 각 피연산자는 정수이거나 다른 표현식일 수 있습니다.
- 두 정수 사이의 나눗셈은 항상 0을 향해 잘립니다.
- 0으로 나누는 일은 없을 것입니다.
- 입력은 역방향 폴란드어 표기법으로 유효한 산술 표현식을 나타냅니다.
- 답과 모든 중간 계산은 32비트 정수로 표현될 수 있습니다.

제한조건
--------------------
- 1 <= tokens.length <= 10^4
- tokens[i]는 '+', '-', '*' 및 '/' 또는 -200 ~ 200 사이의 정수이다.

 

2. 접근 방법

접근방법
--------------------
연산자가 나오면 두 피연산자를 평가해야하므로 stack에 피연산자를 넣어두어 접근해보자.

연산자 로직을 저장한 hashmap 초기화
stack = [] 초기화

tokens 순회
    - 연산자면 stack 최신 2개 피연산자 빼내어 연산
    - 피연산자면 stack 추가

순회 종료 시 stack 마지막 요소 반환

 

 

3. 코드

var evalRPN = function(tokens) {
    const operators = {
        '+':function (a,b) {return a + b},
        '-':function (a,b) {return a - b},
        '/':function (a,b) {return Math.trunc(a / b)},
        '*':function (a,b) {return a * b},
    }
    const operatorKeys = Object.keys(operators)
    const stack = [];

    for (let tk of tokens) {
        if (operatorKeys.includes(tk)) {
            const b = stack.pop();
            const a = stack.pop();
            const res = operators[tk](a,b)
            stack.push(res)
        } else {
            stack.push(Number(tk))
        }
    }
    return stack[0]
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

연산자에 대한 함수 로직을 hashmap에 저장해두었다.

소수점 이하 처리를 어떻게 해야하는지 잘 이해를 못했는데, 정수부분만 사용한다는 의미였다.

Math.trunc()는 숫자의 정수부분만 사용하는 함수이다. 위 상황에서 적절하다.

 

예전에 알고리즘 강의에서 들었던 DFS 챕터의 후위순회 비슷한 개념인 것 같다.

DFS에서 후위순회는 가장 깊은 곳부터 순회하는 방법인데, 위 문제에서도 피연산자를 stack에 저장해두고

연산자가 등장하면 최신 것들부터 빼내어 계산하는 방법과 비슷해서 기억이 났다.