Python——中缀到后缀的转换（Stack）

q987654

　　先贴代码，剩下的结合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
　　愿我们共同进步
　　祝好