# 150 - Evaluate Reverse Polish Notation

解法一 - 用 stack 記錄要被運算的數字順序

這題應該算是滿直觀的，遇到數字就放到 stack 裡，遇到 operator 就拿出 stack 最上方的兩個數字來運算，只要注意數字順序不要搞錯，先拿出來的是 operator 後面的數字就好。實作如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> stk;

        for(auto& tok: tokens) {
            if(tok != "+" && tok != "-" && tok != "*" && tok != "/") {
                stk.push(stoi(tok));
            }
            else {
                int n2 = stk.top();
                stk.pop();
                int n1 = stk.top();
                stk.pop();

                if(tok == "+")
                    stk.push(n1+n2);
                else if(tok == "-")
                    stk.push(n1-n2);
                else if(tok == "*")
                    stk.push(n1*n2);
                else if(tok == "/")
                    stk.push(n1/n2);
            }
        }

        return stk.top();
    }
};

// idea: when we meet digits, we push it to stack
// when we meet operator, we do calculations

Runtime: 12 ms, faster than 91.07% of C++ online submissions for Evaluate Reverse Polish Notation. Memory Usage: 11.4 MB, less than 93.04% of C++ online submissions for Evaluate Reverse Polish Notation.