Evaluate Reverse Polish Notation

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

tags: stack

经典题，今天刚在数据结构书上看到。维护一个栈。当遇到数字时，入栈。当遇到运算符时，弹出两个数字，进行运算，然后将结果压入栈中。栈中最后剩的数字便是结果。

需要注意的是减法和除法数字运算的顺序，后出栈的(operand1)作被减数或被除数，先出栈(operand2)的作减数或除数。

我用了一个抛异常的技巧，如果当前字符串无法转换成数字，stoi会抛出invalid_argument异常，由处理操作符的代码进行解决。

可能是抛异常的处理机制比较耗时间，我的代码运行速度竟然排在了C代码的后面。

class Solution {
public:
    stack<int> s;
    int evalRPN(vector<string> &tokens) {
        for(vector<string>::iterator it = tokens.begin(); it != tokens.end(); it++){
            try{
                int operand = stoi(*it);
                s.push(operand);
            }
            catch(invalid_argument e){//operator
                int operand2 = s.top();
                s.pop();
                int operand1 = s.top();
                s.pop();
                int thisRe;
                if (*it == "+"){
                    thisRe = operand1 + operand2;
                }
                else if(*it == "-"){
                    thisRe = operand1 - operand2;
                }
                else if(*it == "*"){
                    thisRe = operand1 * operand2;
                }
                else{
                    thisRe = operand1 / operand2;
                }
                s.push(thisRe);
            }
        }
        int re = s.top();
        s.pop();
        return re;
    }
};