请用 Python 手写一个函数,对给定的逆波兰表达式(后缀表达式)进行求值,在实现过程中不得调用 Python 内置的求值函数。
考察说明
考查对栈数据结构在表达式求值中的应用,以及手写算法、处理边界情况的能力。
回答思路
- 【回答框架 1】逆波兰表达式求值的核心是使用栈:从左到右扫描每个 token,遇到数字则压栈,遇到运算符则弹出栈顶两个操作数进行计算,将结果压回栈中。注意减法和除法要区分操作数顺序:先弹出的是右操作数,后弹出的是左操作数。
- 【回答框架 2】本题要求不能使用内置求值函数,所以需要用语法实现数字转换,例如用 float() 或 int() 将 token 转为数值,但要注意 Python 的 int() 本身是内置函数,不过这里限制的是不能使用 eval 等直接对表达式求值的函数,而类型转换是允许的。
- 【回答框架 3】对于除法,需要明确是整数除法还是浮点除法。若题中表达式为整数运算,Python 的 / 返回浮点数,而 // 是向下取整,与通常的整数除法截断不同,因此需要根据题意实现:若要求整数结果,可用 int(a / b) 或自定义截断除法。
- 【回答框架 4】算法复杂度:扫描一次表达式,每个 token 进出栈一次,时间复杂度 O(n),空间复杂度 O(n)(栈的最大深度)。
- 【回答框架 5】边界情况:输入的表达式可能为空、只有一个操作数、除数为零、token 数量不足等,需要在实现中处理,但若题目未明确要求,可假定输入合法并做必要的防御。
- 【关键点 1】使用栈保存操作数,扫描 token 序列。
- 【关键点 2】运算符处理时注意操作数顺序(左操作数在栈中先压入,弹出时先弹出右操作数)。
- 【关键点 3】明确除法语义:整数除法与浮点数除法的处理方式。
- 【关键点 4】不能使用 eval 或类似直接求值的内置函数,但允许类型转换。
- 【关键点 5】时间 O(n),空间 O(n)。
- 【易错点 1】混淆操作数顺序导致减法和除法结果错误。
- 【易错点 2】使用 // 进行整数除法,其向下取整不符合通常的截断语义。
- 【易错点 3】输入包含非法 token 或表达式不合法时,未做处理或崩溃。