[LeetCode][JS] 150번 Evaluate Reverse Polish Notation

문제 유형

수학, 배열, 스택

 

문제

들어오는 배열은 후위표기식 순서이다. (Reverse Polish Notation) . 유효한 연산자는 +, -, *및 /입니다. 각 피연산자는 정수 또는 다른 표현식일 수 있습니다. 두 정수 간의 나누기는 0으로 잘려야 합니다 .후위 표기식을 계산하시오.

 

예시

Input: tokens = ["2","1","+","3","*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Input: tokens = ["4","13","5","/","+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

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

 

풀이

빈 스택을 만들어주고 연산자를 담은 객체를 만들어준다. 각 키에 함수를 넣어주는 방식.

for을 돌려 만약 연산자가 나오면 해당 pop을 2회해주고 함수를 실행해준다. 

그리고 다시 스택에 push를 해준다. 마지막으로 스택에 있는 값을 pop해서 반환해준다. 

 

🔎후위 표기식

규칙

1. 연속해서 스택에 넣어준다.

2. 연산자를 만나면 스택에서 pop과정을 2회 해준다 👉🏻 연산을 하려면 피연산자 2개와 연산자 1개 필요

3. 연산한 것을 다시 스택에 push해준다.

4. 위 과정을 반복한다. 

 

 

예 ) ["2","1","+","3","*"]

 

1. stack을 만들어준다. 

 

2. stack에 차례대로 넣어준다.

2

2

1

 

3. 연산자를 만나면 앞에 두 수를 빼고 연산자와 계산해준다. 그리고 다시 stack에 넣어준다

👉🏻 2 + 1 = 3

3

 

4. 다시 stack에 차례대로 넣어준다. 

3

3

 

5. 위 과정을 반복한다

👉🏻 3 * 3 = 9

 

✅ ((2 + 1) * 3) = 9 이 과정이라고 생각하면 된다.

 

 

 

코드

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
  let stack = [];
  let operator = {
    '+': (a, b) => a + b,
    '-': (a, b) => a - b,
    '*': (a, b) => a * b,
    '/': (a, b) => a / b >= 0 ? Math.floor(a / b) : Math.ceil(a / b),
  };
  for (let t of tokens) {
    if (operator[t]) {
      let a = stack.pop();
      let b = stack.pop();
      stack.push(operator[t](b, a));
    } else {
      stack.push(Number(t));
    }
  }
  return stack.pop();
};