資料結構與算法（五）：遞歸和棧實作簡單電腦

一、電腦的計算思路分析

我們以計算

3+8*2-6

這個算式為例：

将算式解析為數字和符号： 3，+，8，*，2，-，6
準備一個用于存放數字的數字棧numStack，還有一個存放運算符号的符号棧symbolStack，下面分别簡稱棧n和棧s
按順序掃描解析後的數字和符号，

如果是數字，就直接入數棧n，

如果是符号，且如果符号棧s為空，就直接入棧，

如果s不為空，就需要比較棧頂符号與目前符号的優先級，再分兩種情況：
- 如果棧頂符号優先級比目前符号大，就從棧n彈出兩個數字，從棧s彈出一個符号，然後進行運算，最後得出的結果再入棧n
- 如果棧頂符号優先級小于或等于目前符号，就将符号入棧s

按照這個流程，掃描完後棧n會留下

3，16，6

這三個數，棧s會留下

+，-

這兩個符号，

然後按順序，棧n彈出兩個數字，棧s彈出一個符号，然後運算得到結果後再入棧n，重複此步驟，最後棧s清空，棧n隻剩一個數字，即為運算結果。

二、代碼實作

我們先來實作一個加減乘除的數電腦：

/**
 * @Author：黃成興
 * @Date：2020-06-25 16:29
 * @Description：使用棧實作一個電腦
 */
public class StackCalculator {

    //數字棧
    public Stack<Integer> numStack = new Stack<>();

    //符号棧
    public Stack<String> symbolStack = new Stack<>();

    /**
     * 根據計算公式運算并輸出結果
     * @param expression 計算公式
     */
    public void calculate(String expression) {
        //用于多位數拼接
        String numStr = "";

        //周遊字元串裡的每一個字元
        for (int i = 0; i < expression.length() ; i++) {
            String ch = expression.substring(i, i + 1);
            
            //檢驗是否數字
            if (ch.matches("[0-9]")) {
                //如果該數字已經是最後一個字元就直接存入數字棧
                if (i == expression.length() - 1){
                    numStack.push(Integer.valueOf(ch));
                }else {
                    //如果不是字元串最後一個字元，就拼接入字元串
                    numStr += ch;
                }
                continue;
            }
            //如果是符号，就把之前拼接的多位數存入數字棧
            numStack.push(Integer.valueOf(numStr));
            numStr = "";
            
            //如果是符号就比較符号優先級
            if (isFrist(ch)){
                //如果目前符号與符号棧棧棧頂符号優先或者平級就入棧
                symbolStack.push(ch);
            }else {
                //否則就從棧中取兩數字和一個符号先計算
                int num = getCalculateResult();
                //再把計算結果入數棧
                numStack.push(num);
                //再把目前符号入棧
                symbolStack.push(ch);
            }
        }

        //當符号棧為空時，說明計算完成，此時數字棧唯一數字即為結果
        while (!symbolStack.empty()) {
            int result = getCalculateResult();
            numStack.push(result);
        }
        System.out.println("計算結束！結果為：" + numStack.pop());
    }
    
    /**
     * 根據數字和符号運算并傳回結果
     * @param num1 後出棧的數字
     * @param num2 先出棧的數字
     * @param symbol 運算符号
     * @return
     */
    public int getCalculateResult(int num1, int num2, String symbol) {
        int result = 0;
        //根據符号進行運算
        switch (symbol){
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num1 - num2;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num1 / num2;
                break;
                default:
                    throw new RuntimeException("隻支援加減乘除運算！");
        }

        System.out.println(num1 + symbol + num2 + "=" + result);

        return result;
    }

    /**
     * 直接從數棧取兩數字，符号棧取一符号進行計算
     * @return
     */
    public int getCalculateResult() {
        int num1 = numStack.pop();
        int num2 = numStack.pop();
        String symbol = symbolStack.pop();
        int result = getCalculateResult(num2, num1, symbol);
        return result;
    }

