各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 55 天。今天力扣上的每日一题是「150. 逆波兰表达式求值」。

解题思路

逆波兰表达式，也叫做后缀表达式。

我们平时见到的运算表达式是中缀表达式，即 “操作数① 运算符② 操作数③” 的顺序，运算符在两个操作数中间。
但是后缀表达式是”操作数① 操作数③ 运算符②” 的顺序，运算符在两个操作数之后。

各种表达式没有本质区别，他们其实是同一个语法树，只是遍历方式不同而得到的不同式子；是一个事物的一体多面，只不过是从不同角度观察罢了。

  • 中缀表达式是其对应的语法树的中序遍历；
    - 后缀表达式是其对应的语法树的后序遍历；
    - 前缀表达式是其对应的语法树的前序遍历；

下图中左边是中缀表达式，中间是其对应的语法树，右边是语法树转成的后缀表达式。

【每日一题】150. 逆波兰表达式求值 - 图1

为什么计算机要使用后缀表达式呢？是因为对于计算机而言，后缀表达式求值更简单。

对逆波兰表达式求值的过程是：

  1. 如果遇到数字就进栈；
    2. 如果遇到操作符，就从栈顶弹出两个数字分别为 num2（栈顶）、num1（栈中的第二个元素）；计算 num1 运算 num2 .

逆波兰表达式是的代码实现很方便，用一个栈就能解决。

躲坑

但是本题对 Python 而言，有坑。

坑一

Python 中没有一个函数可以判断一个字符串是否为合理的整数（包括正、负数）。str.isdigit() 可以判断正数，但是无法判断负数。

解决方法 1

使用 int() 函数，并做 try-except 。

  • 如果是整数，那么可以用 int() 转成数字；
  • 如果是运算符，那么 int() 会报错，从而进入 except 中。
    1. try:
    2.   stack.append(int(token))
    3. except:
    4.   pass # 处理运算符

解决方法 2

整数字符串的最后一位肯定是数字，也可以以此来区分数字 和 运算符。

  1. if token[-1].isdigit():
  2.     stack.append(int(token))
  3. else:
  4.     pass # 处理运算符

坑二

python 的整数除法是向下取整，而不是向零取整。

  • python2 的除法 “/“ 是整数除法， "-3 / 2 = -2" ；
  • python3 的地板除 “//“ 是整数除法， "-3 // 2 = -2" ；
  • python3 的除法 “/“ 是浮点除法， "-3 / 2 = -1.5" ；

而 C++/Java 中的整数除法是向零取整。

  • C++/Java 中 "-3 / 2 = -1" .

本题的题意（一般情况）都是要求向零取整的。

解决方法 1

对 Python 的整数除法问题，可以用 int(num1 / float(num2)) 来做，即先用浮点数除法，然后取整。

  • 无论如何，浮点数除法都会得到一个浮点数，比如 "-3 / 2.0 = 1.5" ；
    - 此时再取整，就会得到整数部分，即 float(-1.5) = -1 。

解决方法 2

使用库函数 operator.truediv(num1, num2) ，调用该函数等价于 num1 / float(num2)。

代码

注意，面试时不可以使用 eval 函数求两个数的运算结果。因为本题是个考察计算的题目，使用 eval 相当于作弊。

  1. class Solution(object):
  2.     def evalRPN(self, tokens):
  3.         stack = []
  4.         for token in tokens:
  5.             try:
  6.                 stack.append(int(token))
  7.             except:
  8.                 num2 = stack.pop()
  9.                 num1 = stack.pop()
  10.                 stack.append(self.evaluate(num1, num2, token))
  11.         return stack[0]
  13.     def evaluate(self, num1, num2, op):
  14.         if op == "+":
  15.             return num1 + num2
  16.         elif op == "-":
  17.             return num1 - num2
  18.         elif op == "*":
  19.             return num1 * num2
  20.         elif op == "/":
  21.             return int(num1 / float(num2))
  • 时间复杂度：$O(N)$
  • 空间复杂度：$O(N)$

刷题心得

本题是逆波兰表达式求值，但是如何把中缀表达式转成逆波兰表达式？

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！