算法打卡第二十天 / 150.逆波兰表达式求值

一、今日学习任务第20天 栈的经典应用核心要求实现逆波兰表达式的求值操作掌握栈这一核心解法理解栈在表达式计算中的底层逻辑。前置建议回顾栈的基础数据结构与进出栈操作理解逆波兰表达式后缀表达式的计算规则这是解决本题的逻辑基础。题目链接https://leetcode.cn/problems/evaluate-reverse-polish-notation/视频链接https://www.bilibili.com/video/BV1kd4y1o7on二、初次解题思路和思考刚看到这道题第一反应是直接遍历字符串遇到运算符就往前找两个数进行计算但这种方式无法处理运算符的优先级和嵌套计算很容易出错直接排除。再看题目场景逆波兰表达式的核心规则是“遇到运算符取前面最近的两个数进行计算”这种“回溯最近元素并计算”的需求栈结构是最优解。核心逻辑是遍历表达式时遇到数字就压入栈中遇到运算符时弹出栈顶的两个数字先弹出的作为右操作数后弹出的作为左操作数进行运算后将结果再压入栈中最终栈中剩余的元素就是表达式的结果。时间复杂度为O(n)空间复杂度为O(n)使用栈存储数字。三、写代码时遇到的问题栈在表达式求值问题中最容易出错的地方是操作数顺序和边界条件核心易错点如下1. 操作数弹出顺序先弹出的是左操作数还是右操作数必须注意栈是“先进后出”的遇到运算符时先弹出的是右操作数后弹出的是左操作数如果顺序颠倒减法和除法会出现结果错误。2. 除法的取整规则向零取整还是向负无穷取整题目要求除法向零截断例如6 / -4的结果是-1而不是-2。直接使用C的整数除法/即可满足向零取整的规则但要注意除数为0的情况题目保证输入合法。3. 栈空判断遇到运算符时栈是否有足够的元素题目保证输入的逆波兰表达式是合法的因此遇到运算符时栈中一定有至少两个元素但自己写代码时要理解这个逻辑避免在非法输入下出现栈空访问错误。4. 数字字符串转换如何区分数字和运算符遍历到的字符串如果长度大于1或长度为1但不是、-、*、/则为数字长度为1且是运算符的才进行运算处理。四、代码实现栈解法测试示例输入tokens [2,1,,3,*]输出9对应表达式(2 1) * 3 9输入tokens [4,13,5,/,]输出6对应表达式4 (13 / 5) 6五、今日收获1. 逆波兰表达式求值的核心是利用栈存储操作数遇到运算符则弹出最近的两个数计算是栈结构在表达式处理中的经典应用。2. 栈的“先进后出”特性天然适配逆波兰表达式的计算规则无需额外的优先级处理遍历一次即可完成求值时间复杂度为O(n)。3. 核心避坑点是操作数的弹出顺序减法和除法必须保证“后弹出的是左操作数先弹出的是右操作数”否则结果会出错。4. 这类表达式计算问题是后续解决“中缀表达式转后缀表达式”“带括号的表达式求值”等复杂问题的基础掌握栈的核心逻辑能快速推导同类题目的解法。