算法训练营第二十天｜逆波兰表达式求值

一、做题第一想法

逆波兰表达式就是后缀表达式，第一眼看不懂运算顺序。
学完思路发现：栈的经典应用题，遇到数字入栈，遇到运算符就弹出两个数计算，结果再压回栈里，特别巧妙。

二、核心思路

1. 遍历每一个字符串 tokens

2. 遇到数字：转整型，压入栈

3. 遇到运算符 + - * /：

◦ 先弹出右操作数

◦ 再弹出左操作数

◦ 按运算符计算，结果重新入栈

4. 最后栈里只剩一个数，就是最终答案

四、易错坑点

1. 弹出顺序搞反：先弹左数后弹右数，计算结果错误

2. 整数除法向零取整，不能直接用普通整除忽略正负

3. 数值溢出，要用 long long 防止越界

4. 把运算符当成数字处理，逻辑错乱

五、今日收获

1. 掌握逆波兰表达式栈固定解法模板

2. 理解栈适合后缀表达式运算的底层原因

3. 熟悉数字、字符串、类型转换用法

4. 栈三大经典题型：括号匹配、相邻消除、逆波兰表达式 全部掌握