Python——中缀到后缀的转换(Sta

先贴代码,剩下的结合Pycharm的Debug贴图一一说明

#coding:utf-8    from pythonds.basic.stack import Stack  from string import *      def infixToPostfix(infixexpr):      # 这里创建一个字典是为了后面 优先级 的比较      prec = {}      prec["*"] = 3      prec["/"] = 3      prec["+"] = 2      prec["-"] = 2      prec["("] = 1        # 实例化      opstack = Stack()      postfixList = []            # 把输入的字符串分割开      tokenList = infixexpr.split()        for token in tokenList:          # 这里用到的是string模块中的两个方法,源代码都是手敲的字母和数字          if token in ascii_uppercase or token in digits:              postfixList.append(token)          elif token == "(":              opstack.push(token)          elif token == ")":              topstack = opstack.pop()              while topstack != "(":                  postfixList.append(topstack)                  topstack = opstack.pop()          else:              while (not opstack.isEmpty()) and (prec[opstack.peek()] >= prec[token]):                  postfixList.append(opstack.pop())              opstack.push(token)      while not opstack.isEmpty():          postfixList.append(opstack.pop())      return " ".join(postfixList)      # print(infixToPostfix("A * B + C * D"))  print(infixToPostfix("( A + B ) * C - ( D - E ) * ( F + G )"))

咱们开始分析吧!

1、传入参数,这里用的复杂一点的

2、 实例化、创建最终生成后缀样式的 列表、将传入的字符串分隔开

3、当token==“(”时,opstack中存入“(”,因为转换成后缀就不需要用“()”表示优先级,存起来是用于做优先级的判断

4、当token为字母时,会添加到postfixList(postfixList是用于存放最终结果的列表)

5、传入“ + ”,进入while循环 –> opstack不是空的(还记得第一步是传入的“(”吗) –> 进行对应的prec对应值的比较(也就是优先级的比较) –> 不满足条件循环结束 –> opstack添加新成员“ + ”

6、传入字母,将添加到postfixList

7、遇到“)”,我们的操作应该是去掉“( )”,后面加上“ + ”

 2 :去掉opstack内的“ + ” –>  3 :并返回到postfixList里面 –>  5 :删掉opstack内的“(” –> topstack==“(”循环结束

8、传入“ * ”,由于上一次传值opstack内元素删光了,直接跳出while循环并在opstack中添加“ * ”

9、传入字母,将添加到postfixList

10、传入“ – ” –> opstack不是空的(还记得步骤8,存入的“*”吗) –> prec[" * "]>prec[" – "] –> postfixList添加“ * ”并在opstack中添加“ – ”

11、传入“(”, opstack添加“(”

12、传入字母,将添加到postfixList

13、 1 传入“ – ” –>  2 opstack不是空的(还记得之前传入的“(”吗) –>  3 prec[“(”]  !>= prec[“ – ”]跳出while循环 –>  4 opstack追加“ – ”

14、传入字母,将添加到postfixList

15、传入“)”–> 将“ – ”从opstack中删除并追加到postfixList中 –> 删除“(”

16、传入“ * ”,while循环不满足条件跳出,将“ * ”追加到opstack中

17、传入“(”, opstack添加“(”

18、传入字母,将添加到postfixList

19、传入“ + ”,进入while循环 –> opstack不是空的(还记得之前传入的“(”和“ * ”吗) –> 进行对应的prec对应值的比较(也就是优先级的比较) –> 不满足条件循环结束 –> opstack添加新成员“ + ”

20、传入字母,将添加到postfixList

21、传入“)”,取出opstack中的“ + ”并返回到postfixList中,接着删掉对应的“(”

22、tokenList列表遍历完跳出for循环,接下来就是一次取出opstack中的“ * ”和“ – ”并添加到postfixList中,再按规定格式返回结果

23、我们的答案在此

我们的代码及思路源自:

http://interactivepython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html

愿我们共同进步

祝好