提出問題

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

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

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

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

現在就請出本文的主角!

主角出現

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

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

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

1 2 3 4 * - 5 / + 6 +

這是怎么做到的

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

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

看到現在，是不是還是一頭霧水，所以，一定要堅持往下看! 進行下一步驟。

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

從逆波蘭表達式的左側開始，先找到第一個符號，抽出符號前的兩個數字并計算。

1. 找到符號 `*`, 進行計算 `3 * 4 = 12`, 當前表達式為 `1 2 12 - 5 / + 6 +`
2. 找到符號 `-`, 進行計算 `2 - 12 = -10`, 當前表達式為 `1 -10 5 / + 6 +`
3. 找到符號 `/`, 進行計算 `-10 / 5 = -2`, 當前表達式為 `1 -2 + 6 +`
4. 找到符號 `+`, 進行計算 `1 + -2 = -1`, 當前表達式為 `-1 6 +`
5. 找到符號 `+`, 進行計算 `-1 + 6 = 5`, 得到結果為 `5`

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

我們需要一個做道題

leetcode 150 題目就是關于逆波蘭表達式求值的:

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

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

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

上一道題好像考察不全面

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

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

以上代碼執行后得到的結果是:

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

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