    /**
     * 比較符号和目前符号棧頂符号的優先級。
     * 如果目前符号優先級小于符号棧棧頂符号的優先級，就傳回false，否則傳回true
     * 如果目前符号棧為空，直接傳回true
     * @param symbol
     * @return
     */
    public boolean isFrist(String symbol) {
        //判斷目前符号棧是否為空
        if (symbolStack.empty()) {
            return true;
        }
        //取出并放回棧頂符号
        String stackSymbol = symbolStack.pop();
        symbolStack.push(stackSymbol);

        //棧頂符号的優先級
        int stackSymbolGrade = getSymbolGrade(stackSymbol);
        //目前符号的優先級
        int symbolgrade = getSymbolGrade(symbol);

        return symbolgrade > stackSymbolGrade;
    }

    /**
     * 根據符号傳回符号的優先級
     * @param symbol
     * @return 加減傳回0，乘除傳回1
     */
    public int getSymbolGrade(String symbol) {
        int grade;
        if ("+".equals(symbol) || "-".equals(symbol)) {
            grade = 0;
        } else if ("*".equals(symbol) || "/".equals(symbol)) {
            grade = 1;
        }else {
            throw new RuntimeException("不支援的操作符類型：" + symbol);
        }
        return grade;
    }
}

現在輸入運算公式調用

calculate()

函數即可得出結果，但是目前這個電腦仍然還有緻命問題沒有解決：

當連續乘除時無法識别，比如：

2*3*3+3

會被識别為

(2*3)*(3+3)

，

這個問題下面我們将用遞歸來解決。

三.、使用遞歸解決連乘問題

我們分析主函數

calculate()

中關于比較符号的代碼片段：

//如果是符号就比較符号優先級
if (isFrist(ch)){
    //如果目前符号與符号棧棧棧頂符号優先或者平級就入棧
    symbolStack.push(ch);
}else {
    //否則就從棧中取兩數字和一個符号先計算
    int num = getCalculateResult();
    //再把計算結果入數棧
    numStack.push(num);
    //再把目前符号入棧
    symbolStack.push(ch);
}

可以知道主要問題在于運算符的比較隻能進行一次，實際上可能會有連需乘除的情況。

舉個例子，要計算

1*2*3*4+3

，+入棧前，數字棧有1234，符号棧有三個*：

加号入棧前，取出第一個乘号比較，發現乘法優先，于是取出4和3乘後得12，把12入數棧
此時數棧有1，2和12，符号棧有兩個*，然後重複步驟1過程，再把乘号取出一個進行比較......
步驟2結束後數字棧有1和24，符号棧還有一個*，于是再重複步驟1過程.....
最終，符号棧沒有比+更優先的符号了，于是加号入棧

以此類推，無論有多少個乘号，實際上的代碼都是重複執行步驟1，直到滿足進入步驟4的條件時結束。

如果我們把步驟1提取成一個函數，讓他執行結束後再調用自己，有幾個乘号就讓他自己調用幾次，那麼等到滿足步驟4的條件時，也就說明套娃到底了，這時就可以結束調用傳回結果。

按照這個思路，我們把原先的代碼提取成一個遞歸方法：

/**
 * 使用遞歸解決連乘或連除問題
 * @param symbol
 */
private void compareAndOperation(String symbol) {
    //如果是符号就比較符号優先級
    if (isFrist(symbol)){
        //如果目前符号與符号棧棧棧頂符号優先或者平級就入棧
        symbolStack.push(symbol);
        return;
    }else {
        //否則就從棧中取兩數字和一個符号先計算
        int num = getCalculateResult();
        //再把計算結果入數棧
        numStack.push(num);

        //遞歸，繼續比較上一個是否與目前符号的優先級
        compareAndOperation(symbol);
    }
}

現在就能計算連續乘除的情況了！

四.完整代碼

/**
 * @Author：黃成興
 * @Date：2020-06-25 16:29
 * @Description：使用棧實作一個電腦
 */
public class StackCalculator {

    //數字棧
    public Stack<Integer> numStack = new Stack<>();

    //符号棧
    public Stack<String> symbolStack = new Stack<>();

