前序、中序和后序表達(dá)式是什么？

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

因?yàn)檫\(yùn)算符出現(xiàn)在兩個(gè)操作數(shù)的中間 ，所以這種表達(dá)式被稱作中序表達(dá)式 。?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

一個(gè)容易觀察到的方法是替換括號(hào)法，但前提是使用完全括號(hào)表達(dá)式。

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

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

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

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

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

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

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

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

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

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

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

步驟：

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

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

3.從左往右掃描這個(gè)標(biāo)記列表

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

3.2 如果標(biāo)記是左括號(hào)，將其壓入 opstack 棧中。

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

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

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

為了在Python中實(shí)現(xiàn)這一算法，我們使用一個(gè)叫作 prec 的字典來保存運(yùn)算符的優(yōu)先級(jí)值。該字典把每一個(gè)運(yùn)算符都映射成一個(gè)整數(shù)。通過比較對(duì)應(yīng)的整數(shù)，可以確定運(yùn)算符的優(yōu)先級(jí)（本例隨意地使用了3、2、1）。左括號(hào)的優(yōu)先級(jí)值最小。這樣一來，任何與左括號(hào)比較的運(yùn)算符都會(huì)被壓入棧中。我們也將導(dǎo)入string 模塊，它包含一系列預(yù)定義變量。本例使用一個(gè)包含所有大寫字母的字符（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:   # 如果當(dāng)前元素是操作數(shù)
            postfixList.append(token)         # 直接放入結(jié)果列表
        elif token == "(":                    # 如果當(dāng)前元素是 左括號(hào)
            opStack.push(token)               # 左括號(hào)入棧
        elif token == ")":                    # 如果當(dāng)前元素是 右括號(hào)
            topToken = opStack.pop()          # 從棧中取元素
            while topToken != "(":            # 取到的元素 不是右括號(hào) 循環(huán)執(zhí)行
                postfixList.append(topToken)  # 元素放入結(jié)果列表
                topToken = opStack.pop()      # 從棧中取元素
        else:                                 # 遍歷到的元素是 運(yùn)算符
            while (not opStack.isEmpty()) and (prec[opStack.peek()] >= prec[token]):
                # （棧非空）并且（棧頂?shù)倪\(yùn)算符優(yōu)先級(jí)大于等于當(dāng)前運(yùn)算符優(yōu)先級(jí)）循環(huán)執(zhí)行：
                #  棧頂元素入結(jié)果列表
                postfixList.append(opStack.pop())
            # 運(yùn)算符入棧
            opStack.push(token)
    # 把棧里剩下的運(yùn)算符全放入結(jié)果列表
    while not opStack.isEmpty():
        postfixList.append(opStack.pop())
    # 返回拼接后的后序表達(dá)式字符串
    return " ".join(postfixList)
print(infixToPostfix("A + B * C"))
# A B C * +
print(infixToPostfix("( A + B ) * ( C + D )"))
# A B + C D + *

計(jì)算后序表達(dá)式

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

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

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

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

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

過程如圖所示：

需要特別注意的是：?

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

用代碼實(shí)現(xiàn)后序表達(dá)式計(jì)算過程：?

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

步驟：

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

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

3.從左往右掃描這個(gè)標(biāo)記列表：

(1) 如果標(biāo)記是操作數(shù)，將其轉(zhuǎn)換成整數(shù)(因?yàn)楫?dāng)前是字符)并且壓入 operandStack 棧中

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

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

為了方便運(yùn)算，我們定義了輔助函數(shù) doMath 。它接受一個(gè)運(yùn)算符和兩個(gè)操作數(shù)，并進(jìn)行相應(yīng)的運(yù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 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ù) 是運(yùn)算符
            operand2 = operandStack.pop()              # 從棧頂取 操作數(shù)2
            operand1 = operandStack.pop()              # 從棧頂取 操作數(shù)1
            result = doMath(token,operand1,operand2)   # 調(diào)用doMath進(jìn)行運(yùn)算
            operandStack.push(result)                  # 運(yùn)算結(jié)果 入棧
    return operandStack.pop()                          
    # 返回棧內(nèi)元素（遍歷結(jié)束后這個(gè)唯一的元素就是整個(gè)算式的結(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)容! 

最新評(píng)論