APP
最詳細(xì)的中綴轉(zhuǎn)后綴
學(xué)渣們請(qǐng)就座：（不用看別人，說(shuō)的就是你！）
大家好，我是Dream。此時(shí)此刻我只想說(shuō)：男神可以遲到，但永遠(yuǎn)不會(huì)缺席！那個(gè)男人回來(lái)了?。?！
最近眼發(fā)炎了，非常難受，但這不會(huì)阻止我為大家更新文章的，請(qǐng)把 淚目 打在評(píng)論區(qū)?。?！
話不多說(shuō)，今天給大家介紹一下，中綴表達(dá)式如何轉(zhuǎn)后綴表達(dá)式。
現(xiàn)在，肯定會(huì)有學(xué)渣問(wèn)：什么是中綴和后綴表達(dá)式呢？
我只想說(shuō)：你好優(yōu)秀，請(qǐng)前排就坐~
簡(jiǎn)單來(lái)講，中綴表達(dá)式就是我們學(xué)習(xí)數(shù)學(xué)時(shí)的各種表達(dá)式，
such as：（A+B）*C/(D-E)
什么是后綴表達(dá)式呢？就是將運(yùn)算符移動(dòng)到字符串后面，但也不是全部移動(dòng)到后面，當(dāng)然也是有條件和順序的。
我們都知道運(yùn)算符是有優(yōu)先級(jí)的，比如乘號(hào)的優(yōu)先級(jí)就高于加號(hào)的優(yōu)先級(jí)，那就要在同一運(yùn)算區(qū)域下先移動(dòng)乘號(hào)再移動(dòng)加號(hào)，為什莫說(shuō)在同一領(lǐng)域下呢，因?yàn)槲覀兌贾涝谶\(yùn)算中少不了括號(hào)的存在，那么括號(hào)就界定了屬不屬于同一領(lǐng)域下。
算了，不和你們多BB了，舉個(gè)例子吧：
A+B : AB+
A+B *C : ABC *+
(A+B) *(C+D) : AB+CD+ *
emmm,我猜你還是不懂應(yīng)該（僅代表學(xué)渣）
好吧，前兩個(gè)你應(yīng)該懂了吧（不懂的同學(xué)回家默寫三千遍三字經(jīng)）
那我來(lái)講一下第三個(gè)：首先(A+B) *(C+D)可以寫作（(A+B) *(C+D)）沒(méi)有問(wèn)題吧，先看第一層括號(hào)，第一層括號(hào)中只有兩個(gè)小括號(hào)和一個(gè) *，那么好的將最外層右邊的括號(hào)用乘號(hào)替換掉，左邊括號(hào)刪除，即：(A+B) (C+D) *
同理看第二層括號(hào)，同樣方法，運(yùn)算符替換掉右邊括號(hào)，同時(shí)刪除左邊括號(hào)，即：AB +(C+D) *----AB +CD+ *得到了最終答案， 是不是very easy？那你會(huì)用代碼表示嗎？？？哈哈哈，繼續(xù)！
首先調(diào)用棧和string：
from pythonds3.basic import Stack
import string
定義一個(gè)函數(shù)：
def infix_to_postfix(infix):
"""將中序表達(dá)式轉(zhuǎn)化為后序表達(dá)式，核心思想"""
這里定義了一個(gè)棧來(lái)儲(chǔ)存運(yùn)算符，一個(gè)列表來(lái)儲(chǔ)存得到的表達(dá)式。
最后將得到的列表用join函數(shù)合并成一個(gè)字符串
當(dāng)出現(xiàn)括號(hào)左時(shí)入棧，字符串照常輸出在列表中，運(yùn)算符繼續(xù)入棧，當(dāng)出現(xiàn)有括號(hào)時(shí)運(yùn)算符出棧，直至遇到最初的左括號(hào)才停止出棧！就這樣循環(huán)往復(fù)遍歷，直至遍歷結(jié)束。
in_list = infix.split() # 將字符串變?yōu)榱斜恚⒁?，輸入時(shí)需要空格隔開(kāi)單個(gè)元素，例："1 2 3 * 2 3"
stack1 = Stack() # 創(chuàng)建空棧，用于存儲(chǔ)遍歷字符串列表的括號(hào)、操作符
post_list = [] # 創(chuàng)建空列表，用于存儲(chǔ)后序表達(dá)式
priority = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1} # 創(chuàng)建優(yōu)先級(jí)字典
for elem in in_list: # 遍歷中序表達(dá)式
if elem == '(': # 為左括號(hào)，入棧
stack1.push(elem)
elif elem in string.ascii_uppercase: # 為字符串里的大寫字母，加入空的輸出列表
post_list.append(elem)
elif elem == ')': # 為右括號(hào)，則出棧，添加到輸出列表，直到匹配到左括號(hào)
token = stack1.pop()
while token != '(':
post_list.append(token)
token = stack1.pop()
else: # 為操作符，則判斷棧中是否有更高優(yōu)先級(jí)的操作符，有則出棧，無(wú)則添加到列表尾部，
while (not stack1.is_empty()) and (priority[stack1.peek()] >= priority[elem]):
post_list.append(stack1.pop())
stack1.push(elem) # 若放到列表尾部，則棧永遠(yuǎn)不會(huì)有操作符
while not stack1.is_empty(): # 若棧不為空，則彈出到后續(xù)表達(dá)式列表（即優(yōu)先級(jí)低的放最后）
post_list.append(stack1.pop())
return ''.join(post_list) # 將列表連在一起
if __name__ == '__main__':
print(infix_to_postfix("A * B + ( C + D ) * ( E - F )"))
emmm，這就是今天我和大家分享的東西了。
如果你喜歡的話，就不要吝惜你的一鍵三連了~
本文摘自 ：https://blog.51cto.com/u
