LeetCode Top Interview 150 - 150. Evaluate Reverse Polish Notation

🤔 문제 이해

tokens에 주어진 배열을 stack을 이용하여 계산하라 (예시를 보면서 이해할수 있었슴)

🤔 EX

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

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

data 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

🤔 의사 코드 

let stack =[] ----> stack으로 사용할 배열 선언

for(const element of tokens){
	if(숫자인지 확인){
    	stack.push(Number(element))
        }else{
        let num1=stack.pop()
        let num2 = stack.pop()
        
        switch(element){
        case "+":
        stack.push(num1+num2)
        break;
        ..... 생략......
        }
     }
     return stack.pop()

🤔 해결한 코드 : O(n)

의사 코드 그대로 구현하였더니 나누기할 때에 문제가 생겼고 console.log()를 찍어 계산순서가 num1과 num2를 계산 위치를 바꿔 줘야해서 수정하니 해결할 수 있었다.

var evalRPN = function(tokens) {
    let stack = []

    for (const element of tokens) {
        if(!isNaN(element)){
              stack.push(Number(element))

        }else{
            const num1 = stack.pop()
            const num2 = stack.pop()

        switch(element) {
            case "+":  
                stack.push(num2+num1)
            break;

            case "-": 
                stack.push(num2-num1)
            break;

            case "/": 
                stack.push(Math.trunc(num2/num1))
            break;

            case "*":
                stack.push(num2*num1)
            break;

        }   

    }
        }
    return stack.pop()
}

 

🤔 다른 풀이방법

다들 비슷하게 풀었다. switch case가 아닌 if else도 있었구 기초적인 로직은 잘 구현한 것 같다.

 

https://leetcode.com/problems/evaluate-reverse-polish-notation/