中文题目
根据 逆波兰表示法，求该后缀表达式的计算结果。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 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 <= 104tokens[i]要么是一个算符（"+"、"-"、"*"或"/"），要么是一个在范围[-200, 200]内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如
( 1 + 2 ) * ( 3 + 4 )。 - 该算式的逆波兰表达式写法为
( ( 1 2 + ) ( 3 4 + ) * )。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成
1 2 + 3 4 + *也可以依据次序计算出正确结果。 - 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
注意：本题与主站 150 题相同： https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
通过代码
高赞题解
栈的介绍
栈(stack) 本身是一种简单、常用的数据结构，它常常用来和队列进行比较。
- 队列： 先入先出
- 栈： 后入先出
栈的所有操作都发生在栈顶，其实就三个操作，入栈(压栈)、出栈(弹栈)、获取栈顶元素。
Python & Java 中的栈
Java中存在Stack的数据结构，但Python是没有栈的，它们的实现与操作方式如下：
| 操作 | Java | Python | 说明 |
|---|---|---|---|
| 初始化 | Stack |
stack = [] | |
| 入栈 | stack.push(1); | stack.append(1) | |
| 出栈 | stack.pop(); | stack.pop() | 为空时报错 |
| 获取栈顶元素 | stack.peek(); | stack[-1] | 为空时报错 |
栈的操作就是这几个，是不是很简单，要不直接下一章？too young，too simple！
栈的操作是简单的，但是栈在算法中的应用确实变化多端….有些题目打眼一看就是栈操作，比如 括号匹配。但更多的题目并不是能直接看出来通过栈去解决的。比如单调栈等类型的题目，真的是新手劝退神器….
但饭要一口一口吃，让我们先来看一道简单的括号匹配问题，熟悉下栈的操作吧。
剑指OfferII036.后缀表达式
https://leetcode-cn.com/problems/8Zf90G/solution/shua-chuan-jian-zhi-offer-day10-zi-fu-ch-c9f1/
难度：中等
题目：
根据 逆波兰表示法，求表达式的值。
有效的算符包括+、-、*、/。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
- 整数除法只保留整数部分。
- 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
提示：
- 1 <= tokens.length <= 10 ^ 4
- tokens[i] 要么是一个算符（”+”、”-“、”*” 或 “/“），要么是一个在范围 [-200, 200] 内的整数
逆波兰表达式：
逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。
- 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
- 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
逆波兰表达式主要有以下两个优点：
- 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
- 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
示例：
示例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分析
- 根据题目所知，输入的逆波兰表达式都是有效的，所以无需考虑特殊的场景。
- 既然是一道栈的题目，肯定要先创建一个stack，然后依次将元素入栈，但什么时候出栈呢？
- 后缀表达式是指算符写在后面，即当我们遇到操作符时，需要将操作符紧邻的前两项拿出来进行计算
- 在第3步计算完成后，还需要将结果重新加入栈中
- 最终将计算结果返回即可
解题：
Python:
class Solution:
def evalRPN(self, tokens):
stack = []
calc = {'+': lambda x, y: x + y,
'-': lambda x, y: x - y,
'*': lambda x, y: x * y,
'/': lambda x, y: int(x / y), }
for i in tokens:
if i in calc:
num2, num1 = stack.pop(), stack.pop()
stack.append(calc[i](num1, num2))
else:
stack.append(int(i))
return stack[0]Java:
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();
for (String c : tokens) {
switch (c) {
case "+":
case "-":
case "*":
case "/":
int num2 = stack.pop();
int num1 = stack.pop();
stack.push(calc(num1, num2, c));
break;
default:
stack.push(Integer.parseInt(c));
}
}
return stack.pop();
}
private int calc(int a, int b, String op) {
switch (op) {
case "+":
return a + b;
case "-":
return a - b;
case "*":
return a * b;
default:
return a / b;
}
}欢迎关注我的公众号: 清风Python，带你每日学习Python算法刷题的同时，了解更多python小知识。
有喜欢力扣刷题的小伙伴可以加我微信（King_Uranus）互相鼓励，共同进步，一起玩转超级码力！
我的个人博客：https://qingfengpython.cn
力扣解题合集：https://github.com/BreezePython/AlgorithmMarkdown
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 4383 | 7750 | 56.6% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
