# 棧(Stack)

## 實際需求
請輸入一個表達式
計算 `7*2*2-5+1-5+3-3`

**請問: 計算機底層是如何運算得到結果的?**
對計算機而言，它接收到的就是一個字串，我們需要將之解析為運算元、運算子，還得考慮優先權。

## 棧的介紹
1. 先進後出(FILO)的有序列表
2. 是限制線性表中元素的插入和刪除只能在線性表的同一端進行的一種特殊線性表。允許插入和刪除的一端，為變化的一端，稱為棧頂(top)，另一端為固定的一端，稱為棧底(bottom)。
3. 入棧稱為PUSH，出棧稱為POP，PUSH和POP的順序和現實生活中堆書本是一樣的。


## 棧的應用場景
1. 子程序的調用：在跳往子程序前，會先將下個指令的地址存在棧中，直到子程序執行完後再將地址取出，以回到原來的程序中。
2. 處理遞歸調用：和子程序的調用類似，只是除了儲存下一個指令的地址外，也將參數、區域變數等數據存入到棧中。
3. 表達式的轉換[中綴表達式轉後綴表達式]與求值
4. 二元樹的遍歷
5. 圖形的深度優先搜尋法(DFS)

## 棧的快速入門

### 思路分析
1. 使用陣列來模擬棧
2. 定義一個top 來表示棧頂，初始化為-1
3. 入棧的操作，當有數據加入到棧時，`top++; stack[top] = data;`
4. 出棧的操作，int value = `stack[top];top--, return value`

import java.util.Scanner;

public class ArrayStackDemo {
    public static void main(String[] args) {
        ArrayStack arrStack = new ArrayStack(4);
        String key = "";
        boolean loop = true;
        Scanner sc = new Scanner(System.in);
        while(loop) {
            System.out.println("s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序");
            key = sc.next();
            switch (key) {
                case "s":
                    arrStack.list();
                    break;
                case "e":
                    sc.close();
                    loop = false;
                    break;
                case "a":
                    System.out.println("請輸入要添加的數據: ");
                    int data = sc.nextInt();
                    arrStack.push(data);
                    break;
                case "d":
                    try {
                        int res = arrStack.pop();
                        System.out.printf("出棧的數據為 %d\n",res);
                        break;
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                default:
                    break;
            }
            
        }
        System.out.println("程序退出!");
    }
}

//定義一個類表示 棧
class ArrayStack {
    private int maxSize; //棧的大小
    private int[] stack; //陣列,模擬棧
    private int top = -1; //棧頂,初始化為-1

    public ArrayStack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //判斷棧滿
    public boolean isFull() {
        return top == maxSize -1;
    }

    //判斷棧空
    public boolean isEmpty() {
        return top == -1;
    }

    //入棧
    public void push(int value) {
        if(isFull()) {
            System.out.println("棧滿");
            return;
        }
        top++;
        stack[top] = value;
    }

