算法训练营第二十天|150. 逆波兰表达式求值
第一部分：题目要求
给你一个字符串数组
tokens，表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。
注意：
- 有效的算符为
'+'、'-'、'*'和'/'。- 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
- 两个整数之间的除法总是向零截断。
- 表达式中不含除零运算。
- 输入是一个根据逆波兰表示法表示的算术表达式。
- 答案及所有中间计算结果可以用32 位整数表示。
本题不难，但第一次做的话，会很难想到，所以先看视频，了解思路再去做题
题目链接：https://leetcode.cn/problems/evaluate-reverse-polish-notation/视频讲解：https://www.bilibili.com/video/BV1kd4y1o7on
第二部分：解题过程
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int>st; for (int i = 0; i < tokens.size(); i++){ string cur = tokens[i]; if (cur == "+" || cur == "-" || cur == "*" || cur == "/"){ int num1 = st.top(); st.pop(); int num2 = st.top(); st.pop(); if (cur == "+") st.push(num2 + num1); else if (cur == "-") st.push(num2 - num1); else if (cur == "*") st.push(num2 * num1); else if (cur == "/") st.push(num2 / num1); } else { st.push(stoi(cur)); } } int result = st.top(); st.pop(); return result; } };
- 初始化栈：用于存储遍历过程中的数字，以及中间计算结果。
- 线性遍历表达式：
- 遇到数字：直接转换为整数压入栈，等待后续运算调用；
- 遇到运算符：触发一次运算，从栈顶连续弹出 2 个操作数（先弹出的是右操作数，后弹出的是左操作数），按运算符完成计算后，将结果重新压入栈。
- 提取最终结果：遍历完成后，栈中只会剩余一个元素，就是整个表达式的最终计算结果。
第三部分：易错点
操作数计算顺序完全搞反：栈是后进先出，先弹出的
num1是右操作数，后弹出的num2是左操作数，减法、除法必须严格按照num2 运算符 num1计算，若写反会直接得到错误结果。字符串与字符的判断错误：输入的
tokens元素是string类型，判断运算符必须用双引号""，不能用单引号'。
第四部分：解题感悟
这类基础算法题，最好的验证方式是手动用示例走一遍流程，尤其是栈的进出顺序，能快速发现逻辑漏洞，避免写完代码后 debug 找不到问题根源。
逆波兰表达式的设计思想非常巧妙：它把人类熟悉的、需要理解优先级的中缀表达式，转换成了计算机可以无脑线性执行的后缀表达式，这也是编译原理中表达式计算的核心底层逻辑，理解这个题