๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์ฝ”ํ…Œ

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/