    /**
     * 根據計算公式運算并輸出結果
     * @param expression 計算公式
     */
    public void calculate(String expression) {
        //用于多位數拼接
        String numStr = "";

        //周遊字元串裡的每一個字元
        for (int i = 0; i < expression.length() ; i++) {
            String ch = expression.substring(i, i + 1);
            //檢驗是否數字
            if (ch.matches("[0-9]")) {
                //如果該數字已經是最後一個字元就直接存入數字棧
                if (i == expression.length() - 1){
                    numStack.push(Integer.valueOf(ch));
                }else {
                    //如果不是字元串最後一個字元，就拼接入字元串
                    numStr += ch;
                }
                continue;
            }
            //如果是符号，就把之前拼接的多位數存入數字棧
            numStack.push(Integer.valueOf(numStr));
            numStr = "";

            //如果是符号就比較符号優先級并進行計算和入棧操作
            compareAndOperation(ch);
        }

        //當符号棧為空時，說明計算完成，此時數字棧唯一數字即為結果
        while (!symbolStack.empty()) {
            int result = getCalculateResult();
            numStack.push(result);
        }
        System.out.println("計算結束！結果為：" + numStack.pop());
    }

    /**
     * 使用遞歸解決連乘或連除問題
     * @param symbol
     */
    private void compareAndOperation(String symbol) {
        //如果是符号就比較符号優先級
        if (isFrist(symbol)){
            //如果目前符号與符号棧棧棧頂符号優先或者平級就入棧
            symbolStack.push(symbol);
            return;
        }else {
            //否則就從棧中取兩數字和一個符号先計算
            int num = getCalculateResult();
            //再把計算結果入數棧
            numStack.push(num);

            //遞歸，繼續比較上一個是否與目前符号的優先級
            compareAndOperation(symbol);
        }
    }

    /**
     * 根據數字和符号運算并傳回結果
     * @param num1 後出棧的數字
     * @param num2 先出棧的數字
     * @param symbol 運算符号
     * @return
     */
    public int getCalculateResult(int num1, int num2, String symbol) {
        int result = 0;
        //根據符号進行運算
        switch (symbol){
            case "+":
                result = num1 + num2;
                break;
            case "-":
                result = num1 - num2;
                break;
            case "*":
                result = num1 * num2;
                break;
            case "/":
                result = num1 / num2;
                break;
                default:
                    throw new RuntimeException("隻支援加減乘除運算！");
        }

        System.out.println(num1 + symbol + num2 + "=" + result);

        return result;
    }

    /**
     * 直接從數棧取兩數字，符号棧取一符号進行計算
     * @return
     */
    public int getCalculateResult() {
        int num1 = numStack.pop();
        int num2 = numStack.pop();
        String symbol = symbolStack.pop();
        int result = getCalculateResult(num2, num1, symbol);
        return result;
    }

    /**
     * 比較符号和目前符号棧頂符号的優先級。
     * 如果目前符号優先級小于符号棧棧頂符号的優先級，就傳回false，否則傳回true
     * 如果目前符号棧為空，直接傳回true
     * @param symbol
     * @return
     */
    public boolean isFrist(String symbol) {
        //判斷目前符号棧是否為空
        if (symbolStack.empty()) {
            return true;
        }
        //取出并放回棧頂符号
        String stackSymbol = symbolStack.pop();
        symbolStack.push(stackSymbol);

        //棧頂符号的優先級
        int stackSymbolGrade = getSymbolGrade(stackSymbol);
        //目前符号的優先級
        int symbolgrade = getSymbolGrade(symbol);

        return symbolgrade > stackSymbolGrade;
    }

    /**
     * 根據符号傳回符号的優先級
     * @param symbol
     * @return 加減傳回0，乘除傳回1
     */
    public int getSymbolGrade(String symbol) {
        int grade;
        if ("+".equals(symbol) || "-".equals(symbol)) {
            grade = 0;
        } else if ("*".equals(symbol) || "/".equals(symbol)) {
            grade = 1;
        }else {
            throw new RuntimeException("不支援的操作符類型：" + symbol);
        }
        return grade;
    }
}