友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
150. 逆波兰表达式求值
给你一个字符串数组 tokens，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
注意：
-
有效的算符为
+、-、*和/。 -
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
-
两个整数之间的除法总是 向零截断 。
-
表达式中不含除零运算。
-
输入是一个根据逆波兰表示法表示的算术表达式。
-
答案及所有中间计算结果可以用 32 位 整数表示。
示例 1：
输入：tokens = ["2","1","+","3","*"] 输出：9 解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = ["4","13","5","/","+"] 输出：6 解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"] 输出：22 解释：该算式转化为常见的中缀算术表达式为： ((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
提示：
-
1 <= tokens.length <= 104 -
tokens[i]是一个算符（`、`-`、`*` 或 `/`），或是在范围 `[-200, 200]+内的一个整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
-
平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 -
该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
-
去掉括号后表达式无歧义，上式即便写成 `+1 2 + 3 4 + * +`也可以依据次序计算出正确结果。
-
适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中
思路分析
其实这只是一个栈操作。遇到数字就入栈，遇到运算符号就将栈顶元素出栈，计算完成后再入栈。
-
一刷
-
二刷
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
/**
* Runtime: 4 ms, faster than 97.32% of Java online submissions for Evaluate Reverse Polish Notation.
*
* Memory Usage: 41.1 MB, less than 6.00% of Java online submissions for Evaluate Reverse Polish Notation.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-26 16:01
*/
public int evalRPN(String[] tokens) {
if (Objects.isNull(tokens) || tokens.length == 0) {
return 0;
}
Deque<Integer> stack = new LinkedList<>();
Set<String> operators = new HashSet<>(Arrays.asList("+", "-", "*", "/"));
for (String token : tokens) {
if (operators.contains(token)) {
Integer v1 = stack.pop();
Integer v2 = stack.pop();
if ("+".equals(token)) {
stack.push(v1 + v2);
continue;
}
if ("-".equals(token)) {
stack.push(v2 - v1);
continue;
}
if ("*".equals(token)) {
stack.push(v1 * v2);
continue;
}
if ("/".equals(token)) {
stack.push(v2 / v1);
continue;
}
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2025-06-08 22:16:19
*/
public int evalRPN(String[] tokens) {
Deque<Integer> stack = new ArrayDeque<>();
for (String token : tokens) {
switch (token) {
case "+":
stack.push(stack.pop() + stack.pop());
break;
case "-":
Integer b = stack.pop();
Integer a = stack.pop();
stack.push(a - b);
break;
case "*":
stack.push(stack.pop() * stack.pop());
break;
case "/":
Integer n = stack.pop();
Integer m = stack.pop();
stack.push(m / n);
break;
default:
stack.push(Integer.parseInt(token));
}
}
return stack.peek();
}