    //出棧
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("棧空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //遍歷棧,從棧頂開始顯示數據
    public void list() {
        if(isEmpty()) {
            System.out.println("棧空,沒有數據");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("stack[%d] = %d\n", i , stack[i]);
        }
    }

}

output:

s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
a
請輸入要添加的數據: 
10
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
a
請輸入要添加的數據: 
20
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
a
請輸入要添加的數據: 
30
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
a
請輸入要添加的數據: 
40
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
a
請輸入要添加的數據: 
50
棧滿
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序

s
stack[3] = 40
stack[2] = 30
stack[1] = 20
stack[0] = 10
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
d
出棧的數據為 40
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
d
出棧的數據為 30
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
d
出棧的數據為 20
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
d
出棧的數據為 10
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
d
棧空
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
s
棧空,沒有數據
s(show): 顯示棧 | a(add): 添加數據到棧中 | d(del): 將數據從棧中移出 | e(exit): 退出程序
e
程序退出!

## 棧實現簡易綜合計算機
`7*2*2-5+1-5+3-1 = ?`

### 思路
1. 通過一個index值(索引)，來遍歷我們的表達式
2. 如果發現是數字，直接入數棧；
3. 若為運算子，就分如下情況：
-(A) 如果發現當前的運算子為空，就直接入棧
-(B) 如果符號棧已有運算子，就進行比較，如果當前的運算子優先級小於等於棧中的運算子，就需要從數棧中pop出兩個數，然後再從符號棧中pop出一個運算子，進行運算，將得到的結果再入數棧，然後將當前運算子入符號棧；如果當前的運算子優先級大於棧中的運算子，就直接入符號棧。
4. 當表達式遍歷完畢，就順序的從數棧和符號棧中pop出相應的數和運算子，並運行
5. 最後在數棧只有一個數，就是表達式的結果。

實際入棧順序演示請看視頻 [EP33](https://www.bilibili.com/video/BV16t411g7wa?p=33)。

### 計算過程

**以 `3+2*6-2` 來做示範，正常來說我們的運算順序是3+(2\*6)-2，所以結果為 13
那麼在棧中該如何去計算？**


計算時，需先pop出兩個數再pop出一個運算子，因此會先將`2,12` pop出數棧，再將 `-` pop出符號棧做運算，得出 `12-2 = 10`，將 `10` push進數棧中。

目前數棧中剩下 `10,3` 而符號棧中剩下 `+`。

再將`10,3` pop 出數棧，將 `+` pop出符號棧做運算，將`10+3 = 13`，把 `13` push進數棧中，現在符號棧為空，數棧僅剩一個數，因此結果為 `13`。

> 請將圖片放大觀看

### 程式碼

棧的個位數中綴表示法表達式計算程式碼如下：

public class Calculator {
    public static void main(String[] args) {
        String expression = "3+2*6-2";
        ArrayStack2 numStack = new ArrayStack2(10);
        ArrayStack2 operStack = new ArrayStack2(10);
        
        //定義需要的相關變數
        int index = 0; //用於遍歷
        int num1 = 0,num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' '; //將每次遍歷得到的char保存到ch
        //開始while循環遍歷expression
        while(true) {
            //依次得到expression的每個字符
            ch = expression.substring(index, index+1).charAt(0);
            //若為運算子
            if(operStack.isOper(ch)) {
                //判斷當前符號棧是否為空
                if(!operStack.isEmpty()){
                    //處理當前運算子優先級小於等於棧中運算子優先級
                    if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = numStack.cal(num1, num2, oper);
                        //把運算結果入數棧
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        //當前運算子優先級大於符號棧中運算子優先級
                        operStack.push(ch);
                    }
                } else {
                    //如果為空
                    operStack.push(ch);
                }
            } else { //如果是數，直接入棧
                numStack.push(ch - 48); //ch是字元 要轉為數字 請對照ASCII表 
            }
            //讓 index +1, 並判斷是否遍歷到expression最後
            index++;
            if (index >= expression.length()) {
                break;
            }
        }

        //遍歷完畢,就順序的從數棧和符號棧中pop出相應的數和運算子,並計算
        while(true) {
            //如果符號棧為空,則計算到最後的結果,數棧中只有一個數字[結果]
            if(operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res); //入棧
        }
        //將數棧最後的數pop出來,就是結果
        System.out.printf("表達式 %s = %d",expression, numStack.pop());
    }
}

class ArrayStack2 {
    private int maxSize; //棧的大小
    private int[] stack; //陣列,模擬棧
    private int top = -1; //棧頂,初始化為-1

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[this.maxSize];
    }

    //返回棧頂值
    public int peek() {
        return stack[top];
    }

    //判斷棧滿
    public boolean isFull() {
        return top == maxSize -1;
    }

    //判斷棧空
    public boolean isEmpty() {
        return top == -1;
    }

