提出問題

假如需要你將兩個已知的數(shù)字相加或者相乘，用代碼表達(dá)出來是不是非常的 easy。再假如給出的是類似 1+1 由一個符號兩個數(shù)字組成的字符串，要求出它的結(jié)果，可以用 split() 函數(shù)分割字符串后進(jìn)行計算，也是沒有多少難度。

那就再升級一步，如果這個字符串不止有兩個數(shù)字和一個符號，是一個包含加減乘除和括號的復(fù)雜算術(shù)表達(dá)式呢?比如下面的一個算術(shù)表達(dá)式:

1 + ( 2 - 3 * 4 ) / 5 + 6

我們可以使用 棧 來完成這個算術(shù)表達(dá)式的計算。創(chuàng)建兩個棧分別存放數(shù)字和符號，然后通過符號間的優(yōu)先級關(guān)系判斷是否前一個符號是否可以計算。具體方法在文章 224. 基本計算器│leetcode 已經(jīng)進(jìn)行了詳細(xì)的解析，本文就不再重復(fù)解析這種方法了，想要了解的小伙伴可以點擊鏈接查看文章。

現(xiàn)在就請出本文的主角!

主角出現(xiàn)

本文的主角叫 逆波蘭表達(dá)式，也叫后綴表達(dá)式。后者這個比較通俗的名字很明確的表示了自己的含義，意思是計算的符號在要計算的兩個數(shù)字之后。

我們常用的算術(shù)表達(dá)式是中綴表達(dá)式，計算符號在兩個數(shù)字之間。在現(xiàn)實中基本沒有直接給出一個逆波蘭表達(dá)式的場景，也就意味著必須先將中綴表達(dá)式轉(zhuǎn)換成逆波蘭表達(dá)式。

我們使用上面的例子，可以先看看轉(zhuǎn)換成逆波蘭表達(dá)式是什么樣子?

1 2 3 4 * - 5 / + 6 +

這是怎么做到的

好奇怪的一串字符，它是怎么轉(zhuǎn)化來的呢?它真的能用來計算嗎?我們先來解析一下第一個問題：

中綴表達(dá)式:
1 + ( 2 - 3 * 4 ) / 5 + 6
第一步:
所有算術(shù)步驟加上括號，表明優(yōu)先級
這一步去除了符號與符號間的優(yōu)先級關(guān)系, 計算先后順序依照括號進(jìn)行. 如:乘除要優(yōu)先于加減
( ( 1 + ( ( 2 - ( 3 * 4 ) ) / 5 ) ) + 6 )
第二步: 
將括號內(nèi)的符號移動到被包裹的最內(nèi)層的右括號之后
( ( 1   ( ( 2   ( 3   4 ) * ) -   5 ) / ) +   6 ) +
第三步: 
去掉括號
1 2 3 4 * - 5 / + 6 +

看到現(xiàn)在，是不是還是一頭霧水，所以，一定要堅持往下看! 進(jìn)行下一步驟。

現(xiàn)在肯定要講轉(zhuǎn)換到的逆波蘭表達(dá)式怎么計算了，否則各位讀者老爺都不耐煩的走光了。

從逆波蘭表達(dá)式的左側(cè)開始，先找到第一個符號，抽出符號前的兩個數(shù)字并計算。

1. 找到符號 `*`, 進(jìn)行計算 `3 * 4 = 12`, 當(dāng)前表達(dá)式為 `1 2 12 - 5 / + 6 +`
2. 找到符號 `-`, 進(jìn)行計算 `2 - 12 = -10`, 當(dāng)前表達(dá)式為 `1 -10 5 / + 6 +`
3. 找到符號 `/`, 進(jìn)行計算 `-10 / 5 = -2`, 當(dāng)前表達(dá)式為 `1 -2 + 6 +`
4. 找到符號 `+`, 進(jìn)行計算 `1 + -2 = -1`, 當(dāng)前表達(dá)式為 `-1 6 +`
5. 找到符號 `+`, 進(jìn)行計算 `-1 + 6 = 5`, 得到結(jié)果為 `5`

看完示例，是不是豁然開朗了呢，將表達(dá)式轉(zhuǎn)換成逆波蘭表達(dá)式，可以從左到右，檢索到一個符號就立刻進(jìn)行計算。完全去除了括號的強制優(yōu)先運算和運算符之間的優(yōu)先級關(guān)系。

我們需要一個做道題

leetcode 150 題目就是關(guān)于逆波蘭表達(dá)式求值的:

150. 逆波蘭表達(dá)式求值
根據(jù) 逆波蘭表示法，求表達(dá)式的值。
有效的運算符包括 +, -, *, / 。
每個運算對象可以是整數(shù)，也可以是另一個逆波蘭表達(dá)式。
說明：
- 整數(shù)除法只保留整數(shù)部分。
- 給定逆波蘭表達(dá)式總是有效的。
  換句話說，表達(dá)式總會得出有效數(shù)值且不存在除數(shù)為 0 的情況。
