零：请教一个问题两个已知数相加或相乘，用代码表达起来是不是很容易？如果给定的字符串类似于由一个符号和两个数字组成的1+1，需要其结果，可以使用split()函数对字符串进行分割计算，并不难。那么再进一步升级，如果这个字符串有两个以上的数字和一个符号，是一个包括加减乘除和括号的复杂算术表达式呢？例如下面的算术表达式：1+(2-3*4)/5+6我们可以使用栈来完成这个算术表达式的计算。创建两个栈分别存放数字和符号，然后通过符号之间的优先级关系判断是否可以计算出前一个符号。具体方法在leetcode224基础计算器│leetcode一文中有详细分析。本文不再重复分析该方法。想了解更多的朋友可以点击链接查看文章。现在请来本文的主角！一：主角出现本文的主角叫做逆波兰表达式，也叫后缀表达式。后者，一个比较通俗的名字，明确表达了自己的意思，意思是计算的符号在两个待计算的数之后。我们常用的算术表达式是中缀表达式，计算符号在两个数之间。现实中基本没有直接给出反波兰表达式的场景，也就是说必须先将中缀表达式转换成反波兰表达式。我们用上面的例子，先看看转换成反波兰表达式是什么样子的？1234*-5/+6+二：这怎么是一串奇怪的字符，怎么转换的？真的可以用来计算吗？先分析第一题：中缀表达式：1+(2-3*4)/5+6第一步：在所有运算步骤前加括号，表示优先级。这一步去除了符号之间的空格优先级关系，计算顺序按照括号内进行。例如：乘除法优先于加减法((1+((2-(3*4))/5))+6)第二步：把括号中的符号移动到包裹的最里面收尾括号((1((2(34)*)-5)/)+6)+第三步：去掉括号1234*-5/+6+看到现在，你是不是还一头雾水，所以，是一定要继续阅读！继续下一步。现在必须要说的是如何计算转换后的反波兰表达式，不然看的人都等不及了。从逆波兰表达式的左边开始，先找到第一个符号，提取符号前的两位数字并计算。1.找到符号`*`，计算`3*4=12`，当前表达式为`1212-5/+6+`2。找到符号`-`，计算`2-12=-10`，当前表达式为`1-105/+6+`3。找到符号`/`，计算`-10/5=-2`，当前表达式为`1-2+6+`4。找到符号`+`，计算`1+-2=-1`，当前表达式为`-16+`5。找到符号`+`，计算`-1+6=5`，结果为`5`看完这个例子，是不是豁然开朗了？将表达式转换为反向波兰表达式，你可以从左到右搜索一个符号并立即计算它。运算符的强制优先级和运算符之间的优先级关系完全从括号中删除。3：我们需要一道leetcode150的题，题目是关于求逆波兰表达式的：150.逆波兰表达式的求值是基于逆波兰表示法，求出表达式的值。有效的运算符包括+、-、*、/。每个操作数可以是整数或另一个反向波兰表达式。解释：-整数除法只保留整数部分。-给定的反波兰表达式总是有效的。换句话说，表达式将始终产生有效值，并且不存在除以0的数。示例1：输入：["2","1","+","3","*"]输出：9解释：这个公式转化为一个普通的中缀算术表达式：((2+1)*3)=9如果要实现反波兰表达式的操作，还需要引入--栈。将数值元素一个一个地添加到堆栈中。如果遇到符号，栈中的最后两个值将被弹出栈。注意顺序。先弹出的值在计算时在符号之后，后弹出的值在计算时在符号中。前。计算完成后，将得到的值压入栈中。最后，数值栈中只保留一个数值元素，即为计算结果。classSolution:defevalRPN(self,tokens:list[str])->int:valuestack=[]fortokenintokens:iftokennotin"+-*/":#当前元素是一个数字值栈。append(int(token))else:valueafter=valuestack.pop()valuebefore=valuestack.pop()iftoken=='+':valuestack.append(valuebefore+valueafter)eliftoken=='-':valuestack.append(beforevalue-aftervalue)eliftoken=='*':valuestack.append(beforevalue*aftervalue)eliftoken=='/':valuestack.append(int(beforevalue/value之后))返回值堆栈。pop()4:上一题好像不全。上题直接给出了逆波兰表达式，我们只需要求解即可。那么如果只给出一个普通的表达式，则需要使用逆波兰表达式来计算。如何使用代码来做到这一点？defInfixexpressionreversesPolishexpression(s):'''假设s是一个有效的中缀表达式，只有数字和运算符号（包括括号）'''Symbolstack,expressionqueue,lastcharacter=[],[],''#符号优先级（堆栈中的最后一位与当前符号进行比较）符号优先级表={"+":{"+":'>','-':'>','*':'<','/':'<','(':'<',')':'>'},"-":{"+":'>','-':'>','*':'<','/':'<','(':'<',')':'>'},"*":{"+":'>','-':'>','*':'>','/':'>','(':'<',')':'>'},"/":{"+":'>','-':'>','*':'>','/':'>','(':'<',')':'>'},"(":{"+":'<','-':'<','*':'','/':'','(':'<',')':'='},")":{"+":'','-':'','*':'','/':'','(':'',')':''},}对于s中的值：如果值不在'+-*/()':#如果前一个字符不在'+-*/()':#是数字表达式的连续数组.append(expressionqueue.pop()*10+int(value))else:表达式queue.append(int(value))else:whileTrue:#There可能是栈上优先级较高的多个符号，需要遍历iflen(symbolstack)==0orsymbolprioritytable[symbolstack[-1]][value]=='<':#当前符号优先级高，加入符号栈stack.append(value)breakelifSymbolprioritytable[symbolstack[-1]][value]=='=':#Theterminatorencounteredtheterminatorsymbolstack.pop()breakelif符号优先级表[symbolstack[-1]][value]=='>':#栈中优先级较高，可计算表达式队列append(symbolstack.pop())previouscharacter=valueforsymbolinsymbolstack:#可能还剩一个符号符号栈，直接添加到表达式queue.append(symbolstack.pop())returnexpressionqueueif__name__=="__main__":print(infixexpressionreversePolishexpression('1+(2-3*4)/5+6'))上面代码执行后的结果是：[1,2,3,4,'*','-',5,'/','+',6,'+']isIsn它转换成与leetcode150题相同的表达式吗？那么接下来的步骤就不用多说了。5：推销自己公众号：《python杂货店》，重点介绍python语言及相关知识。发现更多原创文章，期待您的关注。
