[LeetCode] Evaluate Reverse Polish Notation

Problem Statement (link):

Evaluate the value of an arithmetic expression in Reverse Polish Notation.
Valid operators are +, -, *, /. Each operand may be an integer or another expression.
Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

Analysis:
Read the two examples and the wiki link given in the problem carefully, and you'll find the problem is straight-forward - we could use stack to solve it.

For instance, in the second example above, we keep pushing element into the stack once we meet the operator "/", we then pop out the top two elements in the stack, calculate the result, and push the result back to stack, and so on.

In general, the algorithm goes like this:
- If the entry is not operator, we push it into stack
- Otherwise, we pop out top 2 element and calculate the result, and push the result back to stack.

The time and space complexity is O(n).

Code:

class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        if (tokens.empty())
            return 0;
        stack<int> st;
        for(int i=0; i<tokens.size(); i++) {
            if (tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/") {
                int n1=st.top();
                st.pop();
                int n2=st.top();
                st.pop();
                int res=evaluate(n2, n1, tokens[i].c_str());
                st.push(res);
            }
            else {
                st.push(atoi(tokens[i].c_str()));
            }
        }
        return st.top();
    }
    int evaluate(int n1, int n2, const char* op) {
        int res;
        switch (*op) {
            case '+':
                res=n1+n2;
                break;
            case '-':
                res=n1-n2;
                break;
            case '*':
                res=n1*n2;
                break;
            case '/':
                res=n1/n2;
                break;
            default:
                break;
        }
        return res;
    }
};