题目 150 逆波兰表达式
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
注意 两个整数之间的除法只保留整数部分。
可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入：tokens = [“2″,”1″,”+”,”3″,”“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
示例 2：
输入：tokens = [“4″,”13″,”5″,”/”,”+”]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
示例 3：
输入：tokens = [“10″,”6″,”9″,”3″,”+”,”-11″,”“,”/”,”*”,”17″,”+”,”5″,”+”]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
思路
-
什么是逆波兰表达式：
逆波兰式（或逆波兰记法），也叫后缀表达式（将运算符写在操作数之后）。
如：我们平时写a+b，这是中缀表达式，写成后缀表达式就是：ab+ -
用处：波兰式在计算机看来却是比较简单易懂的结构。因为计算机普遍采用的内存结构是栈式结构，它执行先进后出的顺序。
-
思路：用栈的结构解决：循环字符串，如果碰到数字就入栈，乳沟碰到运算符就出栈两个元素进行运算（注意两个数字的前后顺序），结果再入栈。
代码
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for i in tokens:
if i == "+" or i == "-" or i == "*" or i == "/":
num1 = stack.pop()
num2 = stack.pop()
if i == "+":
stack.append(int(num2)+int(num1))
if i == "-":
stack.append(int(num2)-int(num1))
if i == "*":
stack.append(int(num2)*int(num1))
if i == "/":
# 特别注意，这里就是用地板除法，结果再int一下，不然会有6//-132=-1的情况，但是题目实际是要求等于0的。
stack.append(int(int(num2)/int(num1)))
else:
stack.append(int(i))
return stack[0]
留有疑问，希望看到的博友能解答一下
为什么 6/-132=-1？可能时间长了，最基础的知识都忘掉了。。。哎
原文地址：http://www.cnblogs.com/edkong/p/16834363.html
