前序、中序和后序表達式是什么？

對于像B∗C 這樣的算術表達式，可以根據(jù)其形式來正確地運算。在B∗C 的例子中，由于乘號出現(xiàn)在兩個變量之間，因此我們知道應該用變量 B 乘以變量 C 。?

因為運算符出現(xiàn)在兩個操作數(shù)的中間 ，所以這種表達式被稱作中序表達式 。?

來看另一個中序表達式的例子：A+B∗C。雖然運算符 “ + ” 和 “ * ” 都在操作數(shù)之間，但是存在一個問題：它們分別作用于哪些操作數(shù)？ “ + ” 是否作用于 A 和 B ？“ * ” 是否作用于 B 和 C ？這個表達式看起來存在歧義。?

事實上，我們經(jīng)常讀寫這類表達式，并且沒有遇到任何問題。這是因為，我們知道運算符的特點。每一個運算符都有一個優(yōu)先級 。在運算時，高優(yōu)先級的運算符先于低優(yōu)先級的運算符參與運算。唯一能夠改變運算順序的就是括號。乘法和除法的優(yōu)先級高于加法和減法。?

盡管這些規(guī)律對于人來說顯而易見，計算機卻需要明確地知道以何種順序進行何種運算。一種杜絕歧義的寫法是完全括號表達式 。這種表達式對每一個運算符都添加一對括號。由括號決定運算順序，沒有任何歧義，并且不必記憶任何優(yōu)先級規(guī)則。?

比如，A+B∗C+D可以被重寫成((A+(B∗C))+D)， 以表明乘法優(yōu)先，然后計算左邊的加法表達式。由于加法運算從左往右結合，因此A+B+C+D可以被重寫成(((A+B)+C)+D)。?

我們已經(jīng)了解了中序表達式的原理， 還有另外兩種重要的表達式，也許并不能一目了然地看出它們的含義，那就是前序和后序表達式。?

以中序表達式A+B為例。如果把運算符放到兩個操作數(shù)之前，就得到了前序表達式+AB 。同理，如果把運算符移到最后，會得到后序表達式AB+ 。這兩種表達式看起來有點奇怪。?

通過改變運算符與操作數(shù)的相對位置，我們分別得到 前序表達式 和 后序表達式 。前序表達式要求所有的運算符出現(xiàn)在它所作用的兩個操作數(shù)之前，后序表達式則相反。下表列出了一些例子。

 A+B∗C可以被重寫為前序表達式 + A ∗ B C 

乘號出現(xiàn)在 B 和 C 之前，代表著它的優(yōu)先級高于加號。加號出現(xiàn)在 A 和乘法結果之前。

A+B∗C對應的后序表達式是 A B C ∗ + 

運算順序仍然得以正確保留，這是由于乘號緊跟 B 和 C 出現(xiàn)，意味著它的優(yōu)先級比加號更高。

關于前序表達式和后序表達式，盡管運算符被移到了操作數(shù)的前面或者后面，但是運算順序并沒有改變。
?

再舉一個例子：現(xiàn)在來看看中序表達式  (A+B)∗C。

括號用來保證加號的優(yōu)先級高于乘號。但是，當A+B被寫成前序表達式時，只需將加號移到操作數(shù)之前，即+AB。于是，加法結果就成了乘號的第一個操作數(shù)。乘號被移到整個表達式的最前面，從而得到∗+ABC。?

同理，后序表達式 A B + A B+ AB+保證優(yōu)先計算加法。乘法則在得到加法結果之后再計算。因此，正確的后序表達式為 AB+C∗。?

一些中序、前序與后序表達式對應示例：

我們?yōu)槭裁匆獙W習前/后序表達式？

在上面的中序表達式變?yōu)榍?后序表達式的例子中，請注意一個非常重要的變化。在后兩個表達式中，括號去哪里了？為什么前序表達式和后序表達式不需要括號？答案是，這兩種表達式中的運算符所對應的操作數(shù)是明確的。只有中序表達式需要額外的符號來消除歧義。前序表達式和后序表達式的運算順序完全由運算符的位置決定。?