    //入棧
    public void push(int value) {
        if(isFull()) {
            System.out.println("棧滿");
            return;
        }
        top++;
        stack[top] = value;
    }

    //出棧
    public int pop() {
        if(isEmpty()) {
            throw new RuntimeException("棧空");
        }
        int value = stack[top];
        top--;
        return value;
    }

    //遍歷棧,從棧頂開始顯示數據
    public void list() {
        if(isEmpty()) {
            System.out.println("棧空,沒有數據");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("stack[%d] = %d\n", i , stack[i]);
        }
    }

    //返回運算子的優先級，優先級是programmer來定的
    //優先級使用數字表示，數字越大，則優先級越高
    public int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1; //假定目前的表達式只有 +-*/
        }
    }

    //判斷是不是一個運算子
    public boolean isOper(char val) {
        return val == '+' || val == '-' || val == '*' || val == '/';
    }

    //計算方法
    public int cal(int num1, int num2, int oper) {
        int res = 0; //用於存放計算結果
        switch (oper) {
            case '+':
                res = num1 + num2;
                break;
            case '-':
                res = num2 - num1; //注意順序
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num2 / num1;
                break;
            default:
                break;
        }
        return res;
    }
}

output

表達式 3+2*6-2 = 13

但是，這個code問題還是滿多的，比如最明顯的一點，它只能做**個位數**的+ - * /
現在，我們來完善它，使之能計算多位數。

### 多位數計算

**思路**
1. 當處理多位數時，不能發現是一個數就立即入棧。
2. 在處理數時，需要向expression表達式的index後再看一位，如果是數就繼續遍歷，如果是運算子才入棧。
3. 因此我們需要定義一個變數(字串)，用於拼接

String keepNum = ""; //用於拼接多位數

把本來用於遍歷expression的while循環改良一下，27行是原先的程式碼，改善成28~40行：

//開始while循環遍歷expression
while(true) {
    //依次得到expression的每個字符
    ch = expression.substring(index, index+1).charAt(0);
    //若為運算子
    if(operStack.isOper(ch)) {
        //判斷當前符號棧是否為空
        if(!operStack.isEmpty()){
            //處理當前運算子優先級小於等於棧中運算子優先級
            if(operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                num1 = numStack.pop();
                num2 = numStack.pop();
                oper = operStack.pop();
                res = numStack.cal(num1, num2, oper);
                //把運算結果入數棧
                numStack.push(res);
                operStack.push(ch);
            } else {
                //當前運算子優先級大於符號棧中運算子優先級
                operStack.push(ch);
            }
        } else {
            //如果為空
            operStack.push(ch);
        }
    } else { //如果是數，直接入棧
        // numStack.push(ch - 48); //ch是字元 要轉為數字 請對照ASCII表 
        // 處理多位數
        keepNum += ch;
        //如果ch已經是expression的最後一位，就直接入棧
        if(index == expression.length() - 1) {
            numStack.push(Integer.parseInt(keepNum));
        } else {
            //判斷下一個字符是否為數字
            if(operStack.isOper(expression.substring(index+1, index+2).charAt(0))) {
                numStack.push(Integer.parseInt(keepNum));
                //將keepNum清空
                keepNum = "";
            }
        }
    }
    //讓 index +1, 並判斷是否遍歷到expression最後
    index++;
    if (index >= expression.length()) {
        break;
    }
}

output

表達式 5+6*2-3 = 14
表達式 50+6*2-3 = 59
表達式 500+6*2-3 = 509

## 前中後綴表示法
### 中綴表示法
我們平時常看的運算式就是使用中綴表式法，運算子在數中間：
`(3 + 4) * 5 - 6`

### 前綴表示法
也稱作波蘭表示法(Polish notation)，特點是將運算子放在數字前面：
`- * + 3 4 5 6`

**前綴表示法的計算機求值**

