算法，既不易入门又不易掌握的知识。上次介绍了如何使用栈实现中缀表达式的求值。如果我是出题者，当然要测试前缀、后缀、中缀表达式的相互转换，然后就变成了利用栈来实现前缀、后缀表达式的求值。.前缀、后缀、中缀表达式的转换及其运算可以说是计算机考研的重点。先看下表：注意：前序表达式和后序表达式没有展开标记。这篇文章中有对应的图：https://mp.weixin.qq.com/s/NRbFXZAXEUeXhKKYY7CReg中缀表达式前缀表达式求值中缀表达式转前缀表达式的规则：1.将输入的字符串取反，如"2*3/(2-1)+3*(4-1)"反转后变成")1-4(*3+)1-2(/3*2",2.取出字符串中的下一个字符2.1.如果是操作数，直接输出2.2.如果是")"，压入栈2.3.如果是运算符，不是"(",")",则继续循环下面的处理2.3.1.如果堆栈为空，则将此运算符压入堆栈并结束此步骤2.3.2。如果栈顶是“)”，则将这个操作符压入栈中，本步骤2.3.2结束。如果该算子的优先级与栈顶相同或高于栈顶，则将该算子入栈，本步骤2.3.4结束。否则，运算符不断出栈，直到满足以上三个条件之一，则将这个运算符压入栈2.4，如果是“(”，则运算符不断出栈，直到“)”，则将“)”出栈并丢弃3，如果还有更多的字符串，则转步骤2。4、没有更多未处理的字符串，输出栈中剩余元素为5.再次反转字符串得到最终结果。经过以上步骤，得到的输出就是转换得到的前缀表达式。前缀表达式的计算方法：从后向前扫描前缀表达式，设置一个操作数栈，如果是操作数则直接入栈，如果是运算符则弹出对应的运算符thestackfromthestack计算操作数并将计算结果压入堆栈。直到整个前缀表达式从右向左扫描完，此时操作数栈中应该只有一个元素，这个元素的值就是前缀表达式的计算结果。以上过程是使用数据结构栈实现的，具体代码如下'''@作者：Runsen@微信：RunsenLiu@微信公众号：Python之王@CSDN：https://blog.csdn.net/weixin_44510615@Github:https://github.com/MaoliRUNsen@Date:2020/12/17'''导入reclassStack():def__init__(self):self.items=[]defpush(self,item):returnself。items.append(item)defpop(self):返回self.items.pop()defsize(self):返回len(self.items)defpeek(self):返回self.items[len(self.items)-1]defdisplay(self):print(self.items)definfix_to_prefix(s):prec={'*':3,'/':3,'+':2,'-':2,'(':4,')':1}a=重新。findall('[1-9]\d*|[\+\-\*\/\(\)]',input('请输入中缀表达式:'))prefix=[]forxina[::-1]:ifre.match('[0-9]',x):#操作数，直接输出prefix.append(x)else:#如果是")"，则压入栈ifx==')':s.push(x)elifx=='(':whileTrue:i=s.pop()ifi==')':breakelse:prefix.append(i)else:ifs.size()>0andprec[x]<=prec[s.peek()]:prefix.append(s.pop())s.push(x)for_inrange(s.size()):prefix.append(s.pop())returnprefix[::-1]defcal_prefix(s,prefix):#idea：从后往前扫描前缀表达式，设置一个操作数栈，如果是操作数，直接入栈，如果是运算符，则从stack执行pop操作符对应的操作数运算，并将计算结果入栈#直到从右向左扫描完整个前缀表达式，那么操作数栈中应该只有一个元素，这个元素的值就是前缀表达式的计算结果。forxinprefix[::-1]:ifre.match('[0-9]',x):s.push(x)else:a2=int(s.pop())a1=int(s.pop())ifx=='*':a=a1*a2elifx=='/':a=a2/a1elifx=='+':a=a1+a2else:a=a2-a1s.push(a)returns.pop()if__name__=='__main__':s=Stack()prefix=infix_to_prefix(s)print('前缀表达式:',prefix)prefix_val=cal_prefix(s,prefix)print('前缀表达式计算结果:',prefix_val)请输入中缀表达式：2*3/(2-1)+3*(4-1)前缀表达式：['+','*','2','/','3','-','2','1','*','3','-','4','1']前缀表达式计算结果：15请输入中缀表达式：9+(3-1*2)*3+10/2前缀表达式：['+','+','9','*','-','3','*','1','2','3','/','10','2']前缀表达式计算结果：17中缀表达式转后缀表达式中缀表达式转后缀表达式的求值规则：1.对操作数，直接输出；2.当栈为空时，遇到一个运算符，将其压入栈中；3.遇到左括号时，压入栈中；4、遇到右括号时，执行一次入栈操作，将栈中的元素出栈，直到左括号出栈，左括号不输出；5.当遇到其他运算符'+"-"*"/'时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该运算符压入栈中；6.最后将in中的元素栈一个一个的出栈输出，经过以上步骤，得到的输出就是转换后的后缀表达式，后缀表达式的计算方法：将前面的后缀表达式向后扫描，设置一个操作数栈，如果是操作数，直接压栈，如果是运算符，从栈中弹出该运算符对应的操作数执行运算，并将计算结果压入栈中，直到扫描完整个后缀表达式从右到左，此时操作数栈中应该只有一个元素，这个元素的值就是后缀表达式的计算结果。以上过程是使用数据结构栈实现的，具体代码如下：'''@作者：Runsen@微信：RunsenLiu@微信公众号：Python之王@CSDN：https://blog.csdn。net/weixin_44510615@Github:https://github.com/MaoliRUNsen@Date:2020/12/17'''importreclassStack():def__init__(self):self.items=[]defpush(self,item):returnself。项目.append(项目)defpop(self):returnsself.items.pop()defsize(self):returnlen(self.items)defpeek(self):returnsself.items[len(self.items)-1]defdisplay(self):print(self.items)definfix_to_postfix(s):prec={'*':3,'/':3,'+':2,'-':2,'(':1,')':4}a=re.findall('[1-9]\d*|[\+\-\*\/\(\)]',input('请输入中缀表达式:'))postfix=[]forxina：如果。match('[0-9]',x):#操作数，直接输出postfix.append(x)else:#如果是“(”，则入栈ifx=='(':s.push(x)elifx==')':whileTrue:i=s.pop()ifi=='(':breakelse:postfix.append(i)else:ifs.size()>0andprec[x]<=prec[s.peek()]:postfix.append(s.pop())s.push(x)for_inrange(s.size()):postfix.append(s.pop())returnpostfixdefcal_postfix(s,postfix):forxinpostfix:ifre.match('[0-9]',x):s.push(x)else:a1=int(s.pop())a2=int(s.pop())ifx=='*':a=a1*a2elifx=='/':a=a2/a1elifx=='+':a=a1+a2else:a=a2-a1s。push(a)returns.pop()if__name__=='__main__':s=Stack()postfix=infix_to_postfix(s)print('后缀表达式:',postfix)postfix_val=cal_postfix(s,postfix)print('后缀表达式计算结果：',postfix_val)请输入中缀表达式：2*3/(2-1)+3*(4-1)['2','3','*','2','1','-','/','3','4','1','-']后缀表达式：['2','3','*','2','1','-','/','3','4','1','-','*','+']后缀表达式计算结果：15请输入中缀表达式：9+(3-1*2)*3+10/2后缀表达式:['9','3','1','2','*','-','3','*','10','2','/','+','+']后缀表达式的计算结果：17其实这道题是Leetcode第150题，逆波兰表达式按照逆波兰表示法求值，求值的表达。有效的运算符包括+、-、*、/。每个操作数可以是整数或另一个反向波兰表达式。示例1：输入：["2","1","+","3","*"]输出：9解释：该公式转化为一个普通的中缀算术表达式：((2+1)*3)=9示例2：输入：["4","13","5","/","+"]输出：6解释：该公式转化为一个普通的中缀算术表达式：(4+(13/5))=6prefixexpressiontoinfixexpression从右到左开始，取出一个运算符和运算符右边的两个数进行计算，将计算结果放入，直到计算结束。以前缀表达式+/*23-21*3-41为例，转化为中缀表达式：(1)取出-,4,1，计算并把结果放回去，得到+/*23-21*3(4-1);(2)取出*,3,(4-1),计算并把结果放回去得到+/*23-21(3*(4-1));(3)取出-、2、1，计算并把结果放回去得到+/*23(2-1)(3*(4-1))；(3)取出*,2,3,计算并把结果放回去得到+/(2*3)(2-1)(3*(4-1));(4)取出/,(2*3),(2-1),计算并把结果放回去得到+((2*3)/(2-1))(3*(4-1));(5)取出+,((2*3)/(2-1)),(3*(4-1)),计算将把结果放回去得到((2*3)/(2-1))+(3*(4-1))，计算结束，显然计算结果为15。后缀表达式到中缀表达式从左到右，取出一个运算符和运算符左边的两个数进行计算，放入计算结果直到计算结束，后缀表达式23*21-/以341-*+为例，转化为中缀表达式：(1)取出2、3、*，计算并放入结果返回得到(2*3)21-/341-*+；(2)取出2、1、-，计算并把结果放回去得到(2*3)(2-1)/341-*+；(3)取出(2*3),(2-1),/,计算并把结果放回去得到((2*3)/(2-1))341-*+；(4)取出4、1、-，计算并把结果放回去得到((2*3)/(2-1))3(4-1)*+；(5)取3,(4-1),*,计算并将结果放回去得到((2*3)/(2-1))3*(4-1)+;(6)取出((2*3)/(2-1)),3*(4-1),+,计算并将结果放回去得到((2*3)/(2-1))+3*(4-1)，显然求值为15。本文已收录在GitHub：https://github.com/MaoliRUNsen/runsenlearnpy100
