全網(wǎng)最詳細(xì)數(shù)據(jù)結(jié)構(gòu)----中綴轉(zhuǎn)后綴
2022-04-29 13:58:49

最詳細(xì)的中綴轉(zhuǎn)后綴

學(xué)渣們請(qǐng)就座：（不用看別人，說(shuō)的就是你?。?/p>

大家好，我是Dream。此時(shí)此刻我只想說(shuō)：男神可以遲到，但永遠(yuǎn)不會(huì)缺席！那個(gè)男人回來(lái)了?。。?img alt="全網(wǎng)最詳細(xì)數(shù)據(jù)結(jié)構(gòu)----中綴轉(zhuǎn)后綴_字符串_02" data-type="inline" src="https://s9.51cto.com/images/blog/202201/21192102_61ea971e9e6ee29622.gif" style="width: 48px; visibility: visible; height: 48px;" title="在這里插入圖片描述"/>

最近眼發(fā)炎了，非常難受，但這不會(huì)阻止我為大家更新文章的，請(qǐng)把 淚目 打在評(píng)論區(qū)?。?！

話不多說(shuō)，今天給大家介紹一下，中綴表達(dá)式如何轉(zhuǎn)后綴表達(dá)式。

現(xiàn)在，肯定會(huì)有學(xué)渣問(wèn)：什么是中綴和后綴表達(dá)式呢？

我只想說(shuō)：你好優(yōu)秀，請(qǐng)前排就坐~

簡(jiǎn)單來(lái)講，中綴表達(dá)式就是我們學(xué)習(xí)數(shù)學(xué)時(shí)的各種表達(dá)式，

such as：（A+B）*C/(D-E)

什么是后綴表達(dá)式呢？就是將運(yùn)算符移動(dòng)到字符串后面，但也不是全部移動(dòng)到后面，當(dāng)然也是有條件和順序的。

我們都知道運(yùn)算符是有優(yōu)先級(jí)的，比如乘號(hào)的優(yōu)先級(jí)就高于加號(hào)的優(yōu)先級(jí)，那就要在同一運(yùn)算區(qū)域下先移動(dòng)乘號(hào)再移動(dòng)加號(hào)，為什莫說(shuō)在同一領(lǐng)域下呢，因?yàn)槲覀兌贾涝谶\(yùn)算中少不了括號(hào)的存在，那么括號(hào)就界定了屬不屬于同一領(lǐng)域下。

算了，不和你們多BB了，舉個(gè)例子吧：

A+B : AB+

A+B *C : ABC *+

(A+B) *(C+D) : AB+CD+ *

emmm,我猜你還是不懂應(yīng)該（僅代表學(xué)渣）

好吧，前兩個(gè)你應(yīng)該懂了吧（不懂的同學(xué)回家默寫三千遍三字經(jīng)）

那我來(lái)講一下第三個(gè)：首先(A+B) *(C+D)可以寫作（(A+B) *(C+D)）沒(méi)有問(wèn)題吧，先看第一層括號(hào)，第一層括號(hào)中只有兩個(gè)小括號(hào)和一個(gè) *，那么好的將最外層右邊的括號(hào)用乘號(hào)替換掉，左邊括號(hào)刪除，即：(A+B) (C+D) *

同理看第二層括號(hào)，同樣方法，運(yùn)算符替換掉右邊括號(hào)，同時(shí)刪除左邊括號(hào)，即：AB +(C+D) *----AB +CD+ *得到了最終答案， 是不是very easy？那你會(huì)用代碼表示嗎？？？哈哈哈，繼續(xù)！

首先調(diào)用棧和string：

from pythonds3.basic import Stack
import string

定義一個(gè)函數(shù)：

def infix_to_postfix(infix):
    """將中序表達(dá)式轉(zhuǎn)化為后序表達(dá)式，核心思想"""

這里定義了一個(gè)棧來(lái)儲(chǔ)存運(yùn)算符，一個(gè)列表來(lái)儲(chǔ)存得到的表達(dá)式。

最后將得到的列表用join函數(shù)合并成一個(gè)字符串

當(dāng)出現(xiàn)括號(hào)左時(shí)入棧，字符串照常輸出在列表中，運(yùn)算符繼續(xù)入棧，當(dāng)出現(xiàn)有括號(hào)時(shí)運(yùn)算符出棧，直至遇到最初的左括號(hào)才停止出棧！就這樣循環(huán)往復(fù)遍歷，直至遍歷結(jié)束。

in_list = infix.split()  # 將字符串變?yōu)榱斜恚⒁猓斎霑r(shí)需要空格隔開單個(gè)元素，例："1 2 3 * 2 3"
    stack1 = Stack()  # 創(chuàng)建空棧，用于存儲(chǔ)遍歷字符串列表的括號(hào)、操作符
    post_list = []  # 創(chuàng)建空列表，用于存儲(chǔ)后序表達(dá)式
    priority = {'*': 3, '/': 3, '+': 2, '-': 2, '(': 1}  # 創(chuàng)建優(yōu)先級(jí)字典
    for elem in in_list:  # 遍歷中序表達(dá)式
        if elem == '(':  # 為左括號(hào)，入棧
            stack1.push(elem)
        elif elem in string.ascii_uppercase:  # 為字符串里的大寫字母，加入空的輸出列表
            post_list.append(elem)
        elif elem == ')':  # 為右括號(hào)，則出棧，添加到輸出列表，直到匹配到左括號(hào)
            token = stack1.pop()
            while token != '(':
                post_list.append(token)
                token = stack1.pop()
        else:  # 為操作符，則判斷棧中是否有更高優(yōu)先級(jí)的操作符，有則出棧，無(wú)則添加到列表尾部，
            while (not stack1.is_empty()) and (priority[stack1.peek()] >= priority[elem]):
                post_list.append(stack1.pop())
            stack1.push(elem)  # 若放到列表尾部，則棧永遠(yuǎn)不會(huì)有操作符
    while not stack1.is_empty():  # 若棧不為空，則彈出到后續(xù)表達(dá)式列表（即優(yōu)先級(jí)低的放最后）
        post_list.append(stack1.pop())

    return ''.join(post_list)  # 將列表連在一起
if __name__ == '__main__':
print(infix_to_postfix("A * B + ( C + D ) * ( E - F )"))

emmm，這就是今天我和大家分享的東西了。

如果你喜歡的話，就不要吝惜你的一鍵三連了~