栈和队列——2.逆波兰表达式求值
力扣题目链接
根据 逆波兰表示法，求表达式的值。有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例：
输入：["2", "1", "+", "3", " * "]
输出：9题目是什么意思呢？就是将运算符号放在两个数的后面，示例中2,1，+就代表2+1=3，然后3,3，*就代表3*3=9。同时说明了整数除法只保留整数部分，那就代表了不会有小数出现。
用栈的思维理解就是，列表一个数一个数进栈，当发现当前要进栈的是运算符，那就从栈中吐出两个数用运算符进行运算，运算得到的数再进栈，一直重复直到最后得到值。
完整代码如下：
from operator import add, sub, muldef div(x, y):# 使用整数除法的向零取整方式return int(x / y) if x * y > 0 else -(abs(x) // abs(y))class Solution(object):op_map = {'+': add, '-': sub, '*': mul, '/': div}def evalRPN(self, tokens: List[str]) -> int:stack = []for token in tokens:if token not in {'+', '-', '*', '/'}:stack.append(int(token))else:op2 = stack.pop()op1 = stack.pop()stack.append(self.op_map[token](op1, op2)) # 第一个出来的在运算符后面return stack.pop()首先，先定义一个函数，这个函数的作用是整除向零取整。有些同学会问，整数除法取整不是用//就可以了吗，为什么要特意定义一个函数？这是因为Python中的整除返回值向下取整不是像C语言中那样向0取整。这在x和y都大于0的时候并没有关系，但当y小于0时呢？例如6//-132到底取0还是取-1，正常运算时应该取0，但python中会默认向下取整取-1。所以这里要重新定义一个考虑所有情况的整数除法取整函数。在函数中还有一个问题，int（x/y）是取整数，那我可不可以直接用熟悉的x//y呢，当然可以，因为这个前提条件已经注明了使x*y>0。
接着定义了一个字典，是关于运算符和其对应的函数，这里为什么要用函数表示，而不能直接用python中运算符本身的含义呢？请接着往下看。
定义一个空栈，在字符串循环中，如果字符不是运算符中的某一个，那就是数字，让其以整数形式进入栈。在字符是运算符的情况下，推出栈中的两个元素op2（后进的数）和op1（先进的数），然后将self.op_map[token](op1, op2)压入栈，op_map[token]找到运算符对应的运算函数，例如“+”对应add，则self.add(op1, op2)。这里也可以解释上面提出为什么要用函数表示的问题，你如果用函数表示，这里的代码不好编写。
一直运算，直到最后栈中只存在一个值，return到推出栈的那个值。