150. Evaluate Reverse Polish Notation

---

My Solution

The Key Idea for Solving This Coding Question

在運算的過程中所產生的值有可能超出 int 所能表示的範圍，所以 st 得用 long 或更大的 built-in type 來容納運算的過程中所產生的值。

C++ Code

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        int op1, op2;
        
        for (int i = 0; i < tokens.size(); ++i) {
            if (tokens[i] == "+") {
                getOperands(st, op1, op2);
                st.push(op1 + op2);
            } else if (tokens[i] == "-") {
                getOperands(st, op1, op2);
                st.push(op1 - op2);
            } else if (tokens[i] == "*") {
                getOperands(st, op1, op2);
                st.push(op1 *op2);
            } else if (tokens[i] == "/") {
                getOperands(st, op1, op2);
                st.push(op1 / op2);
            } else {
                st.push(static_cast<int>(strtol(tokens[i].c_str(), NULL, 10)));
            }
        }
        
        return st.top();
    }
    
private:
    void getOperands(stack<int> &st, int &op1, int &op2) {
        op2 = st.top();
        st.pop();
        
        op1 = st.top();
        st.pop();
        
        return;
    }
};

Time Complexity

$O(n)$

$n$ is the length of tokens.

Space Complexity

$O(n)$

$n$ is the length of tokens.

Miscellane