每日一题 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  {
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);
}

}
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() ;
}
};