前序表達式是一種十分有用的表達式，它將中序表達式轉換為可以依靠簡單的操作就能得到運算結果的表達式。例如， ( a + b ) ∗ ( c + d ) (a+b)*(c+d) (a+b)∗(c+d)轉換為 ∗ + a b + c d *+ab+cd ∗+ab+cd。它的優(yōu)勢在于只用兩種簡單的操作，入棧和出棧就可以解決任何中序表達式的運算。——《百度百科關于前序表達式作用的解釋》

從中序向前序和后序轉換

到目前為止，我們使用了一種難以言明的方法來將中序表達式轉換成對應的前序表達式和后序表達式。正如我們所想的那樣，這其中一定存在通用的算法，可用于正確轉換任意復雜度的表達式。

一個容易觀察到的方法是替換括號法，但前提是使用完全括號表達式。

如前所述，可以將A+B∗C寫作(A+(B∗C))，以表示乘號的優(yōu)先級高于加號。進一步觀察后會發(fā)現(xiàn)，每一對括號其實對應著一個中序表達式（包含兩個操作數(shù)以及其間的運算符）。 觀察子表達式(B∗C)的右括號。如果將乘號移到右括號所在的位置，并且去掉左括號，就會得到BC∗，這實際上是將該子表達式轉換成了對應的后序表達式。如果把加號也移到對應的右括號所在的位置，并且去掉對應的左括號，就能得到完整的后序表達式。

如果將運算符移到左括號所在的位置，并且去掉對應的右括號，就能得到前序表達式，如下圖所示。實際上，括號對的位置就是其包含的運算符的最終位置。

因此，若要將任意復雜的中序表達式轉換成前序表達式或后序表達式，可以先將其寫作完全括號表達式， 然后將括號內(nèi)的運算符移到 左括號處（前序表達式） 或者 右括號處（后序表達式）。

用Python實現(xiàn)從中序表達式到后序表達式的轉換?

我們需要開發(fā)一種將任意中序表達式轉換成后序表達式的算法。為了完成這個目標，讓我們進一步觀察轉換過程。?

再一次研究A+B∗C這個例子。如前所示，其對應的后序表達式為 ABC∗+。操作數(shù) A 、B 和 C 的相對位置保持不變，只有運算符改變了位置。再觀察中序表達式中的運算符。從左往右看，第一個出現(xiàn)的運算符是 + 。但是在后序表達式中，由于 * 的優(yōu)先級更高（寫成完全括號表達式后乘法所在的括號先進行運算），因此 * 先于 + 出現(xiàn)。在本例中，中序表達式的運算符順序與后序表達式的相反。?

在轉換過程中，由于運算符右邊的操作數(shù)還未出現(xiàn)（不知道運算符右邊是否還有括號運算）， 因此需要先將運算符保存在某處。同時，由于運算符有不同的優(yōu)先級，因此可能需要反轉它們的保存順序。 本例中的加號與乘號就是這種情況。由于中序表達式中的加號先于乘號出現(xiàn)，但乘號的運算優(yōu)先級更高，因此后序表達式需要反轉它們的出現(xiàn)順序。鑒于這種反轉特性，使用棧來保存運算符就顯得十分合理。?

那么對于(A+B)∗C，情況會如何呢？它對應的后序表達式為 AB+C∗。從左往右看，首先出現(xiàn)的運算符是 + 。不過，由于括號改變了運算符的優(yōu)先級，因此當處理到 * 時，+ 已經(jīng)被放入結果表達式中了。?

現(xiàn)在可以來總結轉換算法： 當遇到左括號時，需要將左括號保存下來，以表示接下來的內(nèi)容里會遇到高優(yōu)先級的運算符（就算括號里出現(xiàn)的運算符本身的優(yōu)先級低，但也因為在括號里而優(yōu)先級高了起來）；那個運算符需要等到左括號對應的右括號出現(xiàn)，才能確定轉換為后序表達式之后它應該存在的位置 （回憶一下完全括號表達式的轉換法）；當右括號出現(xiàn)時，也就是確定了括號內(nèi)運算符在后序表達式中的存在位置，便可以將左括號和左括號上面的其他運算符（可能有可能沒有）從棧中取出來。 (用于完全括號表達式)?

