Python——中缀到后缀的转换（Sta
- 2020 年 1 月 8 日
- 筆記
先贴代码，剩下的结合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
愿我们共同进步
祝好
