共计 2955 个字符，预计需要花费 8 分钟才能阅读完成。
零: 提出问题
如果须要你将两个已知的数字相加或者相乘，用代码表达出来是不是十分的 easy。再如果给出的是相似 1+1 由一个符号两个数字组成的字符串，要求出它的后果，能够用 split() 函数宰割字符串后进行计算，也是没有多少难度。
那就再降级一步，如果这个字符串不止有两个数字和一个符号，是一个蕴含加减乘除和括号的简单算术表达式呢？比方上面的一个算术表达式:
1 + (2 - 3 * 4) / 5 + 6咱们能够应用 栈 来实现这个算术表达式的计算。创立两个栈别离寄存数字和符号，而后通过符号间的优先级关系判断是否前一个符号是否能够计算。具体方法在文章 224. 根本计算器│leetcode 曾经进行了具体的解析，本文就不再反复解析这种办法了，想要理解的小伙伴能够点击链接查看文章。
当初就请出本文的配角！
壹: 配角呈现
本文的配角叫 逆波兰表达式，也叫后缀表达式。后者这个比拟艰深的名字很明确的示意了本人的含意，意思是计算的符号在要计算的两个数字之后。
咱们罕用的算术表达式是中断表达式，计算符号在两个数字之间。在事实中根本没有间接给出一个逆波兰表达式的场景，也就意味着必须先将中断表达式转换成逆波兰表达式。
咱们应用下面的例子，能够先看看转换成逆波兰表达式是什么样子？
1 2 3 4 * - 5 / + 6 +贰: 这是怎么做到的
好奇怪的一串字符，它是怎么转化来的呢？它真的能用来计算吗？咱们先来解析一下第一个问题：
中断表达式:
1 + (2 - 3 * 4) / 5 + 6
第一步:
所有算术步骤加上括号，表明优先级
这一步去除了符号与符号间的优先级关系, 计算先后顺序按照括号进行. 如: 乘除要优先于加减
(( 1 + ( ( 2 - ( 3 * 4) ) / 5 ) ) + 6 )
第二步:
将括号内的符号挪动到被包裹的最内层的右括号之后
(( 1 ( ( 2 ( 3 4) * ) - 5 ) / ) + 6 ) +
第三步:
去掉括号
1 2 3 4 * - 5 / + 6 +看到当初，是不是还是一头雾水，所以，肯定要保持往下看! 进行下一步骤。
当初必定要讲转换到的逆波兰表达式怎么计算了，否则各位读者老爷都不耐烦的走光了。
从逆波兰表达式的左侧开始，先找到第一个符号，抽出符号前的两个数字并计算。
1. 找到符号 `*`, 进行计算 `3 * 4 = 12`, 以后表达式为 `1 2 12 - 5 / + 6 +`
2. 找到符号 `-`, 进行计算 `2 - 12 = -10`, 以后表达式为 `1 -10 5 / + 6 +`
3. 找到符号 `/`, 进行计算 `-10 / 5 = -2`, 以后表达式为 `1 -2 + 6 +`
4. 找到符号 `+`, 进行计算 `1 + -2 = -1`, 以后表达式为 `-1 6 +`
5. 找到符号 `+`, 进行计算 `-1 + 6 = 5`, 失去后果为 `5`看完示例，是不是恍然大悟了呢，将表达式转换成逆波兰表达式，能够从左到右，检索到一个符号就立即进行计算。齐全去除了括号的强制优先运算和运算符之间的优先级关系。
叁: 咱们须要一个做道题
leetcode 150 题目就是对于逆波兰表达式求值的:
150. 逆波兰表达式求值
依据 逆波兰表示法，求表达式的值。无效的运算符包含 +, -, *, /。每个运算对象能够是整数，也能够是另一个逆波兰表达式。阐明：- 整数除法只保留整数局部。- 给定逆波兰表达式总是无效的。换句话说，表达式总会得出无效数值且不存在除数为 0 的状况。示例 1：输出: ["2", "1", "+", "3", "*"]
输入: 9
解释: 该算式转化为常见的中断算术表达式为：((2 + 1) * 3) = 9想要实现逆波兰表达式的运算，还是须要引入 — 栈。将数值元素顺次退出栈中，如果遇到符号，则将栈中的最初两个数值出栈，留神先后顺序，先出栈的在计算时处于符号之后，后出栈的数值在计算时处于符号之前。计算实现后将失去的数值入栈。最初，数值栈中仅保留一个数值元素，这个就是计算结果。
class Solution:
def evalRPN(self, tokens: list[str]) -> int:
数值栈 = []
for token in tokens:
if token not in "+-*/": # 以后元素是数字
数值栈.append(int(token))
else:
数值后 = 数值栈.pop()
数值前 = 数值栈.pop()
if token == '+':
数值栈.append(数值前 + 数值后)
elif token == '-':
数值栈.append(数值前 - 数值后)
elif token == '*':
数值栈.append(数值前 * 数值后)
elif token == '/':
数值栈.append(int(数值前 / 数值后))
return 数值栈.pop()肆: 上一道题如同考查不全面
上题间接给出了逆波兰表达式，咱们只须要求解即可。那如果只给出一个一般的表达式，又须要应用逆波兰表达式进行计算。那应用代码如何去做呢?
def 中断表达式转逆波兰表达式(s):
'''假如 s 是一个仅有数字和运算符号 (蕴含括号) 的无效中断表达式'''
符号栈, 表达式队列, 上一字符 = [], [], ''
# 符号优先级(栈中最初一位与以后符号进行比拟)
符号优先级表 = {"+": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
"-": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
"*": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
"/": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
"(": {"+": '<', '-': '<', '*': '','/':'', '(': '<', ')': '='},
")": {"+": '','-':' ','*':'', '/': '','(':' ',')':' '},
}
for value in s:
if value not in '+-*/()': # 是数字
if 上一字符 not in '+-*/()': # 是间断的数字
表达式队列.append(表达式队列.pop() * 10 + int(value))
else:
表达式队列.append(int(value))
else:
while True: # 在栈中可能有多个优先级更高的符号, 须要遍历
if len(符号栈) == 0 or 符号优先级表[符号栈[-1]][value] == '<': # 以后符号优先级更高, 退出栈
符号栈.append(value)
break
elif 符号优先级表[符号栈[-1]][value] == '=': # 结束符遇到了结束符
符号栈.pop()
break
elif 符号优先级表[符号栈[-1]][value] == '>': # 栈中优先级更高, 可计算
表达式队列.append(符号栈.pop())
上一字符 = value
for 符号 in 符号栈: # 符号栈中可能会残余一个符号, 间接退出
表达式队列.append(符号栈.pop())
return 表达式队列
if __name__ == "__main__":
print(中断表达式转逆波兰表达式('1+(2-3*4)/5+6'))以上代码执行后失去的后果是:
[1, 2, 3, 4, '*', '-', 5, '/', '+', 6, '+']是不是转换成了和 leetcode 150 题一样的表达式了? 那么接下来的步骤就不必多言了吧。
伍: 宣传一下本人
公众号 :「python 杂货铺」，专一于 python 语言及其相干常识。挖掘更多原创文章，期待您的关注。
