---
tags: leetcode
---

# [150. Evaluate Reverse Polish Notation](https://leetcode.com/problems/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
<!--
# Test Cases

["2","1","+","3","*"]

["4","13","5","/","+"]

["10","6","9","3","+","-11","*","/","*","17","+","5","+"]

["4","3","-"]

* Runtime Error

["-128","-128","*","-128","*","-128","*","8","*","-1","*"]

-->