例如：`(3+4)*5-6` 對應的前綴表示法是 `-*+3456`，針對前綴表示法求值步驟如下：
1. 從右至左掃描表達式，將6,5,4,3 push進棧中
2. 遇到 + 運算子，因此彈出3,4 (top棧頂,top-1次頂)，計算出3+4 = 7，將7 push入棧中
3. 接下來是 * 運算子，因此彈出7,5，計算出7*5 = 35，將35 push入棧中
4. 最後是 - 運算子，計算出35-6 = 29，由此得到最終結果
(先彈出的數減去後彈出的數)

### 後綴表示法
也稱作逆波蘭表示法(Reverse Polish notation)，特點是將運算子放在數字後面：
`3 4 + 5 * 6 -`

**後綴表示法的計算機求值**

例如：`(3+4)*5-6` 對應的後綴表示法是 `34+5*6-`，針對後綴表示法求值步驟如下：
1. 從左至右掃描表達式，將3,4 push進棧中
2. 遇到 + 運算子，因此彈出4,3 (top棧頂,top-1次頂)，計算出3+4 = 7，將7 push入棧中
3. 將 5 入棧
4. 接下來是 * 運算子，因此彈出5,7，計算出7*5 = 35，將35 push入棧中
5. 將 6 入棧
4. 最後是 - 運算子，計算出35 - 6 = 29，由此得到最終結果
(後彈出的數減去先彈出的數)

### 為什麼計算機要提供前綴和後綴表示法？

對人來說，中綴表示法很直觀的表現出要計算的內容，但對於計算機來說，中綴表示法並不好操作，因為需要去判斷遇到的運算子優先級和後面的運算子優先級誰高誰低。
就像我們前面實作的例子，因此，在計算結果時往往會將中綴表示法轉為其他表示法操作(一般轉成後綴表示法)。

## 後綴表達式計算機

**需求**
1. 輸入一個後綴表示法，使用棧計算其結果
2. 支持小括號和多位數整數(只針對整數)

首先我們先模擬出一個【個位數(整數)後綴表示法計算機】：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolishNotation {
    public static void main(String[] args) {
        //(3+4)*5-6 => 34+5*6-
        String suffixExpression = "3 4 + 5 * 6 -" ;
        //思路
        //1. 先將"3 4 + 5 * 6 -" => 放到ArrayList中
        //2. 將ArrayList傳遞給一個方法,遍歷ArrayList配合棧完成計算
        List<String> rpnList = getListString(suffixExpression);
        System.out.println("rpnList= " + rpnList);
        int res = calculate(rpnList);
        System.out.println("計算的結果 = " + res);
    }

    //將一個後綴表示法,依次將數字和運算子放入到ArrayList中
    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        List<String> list = new ArrayList<String>();
        for (String ele : split) {
            list.add(ele);
        }
        return list;
    }

    //完成對後綴表示法的運算
    public static int calculate(List<String> ls) {
        //創建棧
        Stack<String> stack = new Stack<String>();
        //遍歷 ls
        for (String item : ls) {
            //使用正則取出數
            if(item.matches("\\d+")) { // +:匹配多位數
                //入棧
                stack.push(item);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if(item.equals("+")) {
                    res = num1 + num2;
                } else if(item.equals("-")) {
                    res = num1 - num2;
                } else if(item.equals("*")) {
                    res = num1 * num2;
                } else if(item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("運算子有誤");
                }
                // 把res入棧
                stack.push(res + "");
            }
        }
        //最後留在stack中的數據為運算結果
        return Integer.parseInt(stack.pop());
    }
}

output:

rpnList= [3, 4, +, 5, *, 6, -]
計算的結果 = 29

**這個code的缺點是什麼呢？**
1. 僅能個位數計算
2. 必須輸入後綴表示法
3. 無法判斷小括號，僅能辨別+ - * /

無法完成我們所要達成的目標，所以我們現在來進行改善。

## 中綴表達式轉為後綴表達式

