## Question

>[Leetcode.150 Evaluate Reverse Polish Notation
](https://leetcode.com/problems/evaluate-reverse-polish-notation/description/)

<br>

:::info
:::spoiler *Optimal Space & Time Complexity*
<br>

- Time complexity: O()
- Space complexity: O()

:::

<br>

## Thoughts & Solutions

### YC
- push the number into the stack
:::spoiler Code

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const numStack = [];
    const operators = {
        '+': (a, b) => a + b,
        '-': (a, b) => a - b,
        '*': (a, b) => a * b,
        '/': (a, b) => Math.trunc(a / b),
    };
    for(t of tokens){
        if(t in operators){
            const back = numStack.pop();
            const front = numStack.pop();
            numStack.push(operators[t](front, back));
        }else{
            numStack.push(Number(t));
        }
    }
    return numStack.pop()   
};

:::

<hr/>

### Sol
:::spoiler Code

/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    const operators = ['+','-','*','/']
    const stack = [];
    for (let i= 0; i< tokens.length ;i++ )  {
        if(!operators.includes(tokens[i])){
            stack.push(+tokens[i])
            continue;
        }
        const operand2 = stack.pop();
        const operand1 = stack.pop();
        switch(tokens[i]){
            case '+':
                stack.push(operand1 + operand2);
                break;
            case '-':
                stack.push(operand1 - operand2);
                break;
            case '*':
                stack.push(operand1 * operand2);
                break;
            case '/':
                stack.push(Math.trunc(operand1 / operand2));
                break;
        }
    }
    return stack[0];
};

:::

<hr/>

### 東

:::spoiler Code

var evalRPN = function(tokens) {
    const stack = [];
    
    for(let i =0; i < tokens.length; i++) {
	    const currChar = tokens[i];
        if(isNaN(+currChar)) {
            const secondChar = stack.pop();
            const firstChar = stack.pop();

            switch(currChar) {
                case “+”: 
                    stack.push(firstChar + secondChar);
                    break;
                case “-”: 
                    stack.push(firstChar - secondChar);
                    break;
                case “*”: 
                    stack.push(firstChar * secondChar);
                    break;
                case “/”:
                    stack.push(Math.trunc(firstChar / secondChar));
            }
	    } else {
	     stack.push(+tokens[i]);
        }
    }
	return stack[0];
}

:::

<hr/>

### Jessie
:::spoiler MEMO
- 先理解 Reverse Polish Notation 是啥
- 維基百科的解釋
- 逆波蘭記法中，運算子(符號)置於運算元(數字)的後面。
例如表達「三加四」時，寫作「3 4 + 」，而不是「3 + 4」。
如果有多個運算子，運算子置於第二個運算元的後面，所以常規中綴記法的「3 - 4 + 5」在逆波蘭記法中寫作「3 4 - 5 + 」：先3減去4，再加上5。
- 答案需求
- 無條件捨去小數
- return 最終計算結果數字即可
- 實作方向
1. 用一個空array `stack` 依序存入遇到的數字
2. 遇到符號的時候就丟eval()計算
- 取出前兩個數字(排序不動)與符號計算
- 計算完的結果無條件捨去小數位
3. 將結果存回stack中接續下一個token走1-3這個模式
:::

graph TD;
subgraph INPUT
tokens("tokens = ['3', '4', '-', '5', '+']")
end

subgraph Step1
tokens1("tokens = ['3', '4', '-']")
stack1("stack = [3, 4]")
ans1(ans = 3 - 4)
	subgraph After Calculation
	ans1AfterCal(ans = -1)
	stack1AfterCal("stack = [-1]")
	end
end

subgraph Step2
tokens2("tokens = ['5', '+']")
stack2("stack = [-1, 5]")
ans2(ans = -1 + 5)
	subgraph After Calculation
	ans2AfterCal(ans = 4)
	stack2AfterCal("stack = [4]")
	end
end

INPUT --> Step1 --> Step2;

:::spoiler Code

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

  tokens.forEach((v, i) => {
    console.log({ i, ans, v, stack });

    //  Save number into stack
    if (isNumber(v)) return stack.push(+v);

    //  Handle symbol
    let secondNum = stack.pop();
    let firstNum = stack.pop();

    //  It's important to add () to secondNum because of the negative will cause the formula cal error
    let formula = `${firstNum}${v}(${secondNum})`;
    ans = calculateAndRoundDown(formula);
    stack.push(ans);
  });

  return tokens.length === 1 ? stack[0] : ans;
};

function isNumber(string) {
  return isNaN(+string) ? false : true;
}

function calculateAndRoundDown(formula) {
  return parseInt(eval(formula));
}

:::

<hr/>

### 皮皮

:::spoiler Code

:::
<br>

## Live Coding

:::spoiler (name)

// write your code here

:::