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