题目链接：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

这道题的要求是计算逆波兰表达式的值。

所谓逆波兰表达式，就是两个操作数在前，操作符在后的表达式。因此，可以利用栈，遇到数字是压入栈，遇到操作符时，从栈中弹出2个数，进行运算，并将结果压入栈。最后栈中元素就是最后的结果。

时间复杂度：O(n)

空间复杂度：O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution 
{
public:
    int evalRPN(vector<string> &tokens) 
    {
        stack<int> s;
        for(int i = 0; i < tokens.size(); ++ i)
        {
            if(tokens[i].size() == 1 && tokens[i][0] < '0')
            {
                int v2 = s.top(); s.pop();
                int v1 = s.top(); s.pop();
                switch(tokens[i][0])
                {
                case '+' : s.push(v1 + v2); break;
                case '-' : s.push(v1 - v2); break;
                case '*' : s.push(v1 * v2); break;
                case '/' : s.push(v1 / v2); break;
                }
            }
            else
                s.push(atoi(tokens[i].c_str()));
        }
        return s.top();
    }
};