150. Evaluate Reverse Polish Notation

发表于 | 分类于

每日一题 2019 - 05 - 12

题目：

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

  • Division between two integers should truncate toward zero.
  • The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

1
2
3
Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

1
2
3
Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

1
2
3
4
5
6
7
8
9
10
Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

解法：

这个题给出逆波兰式让完成后缀表达式的求值，关于逆波兰式的求值在数据结构中已经有接触过，也即使用数据结构栈就可以完成任务，思路就是遇到非运算符时候，把运算数依次存入栈中，遇到运算符依次弹出两个运算数完成运算，并把结果从新推入栈顶，但是这个题还有需要注意的地方：

  • 遇到 '-' 时候，要判断是运算符减号还是负号；
  • 如果进行除法运算过程中遇到除数是 0 的情况，直接返回 0 ；
  • 对两个数进行操作时候，存放计算结果时候需要使用 long long int 来保存计算结果防止溢出；

代码：

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
63
64
65
66
67
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<long long int> p ;
        for(int i = 0 ; i < tokens.size() ; i ++)
        {
            if(tokens[i] != "+" && tokens[i] != "/" && tokens[i] != "*")
            {
                long long int now = 0 ;
                if(tokens[i][0] == '-')
                {
                    if(tokens[i].size() > 1)
                    {
                        for(int j = 1 ; j < tokens[i].size() ; j ++ )
                        {
                            now = now * 10 + ( tokens[i][j] - '0') ;
                        }
                        now = - now ;
                        p.push(now);
                    }
                    else
                    {
                        long long int second = p.top();
                        p.pop() ;
                        long long int first = p.top();
                        p.pop() ;
                        p.push(first-second);
                        continue ;
                    }
                }
                else
                {
                    for(int j = 0 ; j < tokens[i].size() ; j ++ )
                    {
                        now = now * 10 + ( tokens[i][j] - '0') ;
                    }
                    p.push(now);
                }
                //cout << now <<  endl ;
            }
            else
            {
                long long int second = p.top();
                p.pop() ;
                long long int first = p.top();
                p.pop() ;
                if(tokens[i] == "+")
                {
                    p.push(first+second);
                }
                else if(tokens[i] == "/")
                {
                    if(second == 0)
                    {
                        return 0 ;
                    }
                    p.push(first/second);
                }
                else
                {
                    p.push(first*second);
                }
            }
        }
        return p.top() ;
    }
};
0%
undefined