用代碼實現(xiàn)轉換算法：

?假設中序表達式是一個以空格分隔的標記串。其中， 運算符標記有+−∗/ ，括號標記有“ ( ( (”和“ ) ) )” ，操作數(shù)標記有 A 、B 、C 等。下面的步驟會生成一個后序標記串。?

步驟：

1.創(chuàng)建用于保存運算符的空棧 opstack ，以及一個用于保存結果的空列表。

2.使用字符串方法 split 將輸入的中序表達式轉換成一個列表。

3.從左往右掃描這個標記列表

3.1 如果標記是操作數(shù)，將其添加到結果列表的末尾。

3.2 如果標記是左括號，將其壓入 opstack 棧中。

3.3 如果標記是右括號，反復從 opstack 棧中移除元素，直到移除對應的左括號。將從棧中取出的每 一個運算符都添加到結果列表的末尾。

3.4 如果標記是運算符，將其壓入 opstack 棧中。但是，在這之前，需要先從棧中取出優(yōu)先級更高或相同的運算符，并將它們添加到結果列表的末尾。

4.當處理完輸入表達式以后，檢查 opstack 棧。將其中所有殘留的運算符全部添加到結果列表的末尾。?

為了在Python中實現(xiàn)這一算法，我們使用一個叫作 prec 的字典來保存運算符的優(yōu)先級值。該字典把每一個運算符都映射成一個整數(shù)。通過比較對應的整數(shù)，可以確定運算符的優(yōu)先級（本例隨意地使用了3、2、1）。左括號的優(yōu)先級值最小。這樣一來，任何與左括號比較的運算符都會被壓入棧中。我們也將導入string 模塊，它包含一系列預定義變量。本例使用一個包含所有大寫字母的字符（string.ascii_uppercase ）來代表所有可能出現(xiàn)的操作數(shù)。下述代碼展示了完整的轉換過程。

import string
class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def pop(self):
        return self.items.pop()
    def push(self, item):
        self.items.append(item)
    def peek(self):
        return self.items[len(self.items) - 1]
def infixToPostfix(infixexpr):
    prec = {
        "*" : 3,
        "/" : 3,
        "+" : 2,
        "-" : 2,
        "(" : 1
        }
    opStack = Stack()  # 創(chuàng)建棧
    postfixList = []  # 創(chuàng)建結果列表
    tokenList = infixexpr.split()  # 分割算式為列表
    for token in tokenList:                   # 遍歷算式
        if token in string.ascii_uppercase:   # 如果當前元素是操作數(shù)
            postfixList.append(token)         # 直接放入結果列表
        elif token == "(":                    # 如果當前元素是 左括號
            opStack.push(token)               # 左括號入棧
        elif token == ")":                    # 如果當前元素是 右括號
            topToken = opStack.pop()          # 從棧中取元素
            while topToken != "(":            # 取到的元素 不是右括號 循環(huán)執(zhí)行
                postfixList.append(topToken)  # 元素放入結果列表
                topToken = opStack.pop()      # 從棧中取元素
        else:                                 # 遍歷到的元素是 運算符
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                # （棧非空）并且（棧頂?shù)倪\算符優(yōu)先級大于等于當前運算符優(yōu)先級）循環(huán)執(zhí)行：
                #  棧頂元素入結果列表
                postfixList.append(opStack.pop())
            # 運算符入棧
            opStack.push(token)
    # 把棧里剩下的運算符全放入結果列表
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    # 返回拼接后的后序表達式字符串
    return " ".join(postfixList)
print(infixToPostfix("A + B * C"))
# A B C * +
print(infixToPostfix("( A + B ) * ( C + D )"))
# A B + C D + *

計算后序表達式