示例 1：
輸入: ["2", "1", "+", "3", "*"]
輸出: 9
解釋: 該算式轉(zhuǎn)化為常見的中綴算術(shù)表達(dá)式為：((2 + 1) * 3) = 9

想要實現(xiàn)逆波蘭表達(dá)式的運算，還是需要引入 – 棧。將數(shù)值元素依次加入棧中，如果遇到符號，則將棧中的最后兩個數(shù)值出棧，注意先后順序，先出棧的在計算時處于符號之后，后出棧的數(shù)值在計算時處于符號之前。計算完成后將得到的數(shù)值入棧。最后，數(shù)值棧中僅保留一個數(shù)值元素，這個就是計算結(jié)果。

class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        數(shù)值棧 = []
        for token in tokens:
            if token not in "+-*/":  # 當(dāng)前元素是數(shù)字
                數(shù)值棧.append(int(token))
            else:
                數(shù)值后 = 數(shù)值棧.pop()
                數(shù)值前 = 數(shù)值棧.pop()
                if token == '+':
                    數(shù)值棧.append(數(shù)值前 + 數(shù)值后)
                elif token == '-':
                    數(shù)值棧.append(數(shù)值前 - 數(shù)值后)
                elif token == '*':
                    數(shù)值棧.append(數(shù)值前 * 數(shù)值后)
                elif token == '/':
                    數(shù)值棧.append(int(數(shù)值前 / 數(shù)值后))
        return 數(shù)值棧.pop()

上一道題好像考察不全面

上題直接給出了逆波蘭表達(dá)式，我們只需要求解即可。那如果只給出一個普通的表達(dá)式，又需要使用逆波蘭表達(dá)式進(jìn)行計算。那使用代碼如何去做呢?

def 中綴表達(dá)式轉(zhuǎn)逆波蘭表達(dá)式(s):
    '''假設(shè) s 是一個僅有數(shù)字和運算符號(包含括號)的有效中綴表達(dá)式'''
    符號棧, 表達(dá)式隊列, 上一字符 = [], [], ''
    # 符號優(yōu)先級(棧中最后一位與當(dāng)前符號進(jìn)行比較)
    符號優(yōu)先級表 = {
        "+": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
        "-": {"+": '>', '-': '>', '*': '<', '/': '<', '(': '<', ')': '>'},
        "*": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
        "/": {"+": '>', '-': '>', '*': '>', '/': '>', '(': '<', ')': '>'},
        "(": {"+": '<', '-': '<', '*': '', '/': '', '(': '<', ')': '='},
        ")": {"+": ' ', '-': ' ', '*': '', '/': '', '(': ' ', ')': ' '},
    }
    for value in s:
        if value not in '+-*/()':  # 是數(shù)字
            if 上一字符 not in '+-*/()':  # 是連續(xù)的數(shù)字
                表達(dá)式隊列.append(表達(dá)式隊列.pop() * 10 + int(value))
            else:
                表達(dá)式隊列.append(int(value))
        else:
            while True:  # 在棧中可能有多個優(yōu)先級更高的符號, 需要遍歷
                if len(符號棧) == 0 or 符號優(yōu)先級表[符號棧[-1]][value] == '<':  # 當(dāng)前符號優(yōu)先級更高, 加入棧
                    符號棧.append(value)
                    break
                elif 符號優(yōu)先級表[符號棧[-1]][value] == '=':  # 結(jié)束符遇到了結(jié)束符
                    符號棧.pop()
                    break
                elif 符號優(yōu)先級表[符號棧[-1]][value] == '>':  # 棧中優(yōu)先級更高, 可計算
                    表達(dá)式隊列.append(符號棧.pop())
        上一字符 = value
    for 符號 in 符號棧:  # 符號棧中可能會剩余一個符號, 直接加入
        表達(dá)式隊列.append(符號棧.pop())
    return 表達(dá)式隊列
if __name__ == "__main__":
    print(中綴表達(dá)式轉(zhuǎn)逆波蘭表達(dá)式('1+(2-3*4)/5+6'))

以上代碼執(zhí)行后得到的結(jié)果是:

[1, 2, 3, 4, '*', '-', 5, '/', '+', 6, '+']

是不是轉(zhuǎn)換成了和 leetcode 150 題一樣的表達(dá)式了? 那么接下來的步驟就不用多言了吧。如果大家對此比較感興趣，想了解更多相關(guān)知識，不妨來關(guān)注一下動力節(jié)點的Java在線學(xué)習(xí)，里面的課程內(nèi)容更加細(xì)致全面，很適合沒有基礎(chǔ)的小白學(xué)習(xí)，希望對大家能夠有所幫助。