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

對于像B∗C 這樣的算術(shù)表達式，可以根據(jù)其形式來正確地運算。在B∗C 的例子中，由于乘號出現(xiàn)在兩個變量之間，因此我們知道應(yīng)該用變量 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)先，然后計算左邊的加法表達式。由于加法運算從左往右結(jié)合，因此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 和乘法結(jié)果之前。

A+B∗C對應(yīng)的后序表達式是 A B C ∗ + 

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

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

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

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

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

一些中序、前序與后序表達式對應(yīng)示例：

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

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

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

從中序向前序和后序轉(zhuǎn)換

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

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

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

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

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

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

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

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

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

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

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

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

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

步驟：

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

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

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

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

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

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

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

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

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

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)建結(jié)果列表
    tokenList = infixexpr.split()  # 分割算式為列表
    for token in tokenList:                   # 遍歷算式
        if token in string.ascii_uppercase:   # 如果當前元素是操作數(shù)
            postfixList.append(token)         # 直接放入結(jié)果列表
        elif token == "(":                    # 如果當前元素是 左括號
            opStack.push(token)               # 左括號入棧
        elif token == ")":                    # 如果當前元素是 右括號
            topToken = opStack.pop()          # 從棧中取元素
            while topToken != "(":            # 取到的元素 不是右括號 循環(huán)執(zhí)行
                postfixList.append(topToken)  # 元素放入結(jié)果列表
                topToken = opStack.pop()      # 從棧中取元素
        else:                                 # 遍歷到的元素是 運算符
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                # （棧非空）并且（棧頂?shù)倪\算符優(yōu)先級大于等于當前運算符優(yōu)先級）循環(huán)執(zhí)行：
                #  棧頂元素入結(jié)果列表
                postfixList.append(opStack.pop())
            # 運算符入棧
            opStack.push(token)
    # 把棧里剩下的運算符全放入結(jié)果列表
    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 + *

計算后序表達式

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

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

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

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

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

過程如圖所示：

需要特別注意的是：?

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

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

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

步驟：

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

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

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

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

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

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

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

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))              # 轉(zhuǎn)化為整型 入棧
        else:                                          # 元素不是操作數(shù) 是運算符
            operand2 = operandStack.pop()              # 從棧頂取 操作數(shù)2
            operand1 = operandStack.pop()              # 從棧頂取 操作數(shù)1
            result = doMath(token,operand1,operand2)   # 調(diào)用doMath進行運算
            operandStack.push(result)                  # 運算結(jié)果 入棧
    return operandStack.pop()                          
    # 返回棧內(nèi)元素（遍歷結(jié)束后這個唯一的元素就是整個算式的結(jié)果）
def doMath(op,op1,op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return op1 / op2
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

總結(jié)

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

最新評論