注：本文如涉及到代碼，均經(jīng)過(guò)Python 3.7實(shí)際運(yùn)行檢驗(yàn)，保證其嚴(yán)謹(jǐn)性。
本文閱讀時(shí)間約為9分鐘。
接下來(lái)討論通用的中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的算法，以及如何使用Python程序來(lái)實(shí)現(xiàn)中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式這一過(guò)程。
通用的中綴轉(zhuǎn)后綴表達(dá)式的算法思考
在后綴表達(dá)式中，操作符的出現(xiàn)順序運(yùn)算次序一致，因此會(huì)出現(xiàn)操作符調(diào)整順序的情況。
中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理過(guò)程中，操作符比操作數(shù)要晚輸出。所以在程序掃描到對(duì)應(yīng)的第二個(gè)操作數(shù)之前，需要先把操作符保存起來(lái)。
這些保存起來(lái)的操作符當(dāng)中，由于優(yōu)先級(jí)的規(guī)則，有的操作符可能需要反轉(zhuǎn)次序輸出。這種保存需求和反轉(zhuǎn)特性，使得我們考慮用棧這種數(shù)據(jù)結(jié)構(gòu)來(lái)保存暫時(shí)未處理的操作符。
比如A + B * C中，"+"雖然先出現(xiàn)，但是優(yōu)先級(jí)不如后面的"*"，因此它要等到"*"操作符處理完成之后，才能再進(jìn)行處理。
關(guān)于操作符的優(yōu)先級(jí)，由于有括號(hào)強(qiáng)制優(yōu)先級(jí)的情況，所以不一定是優(yōu)先級(jí)更高的操作符排在前面，而是要看操作符實(shí)際的優(yōu)先順序。比如(A+B)*C中，“+”的優(yōu)先級(jí)就要高于“*”，所以這個(gè)中綴表達(dá)式的后綴形式是AB+C*。對(duì)于這種情況，程序的算法又該如何解決呢？
解決方法是，程序掃描到左括號(hào)時(shí)，標(biāo)記下來(lái)，其后出現(xiàn)的操作符的優(yōu)先級(jí)要得到提高，當(dāng)掃描到對(duì)應(yīng)的右括號(hào)時(shí)，就可以馬上輸出這個(gè)優(yōu)先級(jí)得到提高的操作符。
通用的中綴轉(zhuǎn)后綴表達(dá)式的算法總結(jié)
想通了上述的各種細(xì)節(jié)，就可以對(duì)通用的中綴轉(zhuǎn)后綴表達(dá)式的算法做一個(gè)總結(jié)了：
在從左到右逐個(gè)字符掃描中綴表達(dá)式的過(guò)程中，采用一個(gè)棧來(lái)暫存未處理的操作符。
由于棧的LIFO(后進(jìn)先出)的特性，棧頂?shù)牟僮鞣褪亲罱鼤捍孢M(jìn)去的，當(dāng)遇到一個(gè)新的操作符，就需要跟棧頂?shù)牟僮鞣缺容^優(yōu)先級(jí)，再?zèng)Q定如何處理。
通用的中綴轉(zhuǎn)后綴表達(dá)式的算法流程詳解
注：后面的算法描述中，約定中綴表達(dá)式是由空格隔開(kāi)的一系列單詞(token，即最小的一個(gè)詞法單位)構(gòu)成。操作符的單詞token包括*/+-()，操作數(shù)的單詞token則是單字母標(biāo)識(shí)符A、B、C等。
首先，創(chuàng)建空棧opstack用于暫存操作符，空列表postfixList用于保存后綴表達(dá)式。用字符串形式的中綴表達(dá)式轉(zhuǎn)換為單詞(token)作為元素構(gòu)成的列表。
例如，"A + B * C"字符串利用字符串方法string.split(" ")轉(zhuǎn)換成由操作數(shù)和操作符構(gòu)成的列表['A', '+', 'B', '*', 'C']。
然后，再?gòu)淖笾劣覓呙柚芯Y表達(dá)式單詞列表，會(huì)有以下幾種情況：
- 如果單詞token是操作數(shù)，則直接添加到后綴表達(dá)式列表postfixList的末尾；
- 如果單詞token是左括號(hào)“(”，則壓入opstack棧頂（所謂壓入棧頂，就是將元素入棧）；
- 如果單詞token是右括號(hào)“)”，則反復(fù)彈出opstack棧頂操作符（所謂彈出棧頂，就是將元素移除出棧），加入到輸出列表postfixList的末尾，直到碰到左括號(hào)為止；
- 如果單詞是操作符“*/+-”，則壓入opstack棧頂——壓入之前，要比較其與opstack棧當(dāng)前的棧頂操作符的優(yōu)先級(jí)。如果當(dāng)前棧頂?shù)牟僮鞣膬?yōu)先級(jí)高于或等于它，則要反復(fù)彈出棧頂?shù)牟僮鞣瑢ｍ數(shù)牟僮鞣敵霾⒓尤氲搅斜韕ostfixList的末尾，直到opstack棧頂?shù)牟僮鞣膬?yōu)先級(jí)低于它為止。把只裝操作符的棧想象成一堆盤(pán)子，上面的是棧頂，下面的是棧底，這里的要求是，棧底的操作符的優(yōu)先級(jí)必須小于棧頂?shù)牟僮鞣?/li>
接著，中綴表達(dá)式單詞列表掃描結(jié)束后，把opstack棧中的所有剩余操作符依次彈出，添加到輸出列表postfixList的末尾。
最后，把輸出列表postfixList再用join方法使其轉(zhuǎn)化為字符串形式的后綴表達(dá)式，算法結(jié)束。
具體實(shí)現(xiàn)的代碼如下：
# 中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的程序。
class Stack:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def push(self, item):
self.items.append(item)
def pop(self):
return self.items.pop()
def peek(self):
return self.items[len(self.items)-1]
def size(self):
return len(self.items)
def infixToPostfix(infixexpr):
"""
infixexpre：一個(gè)字符串類型的中綴表達(dá)式，操作數(shù)與操作符之間都由空格" "隔開(kāi)。
如"A+B*C+D"是錯(cuò)誤的輸入，"A + B * C + D"才是正確的輸入。
"""
# 下面連續(xù)6行是用一個(gè)字典記錄操作符優(yōu)先級(jí)。
prec = {}
prec["*"] = 3
prec["/"] = 3
prec["+"] = 2
prec["-"] = 2
prec["("] = 1
opStack = Stack() # 創(chuàng)建一個(gè)名為opStack的空棧。
postfixList = []
tokenList = infixexpr.split() # 解析表達(dá)式到單詞列表。
for token in tokenList:
if token in "ABCDEFGHIJKLMNOPQRSTUVWXYZ" or token in "0123456789": #操作數(shù)。
postfixList.append(token)
elif token == '(': # 碰到左括號(hào)“(”，直接輸出。
opStack.push(token)
elif token == ')': # 碰到右括號(hào)“)”，不停地彈出來(lái)。
topToken = opStack.pop()
while topToken != '(':
postfixList.append(topToken)
topToken = opStack.pop()
else: # 碰到操作符也是不停地彈出，直到棧頂?shù)牟僮鞣麅?yōu)先級(jí)比自己低。
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) # 合成后綴表達(dá)式字符串。
print(infixToPostfix("A + B * C + D"))
<<<A B C * + D +
To be continued.
