Description

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:

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

 

Solution

计算一个后缀表达式（逆波兰式），式中的操作数均为整数，运算符只含有加减乘除四种。

逆波兰式中的运算符每次向前找数个最临近的操作数作为其作用对象，因此只要将每一个数或操作符依次入栈，当入栈的是操作数时不做其他处理，当入栈的是操作符时，将操作符连同该操作符所需个数的操作数一同取出（出栈）来进行一次运算，将算得的结果再存回栈即可完成一次运算。

由于题目给定的总是合法的逆波兰式，所以最终栈中只有一个元素，即是算式的最终结果。

实现上要注意的点：

1.由于题目所给的操作符和操作数均为string形式（C++），运算需要将string转化为int，不要忽略负数的符号位‘-’在转化时的干扰。

2.将int转化为string可以利用C++的stringstream，代码可写为：

1
2
3
4
5
int val = 100;
stringstream ss;
string str;
ss<<val;
ss>>str;

 

Code

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution {
public:
    int (string str)
    {
        int ret = 0, i = 0;
        bool neg_flag = false;
        if(str[0] == '-')
        {
            neg_flag = true;
            i++;
        }
        for(; i < (int)str.length(); i++)
        {
            ret *= 10;
            ret += str[i] - '0';
        }
        if(neg_flag) return -ret;
        return ret;
    }
    int calculate(string a, string b, string oper)
    {
        int left = string2int(a);
        int right = string2int(b);
        switch(oper[0])
        {
            case '+': return left + right;
            case '-': return left - right;
            case '*': return left * right;
            case '/': return left / right;
        }
        return INT_MIN;
    }
    int evalRPN(vector<string>& tokens)
    {
        stack<string> S;
        vector<string>::iterator it = tokens.begin();
        for(; it != tokens.end(); it++)
        {
            S.push(*it);
            if(S.top().length() == 1 &&
               (S.top()[0] == '+' ||S.top()[0] == '-' || S.top()[0] == '*' || S.top()[0] == '/'))
            {
                string oper = S.top();
                S.pop();
                string b = S.top();
                S.pop();
                string a = S.top();
                S.pop();
                int val = calculate(a, b, oper);
                stringstream ss;
                string str;
                ss<<val;
                ss>>str;
                S.push(str);
            }
        }
        return string2int(S.top());
    }
};