後綴表示法適合計算機去運算，但是人卻不太容易能夠直接寫出來，尤其是在表達式很長的情況下。因此在開發中，我們需要將中綴表達式轉為後綴表達式。

***!!!(建議先看下面轉換過程圖例示範後再來看具體步驟如何實現。)!!!***

### 具體步驟
1. 初始化兩個棧：運算子棧s1 和 儲存中間結果的棧s2
2. 從左至右掃描中綴表達式
3. 遇到運算元的時候將其push進 s2 中
4. 遇到運算子的時候，比較其與 s1棧頂(top)運算子的優先級：
-1 若 s1 為空，或棧頂運算子為左括號"`(`"，則直接將此運算子push進 s1 中
-2 否則，若優先級比棧頂運算子來的高，也將運算子push進 s1
-3 否則，將 s1 棧頂的運算子pop出並push進s2中，再次轉到(4-1)與s1中心的棧頂運算子相比較
5. 遇到括號時：
-- 如果是左括號 "`(`"，則直接push進s1
-- 如果是右括號 "`)`"，則依次pop s1 棧頂的運算子，並push進 s2，直到遇到左括號為止，此時將這一對括號丟棄
6. 重複步驟 2 至 5，直到表達式結束
7. 將 s1 中剩餘的運算子依次 pop 出並 push進 s2
8. 依次彈出 s2 中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式

光是看到八個步驟和密密麻麻的字大部分人都被勸退了吧？
其實並沒有那麼複雜，接著我會一步一步帶大家理解。

### 轉換過程

舉例說明：將中綴表達式"`1+((2+3)*4)-5`"轉換為後綴表達式
結果為："`1 2 3 + 4 * + 5 -`"


1. 首先 前面的 `1+((2+3` 都沒有什麼問題，直接按順序push進各自的棧中即可。
**\*(s1:運算子棧, s2:運算元棧)**


2. 遇到 `)` 怎麼辦?



3. 接著將 `* 4` push進各自的棧中


4. 再次遇到 `)`


5. 此時遇到 `-` ，現在s1棧中僅有 `+`，`-` 並沒有比 `+` 優先級高，因此將s1棧頂pop出並push到s2，再把 `- 5` push至各自的棧中。


6. 表達式結束，將s1中剩餘的運算子依次pop並push進s2棧中


7. 依次pop出s2中的元素並輸出，結果的逆序即為中綴表達式對應的後綴表達式。


即 `-5+*4+321` 逆序為 `123+4*+5-`。

## 中綴轉後綴表達式計算機

現在，我們將按步驟解釋程式碼的意義，最後會附上完整程式碼。

首先，因為直接對string做操作並不方便，所以我們需要寫一個方法將表達式字串轉為list儲存：

//1. 1+((2+3)*4)-5 => 123+4*+5-
//2. 直接對str進行操作並不方便，因此先將字串轉成一個中綴表示法的list
//3. 即 1+((2+3)*4)-5 => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
String expression = "1+((2+3)*4)-5";
List<String> infixExpressionList = toInfixExpressionList(expression);
System.out.println(infixExpressionList);

//方法：將中綴表達式轉為對應的list
public static List<String> toInfixExpressionList(String s) {
    //定義一個list,存放中綴表達式
    List<String> ls = new ArrayList<String>();
    int i = 0; //用於遍歷expression
    String str; //對多位數的拼接
    char c; //每遍歷一個字符就放入到c

    do{
        //如果 c 非數字, 需要加入到ls
        if((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
            ls.add("" + c);
            i++;
        } else {
            str = ""; //將 str 清空
            while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                str += c; //多位數拼接
                i++;
            }
            ls.add(str);
        }
    } while(i < s.length()); 
    return ls;
}

output

[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]

現在，我們需要將得到的中綴表達式對應的List 轉為 後綴表達式對應的List

