資料結構之字尾表示式求值（java實現）

前記

今天在刷leet code的時候刷到了一道題，字尾表示式（逆波蘭表示式）求值，我花了一會兒寫了一下它的解法。但是今天我不談什麼是字尾表示式，有興趣的同學可以去論壇上看看其他人聊字尾表示式的問題，單就解題來說，我用了最為常規的辦法，應該也是初學者最容易理解的方法寫的，故程式碼數量較多，一定要讀下去哦！

圖解分析

首先我們拿出一個字尾表示式的例子，這裡我直接用力扣上的測試用例。

String[] expression = {"2", "1", "+", "3", "*"}; 
//其轉化為中綴表示式就是 ((2 + 1) * 3) = 9

對於字尾表示式求值，我們有這樣一個規則：

1. ==遇到數位則入棧。==
2. ==遇到算符則取出棧頂兩個數位進行計算，並將結果壓入棧中。==

我相信有很多同學會有疑惑為什麼直接接給出了這個規則，怎麼來的這個規則，其實我也會有這樣的疑惑，但是我覺得有可能是因為計算機的工作原理，棧的工作原理所知，以前的程式設計師可能就總結出了很多規律供我們使用。實際上我們不用事事都去追根溯源，要學會使用工具和思考，該深思的地方才去深思，避免重複造輪子。

通過理解規則我們首先能想到的是，這個題我們應該要用到棧（Stack），所以我嘗試用圖的方式來演示該工作過程。

第一步：

{「2」, 「1」, 「+」, 「3」, 「*」}

首先遍歷的是第一個元素「2」，此時是數位，直接入棧。

在這裡插入圖片描述

第二步：

{「2」, 「1」, 「+」, 「3」, 「*」}

遍歷下一個元素「1」依舊是數位，也是直接入棧。
在這裡插入圖片描述

第三步：

{「2」, 「1」, 「+」, 「3」, 「*」}

繼續遍歷下一個元素「+」，此時我們遇到了規則裡面的第二個條件，不是數位了，我們將從棧中彈出兩個數位，進行運算，也就是==1 和 2==進行1+2=3，並將3入棧。

在這裡插入圖片描述

第四步：

{「2」, 「1」, 「+」, 「3」, 「*」}

遍歷到第四個元素「3」，直接入棧。

在這裡插入圖片描述

第五步：

{「2」, 「1」, 「+」, 「3」, 「*」}

遍歷最後一個元素「*」，此時又要從棧裡面彈出兩個數位，進行運算，也就是3*3=9,再將9入棧。

在這裡插入圖片描述

當遍歷完連結串列中所有元素時，棧中的唯一的一個數位即為最終的運算結果。

接下來，我們準備進行程式碼實現。

程式碼實現

我們首先定義一個方法對彈出來的數位進行運算。

值得注意的是，在字尾表示式求值時，從棧中彈出來的數，越靠近棧底的數，就要作為被減數，被除數

程式碼如下：

 /**
     * 該方法用於計算
     */
    public static int cal(int num1,int num2,String oper){
        int result = 0;
        switch (oper){
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num2 - num1;  //靠近棧底的做被減數
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num2 / num1; //靠近棧底的做被除數
                break;
            default:
                break;
        }
        return result;
    }

然後還需要定義一個用於遍歷字元陣列，完成入棧彈棧操作的方法

程式碼如下：

public static int calculate(List<String> ls){
        Stack<String> stack = new Stack<>();
        for (String l : ls) {
            if (l.matches("-?\\d+")){//正規表示式匹配數位
                stack.push(l);
            }else{
                String num1 = stack.pop();
                String num2 = stack.pop();
                int calculate = cal(Integer.parseInt(num1), Integer.parseInt(num2), l);
                stack.push(String.valueOf(calculate));
            }
        }
        return Integer.parseInt(stack.pop());
    }

在對數位進行判別的時候我採用了正規表示式，並考慮到可能為多位數，負數的情況，不理解的同學可以去了解一下正規表示式。

最後就是測試了：

 @Test
    public void test() {
        //定義一個逆波蘭表示式
        String[] surffixExpression = {"2", "1", "+", "3", "*"};
        int result = calculate(surffixExpression);
        System.out.println(result);

    }

後記

至此，字尾表示式的求值就完成了，此方法我認為是初學者最容易理解的方法，不懂的同學可以多畫圖去理解，一邊畫圖一邊思考，演演算法題畫圖還是很重要的，動起來，一起學習。