150. Evaluate Reverse Polish Notation
Medium

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

  算法思想:看到这个题目,是求逆波兰表达式,逆波兰表达式,通俗一点就是后缀表达式,即运算符号在操作数的后方。针对这种形式的表达式,比较直观的想法就是处理两个栈,一个放操作数,一个放符号。遍历整个数组,如果是操作数,进操作数栈,如果是符号,判断操作数是否已有两个数存在且符号栈中是否有符号比当前符号运算优先
  ①若已有两个数且没有符号比当前符号优先,则弹出两个操作数进行运算后压回栈中。
  ②若操作数不足两个,则当前运算符号入符号栈。
  ③若符号栈中有比当前符号优先级高的,则先弹出进行运算后,再将当前符号及结果分别压到各自栈中。
遍历直到数组结尾,操作数栈中第一个值即为运算结果。以上是个人比较直观的暴力解决方法,若有更方便的方法欢迎评论区留言交流,谢谢。


Javascript Solution:

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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/**
* @param {string[]} tokens
* @return {number}
*/
var evalRPN = function(tokens) {
let number = [], operate = []
for(let i=0;i < tokens.length;i++){
let temp = parseInt(tokens[i])
if(isNaN(temp) === false) number.push(temp)
//判断是否是数字,这边采用了isNaN
else{
let first = 0, second = 0
switch(tokens[i]){
case "+":
if(number.length < 2) operate.push(tokens[i])
//操作数不够两个,直接压进栈中,下同
else{
first = number.pop()
second = number.pop()
if(operate.length != 0){
let opt = operate[operate.length-1]
if(opt != "*" && opt!="/") number.push(second+first)
else {
if(opt === "*"){
number.push(second*first)
operate.pop()
operate.push(tokens[i])
}
else if(opt === "/"){
number.push(parseInt(second/first))
operate.pop()
operate.push(tokens[i])
}
}
}
else{
number.push(second+first)
}
}
break
case "-":
if(number.length < 2) operate.push(tokens[i])
else{
first = number.pop()
second = number.pop()
if(operate.length != 0){
let opt = operate[operate.length-1]
if(opt != "*" && opt!="/") number.push(second-first)
else {
if(opt === "*"){
number.push(second*first)
operate.pop()
operate.push(tokens[i])
}
else if(opt === "/"){
number.push(parseInt(second/first))
operate.pop()
operate.push(tokens[i])
}
}
}
else{
number.push(second-first)
}
}
break
/** + -两种情况需要判断当前符号栈中是否有符号且是否是* /
若是,则将乘除取出并进行运算后,将结果和当前符号分别压入各自栈中
若不是,直接进行运算并将结果压入操作数栈中 **/
case "*":
if(number.length < 2) operate.push(tokens[i])
else{
first = number.pop()
second = number.pop()
number.push(parseInt(second*first))
}
break
case "/":
if(number.length < 2) operate.push(tokens[i])
else{
first = number.pop()
second = number.pop()
number.push(parseInt(second/first))
}
break
//* /仅需判断当前是否有两个操作数,若无,压运算符入栈中
若有,弹出操作数运算后压结果回栈中
default: break
}
}
}

return number[0]
};
JavaScript结果

本文标题:逆波兰表达式

文章作者:JarryChen

发布时间:2020年01月07日 - 20:12

最后更新: 2020年01月07日 21:02

原始链接: https://jarrychen.xyz/archives/93bfc68e.html

× 请我喝奶茶~
打赏二维码