//4. 將得到的中綴表達式對應的List => 後綴表達式對應的List
//即 [1,+,(,(,2,+,3,),*,4,),-,5] => [1,2,3,+,4,*,+,5,-] , 小括號被消除掉了
List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
System.out.println(suffixExpressionList); //[1,2,3,+,4,*,+,5,-]

新建一個判斷運算子對應優先級的類

//返回一個運算子對應的優先級
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                break;
        }
        return result;
    }
}

//方法：將得到的中綴表達式對應的list => 後綴表達式的list
public static List<String> parseSuffixExpressionList(List<String> ls) {
    //定義數棧和運算子棧
    Stack<String> s1 = new Stack<String>(); //運算子棧
    //由於s2這個棧在整個過程中沒有push & pop 並且最後我們還需要逆序 因此不使用stack , 直接使用list
    //Stack<String> s2 = new Stack<String>(); 
    List<String> s2 = new ArrayList<String>(); //儲存中間結果

    for (String item : ls) {
        //數, 加入s2
        if(item.matches("\\d+")) {
            s2.add(item);
        } else if(item.equals("(")) { //左括號
            s1.push(item);
        } else if(item.equals(")")) { //右括號 
            while(!s1.peek().equals("(")) { //遇到左括號前將s1 pop到s2
                s2.add(s1.pop());
            }
            s1.pop(); //將左括號消除
        } else {
            //當item的優先級小於等於s1棧頂運算子
            while(s1.size() != 0 && (Operation.getValue(s1.peek()) >= Operation.getValue(item))) {
                s2.add(s1.pop());
            }
            //還需要將item push入棧
            s1.push(item);
        }
    }

    //將s1中剩餘的運算子依次pop出並加入s2
    while(s1.size() != 0) {
        s2.add(s1.pop());
    }

    return s2; //因為是存在list中, 所以按順序輸出就是對應的後綴表達式
}

output

