[LeetCode] 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

• 解题思路
  用一个栈来存储数字，从第一个数开始遍历vector<string> tokens，直到最后一个元素。如果遍历到的元素为操作符，则从栈中弹出两个操作数，将其与操作符进行运算，并将运算结果入栈。遍历完成后，栈中的元素即为所求。
• 实现代码

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/9 15:07
    *  @Status   : Accepted
    *  @Runtime  : 20 ms
******************************************************************/
class Solution {
public:
    int evalRPN(vector<string> &tokens) {
        stack<int> nums;
        int i = 0;
        int n1, n2;
        while (i < tokens.size())
        {
            if (isToken(tokens[i]))
            {
                n1 = nums.top();
                nums.pop();
                n2 = nums.top();
                nums.pop();
                //特别注意：第二次弹出数字n2为第一个操作数
                nums.push(calc(n2,n1,tokens[i]));
                i++;
            }
            else
            {
                nums.push(strToInt(tokens[i]));
                i++;
            }
        }

        return nums.top();
    }

    int calc(int n1, int n2, string op)
    {
        char ch = op[0];
        switch(ch)
        {
        case '+':
            return n1 + n2;
            break;
        case '-':
            return n1 - n2;
            break;
        case '*':
            return n1 * n2;
            break;
        case '/':
            return n1 / n2;
            break;
        }
    }

    bool isToken(string str)
    {
        if (str.size() == 1 && (str[0] < '0' || str[0] > '9'))
        {
            return true;
        }
        return false;
    }

    int strToInt(string str)
    {
        int sum = 0;
        bool flag = false;
        int i = 0;
        while (str[i] == ' ')
        {
            i++;
        }

        if (str[i] == '-')
        {
            flag = true;
            i++;
        }
        else if (str[i] == '+')
        {
            i++;
        }

        while (i < str.size())
        {
            sum = sum * 10 + str[i++] - '0';
        }

        if (flag)
        {
            return -sum;
        }
        return sum;
    }
};

例如，表达式“8 – ((1 + 2) * 2)”用RPN表示为:8 1 2 + 2 * –

算法结束后，栈中只有一个元素，它就是RPN表达式的结果，本例子中结果为2。