python实现中缀表达式转逆波兰式

╰半夏微凉° 2022-09-09 14:43 168阅读 0赞

中缀转后缀需要遵循以下规则：

> 1.  字母直接输出  
>     2.右括号，依次弹栈并输出符号，直到遇到左括号  
>     3.字符优先级低于栈顶符号，依次弹栈直到遇到字符优先级高于栈顶符号或者遇到左括号或者空栈，当前符号再才进栈(如果和栈顶符号优先级一样也要先栈顶符号也要先弹栈，因为优先级一样运算顺序是从左往右)  
>     4.左括号直接压栈，如果栈顶元素为左括号，该字符同样直接压栈

代码实现：

def mid2behind():
        ss=input().strip().replace(" ","")
        alp=[chr(x) for x in range(97,123)]
        prori={ 
            "+":1,
            "-":1,
            "*":2,
            "/":2,
            "(":3
        }
        mystack=[]#符号栈
        res=""#表达式
    
        for x in ss:
            print(x)
            #字母直接入栈
            if x in alp:
                res+=x
            #右括号，弹栈直到遇到左括号
            elif x==")":
                while mystack[-1]!="(":
                    res+=mystack[-1]
                    mystack.pop()
                mystack.pop()
            #其他运算符
            else:
                #栈为空或者运算符为左括号时直接压栈
                if len(mystack)==0:
                    mystack.append(x)
                elif x=="(":
                    mystack.append(x)
                #根据运算符优先级选择何时压栈
                else:
                    while len(mystack)!=0 and prori[x]<=prori[mystack[-1]]:
                        #栈顶元素为左括号则直接压栈
                        if mystack[-1]=="(":
                            break
                        else:
                            res+=mystack[-1]
                            mystack.pop()
                    mystack.append(x)
            print(res,mystack)
        while len(mystack)!=0:
            res+=mystack[-1]
            mystack.pop()
        print(res, mystack)
    if __name__ == '__main__':
        mid2behind()

运行结果：

a*c+d-(h-g*e+f)-r
    a
    a []
    *
    a ['*']
    c
    ac ['*']
    +
    ac* ['+']
    d
    ac*d ['+']
    -
    ac*d+ ['-']
    (
    ac*d+ ['-', '(']
    h
    ac*d+h ['-', '(']
    -
    ac*d+h ['-', '(', '-']
    g
    ac*d+hg ['-', '(', '-']
    *
    ac*d+hg ['-', '(', '-', '*']
    e
    ac*d+hge ['-', '(', '-', '*']
    +
    ac*d+hge*- ['-', '(', '+']
    f
    ac*d+hge*-f ['-', '(', '+']
    )
    ac*d+hge*-f+ ['-']
    -
    ac*d+hge*-f+- ['-']
    r
    ac*d+hge*-f+-r ['-']
    ac*d+hge*-f+-r- []