[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
[1, 2, 3, +, 4, *, +, 5, -]

再用前面所寫的後綴表達式計算方法計算出結果

//完成對後綴表示法的運算
public static int calculate(List<String> ls) {
    //創建棧
    Stack<String> stack = new Stack<String>();
    //遍歷 ls
    for (String item : ls) {
        //使用正則取出數
        if(item.matches("\\d+")) { // +:匹配多位數
            //入棧
            stack.push(item);
        } else {
            int num2 = Integer.parseInt(stack.pop());
            int num1 = Integer.parseInt(stack.pop());
            int res = 0;
            if(item.equals("+")) {
                res = num1 + num2;
            } else if(item.equals("-")) {
                res = num1 - num2;
            } else if(item.equals("*")) {
                res = num1 * num2;
            } else if(item.equals("/")) {
                res = num1 / num2;
            } else {
                throw new RuntimeException("運算子有誤");
            }
            // 把res入棧
            stack.push(res + "");
        }
    }
    //最後留在stack中的數據為運算結果
    return Integer.parseInt(stack.pop());
}

System.out.printf("expression = %d",calculate(suffixExpressionList));

output

[1, 2, 3, +, 4, *, +, 5, -]
expression = 16

### 完整程式碼

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolishNotation {
    public static void main(String[] args) {
        //1. 1+((2+3)*4)-5 => 123+4*+5-
        //2. 直接對str進行操作並不方便，因此先將字串轉成一個中綴表示法的list
        //3. 即 1+((2+3)*4)-5 => ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
        String expression = "1+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(expression);
        System.out.println(infixExpressionList); //[1,+,(,(,2,+,3,),*,4,),-,5]

        //4. 將得到的中綴表達式對應的List => 後綴表達式對應的List
        //即 [1,+,(,(,2,+,3,),*,4,),-,5] => [1,2,3,+,4,*,+,5,-] , 小括號被消除掉了
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println(suffixExpressionList); //[1,2,3,+,4,*,+,5,-]

        //計算後綴表達式結果
        System.out.printf("expression = %d",calculate(suffixExpressionList));
    }

    //方法：將得到的中綴表達式對應的list => 後綴表達式的list
    public static List<String> parseSuffixExpressionList(List<String> ls) {
        //定義數棧和運算子棧
        Stack<String> s1 = new Stack<String>(); //運算子棧
        //由於s2這個棧在整個過程中沒有push & pop 並且最後我們還需要逆序 因此不使用stack , 直接使用list
        //Stack<String> s2 = new Stack<String>(); 
        List<String> s2 = new ArrayList<String>(); //儲存中間結果

        for (String item : ls) {
            //數, 加入s2
            if(item.matches("\\d+")) {
                s2.add(item);
            } else if(item.equals("(")) { //左括號
                s1.push(item);
            } else if(item.equals(")")) { //右括號 
                while(!s1.peek().equals("(")) { //遇到左括號前將s1 pop到s2
                    s2.add(s1.pop());
                }
                s1.pop(); //將左括號消除
            } else {
                //當item的優先級小於等於s1棧頂運算子
                while(s1.size() != 0 && (Operation.getValue(s1.peek()) >= Operation.getValue(item))) {
                    s2.add(s1.pop());
                }
                //還需要將item push入棧
                s1.push(item);
            }
        }

        //將s1中剩餘的運算子依次pop出並加入s2
        while(s1.size() != 0) {
            s2.add(s1.pop());
        }

        return s2; //因為是存在list中, 所以按順序輸出就是對應的後綴表達式
    }

    //方法：將中綴表達式轉為對應的list
    public static List<String> toInfixExpressionList(String s) {
        //定義一個list,存放中綴表達式
        List<String> ls = new ArrayList<String>();
        int i = 0; //用於遍歷expression
        String str; //對多位數的拼接
        char c; //每遍歷一個字符就放入到c

        do{
            //如果 c 非數字, 需要加入到ls
            if((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {
                ls.add("" + c);
                i++;
            } else {
                str = ""; //將 str 清空
                while(i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {
                    str += c; //多位數拼接
                    i++;
                }
                ls.add(str);
            }
        } while(i < s.length()); 
        
        return ls;
    }

    //完成對後綴表示法的運算
    public static int calculate(List<String> ls) {
        //創建棧
        Stack<String> stack = new Stack<String>();
        //遍歷 ls
        for (String item : ls) {
            //使用正則取出數
            if(item.matches("\\d+")) { // +:匹配多位數
                //入棧
                stack.push(item);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                if(item.equals("+")) {
                    res = num1 + num2;
                } else if(item.equals("-")) {
                    res = num1 - num2;
                } else if(item.equals("*")) {
                    res = num1 * num2;
                } else if(item.equals("/")) {
                    res = num1 / num2;
                } else {
                    throw new RuntimeException("運算子有誤");
                }
                // 把res入棧
                stack.push(res + "");
            }
        }
        //最後留在stack中的數據為運算結果
        return Integer.parseInt(stack.pop());
    }
}

//返回一個運算子對應的優先級
class Operation {
    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;

    public static int getValue(String operation) {
        int result = 0;
        switch (operation) {
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("運算子有誤");
                break;
        }
        return result;
    }
}

**補充：**

表達式一下有空格一下沒空格怎麼處理？

/**
 * 去除所有空白符
 * @param s
 * @return
 */
public static String replaceAllBlank(String s ){
    // \\s+ 匹配任何空白字符，包括空格、制表符、换页符等等, 等价于[ \f\n\r\t\v]
    return s.replaceAll("\\s+","");
}

想使用浮點數、整數混在一起計算怎麼辦？

/**
 * 判断是不是数字 int double long float
 * @param s
 * @return
 */
public static boolean isNumber(String s){
    Pattern pattern = Pattern.compile("^[-\\+]?[.\\d]*$");
    return pattern.matcher(s).matches();
}

這部分大家自己看著改吧。