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

2023-01-31 05:01:46 转换 后缀 中缀

先贴代码,剩下的结合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、传入参数,这里用的复杂一点的

1.png


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

2.png


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

3.png


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

4.png


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

5.png


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

6.png


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

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


8.png


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

8.png


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

9.png


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

10.png


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

11.png


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

12.png


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

13.png


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

14.png


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

15.png


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

16.png


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

17.png


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

18.png


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

19.png


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

20.png


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

21.png


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

22.png


23、我们的答案在此

23.png



我们的代码及思路源自:

Http://interactivePython.org/runestone/static/pythonds/BasicDS/InfixPrefixandPostfixExpressions.html


愿我们共同进步

祝好


相关文章