最后一個關于棧的例子是計算后序表達式。在這個例子中，棧再一次成為適合選擇的數(shù)據(jù)結構。不過，當掃描后序表達式時，需要保存的是操作數(shù)，而不是運算符。換一個角度來說，當遇到一個運算符時，需要用離它最近的兩個操作數(shù)來計算。?

為了進一步理解該算法，考慮后序表達式 4 5 6 * + 。當從左往右掃描該表達式時，首先會遇到操作數(shù) 4 和 5 。在遇到下一個符號之前，我們并不確定要對它們進行什么運算。故而將它們都保存在棧中，便可以在需要時取用。?

在本例中，緊接著 4 和 5 后出現(xiàn)的符號又是一個操作數(shù)。因此，將 6 也壓入棧中，并繼續(xù)檢查后面的符號。?

現(xiàn)在遇到了運算符 * ，這意味著需要將最近遇到的兩個操作數(shù)相乘。通過執(zhí)行兩次出棧操作，可以得到相應的操作數(shù)，然后進行乘法運算 5 ∗ 6 5*6 5∗6（本例的結果是30）。?

接著，將結果壓入棧中。這樣一來，當遇到后面的運算符時，它就可以作為操作數(shù)。當處理完最后一個運算符之后，棧中就只剩一個值。然后就可以將這個值取出來，并作為表達式的結果返回。?

過程如圖所示：

需要特別注意的是：?

處理除法運算時需要非常小心。由于后序表達式只改變運算符的位置，因此操作數(shù)的位置與在中序表達式中的位置相同。當從棧中依次取出除號的操作數(shù)時，它們的順序是顛倒的，因此我們要必須保證操作數(shù)的順序不能顛倒。?

用代碼實現(xiàn)后序表達式計算過程：?

假設后序表達式是一個以空格分隔的標記串。其中， 運算符標記有 ∗ / + − * / + - ∗/+−，操作數(shù)標記是一位的整數(shù)值。結果是一個整數(shù)。?

步驟：

1.創(chuàng)建空棧 operandStack

2.使用字符串方法 split 將輸入的后序表達式轉換成一個列表

3.從左往右掃描這個標記列表：

(1) 如果標記是操作數(shù)，將其轉換成整數(shù)(因為當前是字符)并且壓入 operandStack 棧中

(2) 如果標記是運算符，從 operandStack 棧中取出兩個操作數(shù)。第一次取出右操作數(shù)，第二次取出左操作數(shù)。進行相應的算術運算，然后將運算結果壓入 operandStack 棧中。

4.當處理完輸入表達式時，棧中的值就是結果。將其從棧中返回。?

為了方便運算，我們定義了輔助函數(shù) doMath 。它接受一個運算符和兩個操作數(shù)，并進行相應的運算。

import string

class Stack:
    def __init__(self):
        self.items = []
    def isEmpty(self):
        return self.items == []
    def pop(self):
        return self.items.pop()
    def push(self, item):
        self.items.append(item)
    def peek(self):
        return self.items[len(self.items) - 1]

def postfixEval(postfixExpr):
    operandStack = Stack()                             # 創(chuàng)建存放元素的棧
    tokenList = postfixExpr.split()                    # 分割算式字符串
    for token in tokenList:                            # 遍歷算式元素
        if token in "0123456789":                      # 如果 元素 是 操作數(shù)
            operandStack.push(int(token))              # 轉化為整型 入棧
        else:                                          # 元素不是操作數(shù) 是運算符
            operand2 = operandStack.pop()              # 從棧頂取 操作數(shù)2
            operand1 = operandStack.pop()              # 從棧頂取 操作數(shù)1
            result = doMath(token,operand1,operand2)   # 調(diào)用doMath進行運算
            operandStack.push(result)                  # 運算結果 入棧
    return operandStack.pop()                          
    # 返回棧內(nèi)元素（遍歷結束后這個唯一的元素就是整個算式的結果）
def doMath(op,op1,op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

總結

本篇文章就到這里了，希望能夠給你帶來幫助，也希望您能夠多多關注腳本之家的更多內(nèi)容!