# 【LeetCode】 150. Evaluate Reverse Polish Notation

## Description
> 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.

> 計算用反向波蘭表示法表示的數學式的值。
> 合法的運算子有 `+` `-` `*` `/`，每個運算元可能是一個整數或是另一個表達式。
> 注意兩個整數的除法應該要整除。
> 保證給定的表達式一定合法，這表示一定可以計算出結果且不會有除以零的操作。

## Example:

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

## Solution

* 基本上就是後敘表達的題目，沒學過的可以參考[這邊](https://hackmd.io/@Zero871015/SyHco0i2m?type=view)
* 簡單來說就是用一個 Stack 把"數字"存起來
* 如果遇到運算，就把 Stack 最後兩個拿出來做計算，算完放回 Stack
* 最後每個 token 都跑完之後，留在 Stack 的元素就會是答案了
* 好像可以寫得乾淨一點，不過算了
* 要注意 temp1 和 temp2 在 - 和 / 會有順序的差異。

### Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        vector<int> numStack;
        int temp1, temp2;
        for(int i = 0; i < tokens.size(); i++)
        {
            if(tokens[i] == "+")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp1 + temp2);
            }
            else if(tokens[i] == "-")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp2 - temp1);
            }
            else if(tokens[i] == "*")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp1 * temp2);
            }
            else if(tokens[i] == "/")
            {
                temp1 = numStack.back();
                numStack.pop_back();
                temp2 = numStack.back();
                numStack.pop_back();
                numStack.push_back(temp2 / temp1);
            }
            else
                numStack.push_back(stoi(tokens[i]));
        }
        return numStack.back();
    }
};

###### tags: `LeetCode` `C++`