[Easy] 150. Evaluate Reverse Polish Notation

문제

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, and /. Each operand may be an integer or another expression.

Note that division between two integers should truncate toward zero.

It is guaranteed that the given RPN expression is always valid. That means the expression would always evaluate to a result, and there will not be any division by zero operation.

 

역폴란드 표기법에서 산술 식의 값을 평가합니다.
유효한 연산자는 +, -, * 및 /입니다. 각 피연산자는 정수 또는 다른 식일 수 있다.
두 정수 사이의 나눗셈은 0을 향해 잘려야 한다.
지정된 RPN 식은 항상 유효합니다. 즉, 식은 항상 결과에 따라 평가되며 0 연산에 의한 분할이 발생하지 않습니다.

 

예시

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].

 

해결 과정

stack을 이용하여 문제를 해결하였다.

• stack으로 사용할 변수를 선언한다.
• for문으로 tokens을 순회한다.
  • 이때 tokens[i]가 연산자라면 stack.pop()을 통해 숫자 2개를 꺼낸다. +를 통해 형 변환한다.
  • 연산자마다 값을 계산해서 result에 할당한다.
  • 계산이 끝나면 stack에 result 값을 push 한다. result값에 소수가 들어가지 않게 정수로 형 변환한다.
• 만약 tokens[i]가 연산자가 아니라면 stack에 push한다.
• tokens의 순회가 끝나고 stack에 남은 result 값을 반환한다. 

해결 코드

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    let stack = []
    
    for(let i = 0 ; i < tokens.length ; i++){
        if(
            tokens[i] === '+' ||
            tokens[i] === '-' ||
            tokens[i] === '*' ||
            tokens[i] === '/'          
          ){
            let num2 = +stack.pop()
            let num1 = +stack.pop()
            let result = 0
            
            if(tokens[i] === '+'){
                result = num1 + num2     
            }else if(tokens[i] === '-'){
                result = num1 - num2    
            }else if(tokens[i] === '*'){
                result = num1 * num2    
            }else if(tokens[i] === '/'){
                result = num1 / num2    
            }
            
            stack.push(parseInt(result))
        }else{
            stack.push(tokens[i])
        }
    }
    
    return stack[0]
};