[LeetCode] Evaluate Reverse Polish Notation - Javascript

Evaluate Reverse Polish Notation

[역폴란드 표기법]

 

제약 조건 

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

 

Example

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

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

ex3) 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

초기 문제 접근 방식

역폴란드 표기법은 우리가 평소에 하던 연산과 조금 개념이 다르다.

후위 표기법이라고도 불리며, 평소 우리가 사용 하던 방법은 중위 표기법이다.

예로들어 아래의 표기법은 서로 같은 값을 나타낸다.

(3 + 5) * (4 + 2)  === 3 5 + 4 2 + *

이점을 고려해 해당 문제는 스택 개념을 활용해 비교적 쉽게 풀이가 가능하다.

 

temp 변수와 arr 변수를 생성해 tokens[i]의 값이 피연산자라면 arr 배열에 문자열을 정수로 변환해 push 하고,
산술연산자라면 해당 값이 어떤 산술 연산자인지 확인해 연산을 한다.
초기에는 temp 변수로 더하고 빼고 등을 연산했는데, 이렇게 하면 연산 순서를 지켜줄 수가 없다.

예로 들어 아래와 같은 input이 들어온다고 가정할 때,

["3","11","5","+","-"]

3-(11+5) 이되어 아웃풋으로 -13이 나와야 하지만,

temp 변수로 계속 저장하며 값을 계산하면 16-3 연산이 되어 +13이 나오게 된다.

그렇다고 temp - target의 순서를 target - temp로 변경해 주면 해당 테스트케이스는 통과가 되지만,
반대의 다른 테스트 케이스에서 또 실패하게 된다.

추가적으로 if 문에 "tokens[i].length !== 1" 코드를 작성 한 이유는 -11 같은 값이 들어왔을 때 이 값을 정수로 보기 위함이다.
해당 조건 없이 제어문에 들어갈 시 -11을 산술 연산자 "-"로 인식해 else 문으로 들어가는 문제가 있어 해당 코드를 작성했다.

초기 전체코드

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
   let temp = undefined;

   let target;
   let arr = [];
   const arit = /[+\-*/]/;
   
   for (let i = 0; i < tokens.length; i++) {
      if (tokens[i].length !== 1 || !arit.test(tokens[i])) {
         arr.push(parseInt(tokens[i]));
      } else {
         target = arr.pop();
         if (tokens[i] === '+') {
            temp = temp !== undefined ? temp + target : arr.pop() + target;
         } else if (tokens[i] === '-') {
            temp = temp !== undefined ? temp - target : arr.pop() - target;
         } else if (tokens[i] === '*') {
            temp = temp !== undefined ? temp * target : arr.pop() * target;
         } else if (tokens[i] === '/') {
             console.log(temp,target)
            temp = temp !== undefined ? Math.trunc(target / temp) : Math.trunc(arr.pop() / target);
         }
      }
   }
    return temp

};

 

다시 생각 해보며..

위의 방법을 해결하기 위해선 계산 한 값을 스택에 push 하는 것이다.
이렇게 하면 위의 문제를 해결할 수 있다.
["3","11","5","+","-"]

아까와 같은 예시를 볼 때,
맨 처음 더하기 연산을 하고 ex) 11+5 = 16
16의 값을 스택에 push 한다.

그 후 pop을 두 번 수행하여 맨 처음 pop 한 값과 두 번째로 pop 한 값을 변수에 저장하고

second - first로 계산해 주면 된다.

first = arr.pop()
second = arr.pop()
result = second - first
arr.push(result)

또한 더하기나 곱하기 일 땐 해당 문제를 생각해 줄 필요가 없으므로
산술 연산자 중 빼거나 나누기를 할 때만 해당 코드를 작성하면 된다.

solve 전체 코드

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function (tokens) {
   let temp = undefined;
    let result = 0
   let target;
   let arr = [];
   const arit = /[+\-*/]/;
   
    if(tokens.length === 1){
        return tokens.pop()
    }

   for (let i = 0; i < tokens.length; i++) {
      if (tokens[i].length !== 1 || !arit.test(tokens[i])) {
         arr.push(parseInt(tokens[i]));
      } else {
         if (tokens[i] === '+') {
             result = arr.pop() + arr.pop()
             arr.push(result)
         } else if (tokens[i] === '-') {
             first = arr.pop()
             second = arr.pop()
             result = second - first
             arr.push(result)
         } else if (tokens[i] === '*') {
             result = arr.pop() * arr.pop()
             arr.push(result)
         } else if (tokens[i] === '/') {
             first = arr.pop()
             second = arr.pop()
             result = Math.trunc(second / first)
             arr.push(result)
           
         }
      }

   }
    return result

};