介紹

棧(stack)是一個先入後出(FILO-First In Last Out) 的有序清單。
棧(stack) 是限制線性表中元素的插入和删除隻能線上性表的同一端進行的一種特殊線性表。允許插入和删除的一端，為變化的一端，稱為棧頂(Top) ，另一端為固定的一端，稱為棧底(Bottom) 。
根據棧的定義可知，最先放入棧中元素在棧底，最後放入的元素在棧頂，而删除元素剛好相反，最後放入的元素最先删除，最先放入的元素最後删除
圖解【說明出棧(pop) 和入棧(push)】

Java資料結構和算法（五）棧介紹棧的應用場景棧的快速入門棧實作綜合電腦

棧的應用場景

子程式的調用：在跳往子程式前，會先将下個指令的位址存到堆棧中，直到子程式執行完後再将位址取出，以回到原來的程式中。
處理遞歸調用：和子程式的調用類似，隻是除了儲存下一個指令的位址外，也将參數、區域變量等資料存入堆棧中。
表達式的轉換[中綴表達式轉字尾表達式]與求值。
二叉樹的周遊。
圖形的深度優先(depth 一 first)搜尋法。

棧的快速入門

用數組模拟棧的使用，由于棧是一種有序清單，當然可以使用數組的結構來儲存棧的資料内容，下面我們就用數組模拟棧的出棧，入棧等操作。

思路分析

Java資料結構和算法（五）棧介紹棧的應用場景棧的快速入門棧實作綜合電腦

實作棧的思路分析

使用數組來模拟棧
定義一個 top 來表示棧頂，初始化為 -1
入棧的操作，當有資料加入到棧時， top++; stack[top] = data;
出棧的操作， int value = stack[top]; top–, return value

代碼示範

package datastructure.stack;

import java.util.Scanner;

/**
 * @author wsh
 * @date 2020/9/8 3:31 下午
 */
public class ArrayStackDemo {

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(3);
        boolean loop = true;
        Scanner scanner = new Scanner(System.in);
        while (loop) {
            System.out.println("show：顯示棧");
            System.out.println("exit：退出程式");
            System.out.println("push：添加資料入棧");
            System.out.println("pop 從棧頂取出資料");
            String key = scanner.next();
            switch (key) {
                case "show":
                    stack.list();
                    break;
                case "push":
                    System.out.println("請輸入一個數：");
                    int value = scanner.nextInt();
                    stack.push(value);
                    break;
                case "pop":
                    int result = stack.pop();
                    System.out.printf("%d 出棧\n", result);
                    break;
                case "exit":
                    scanner.close();
                    loop = false;
                    break;
                default:
                    break;
            }
        }
    }
}

class ArrayStack {
    /**
     * 棧大小
     */
    private int maxSize;
    /**
     * 數組模拟棧
     */
    private int[] stack;
    /**
     * 棧頂指針
     */
    private int top = -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;
    }

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

    /**
     * 出棧
     *
     * @return 棧頂的值
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧空~~");
        }
        return stack[top--];
    }

    /**
     * 顯示棧（從棧頂開始）
     */
    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]);
        }
    }
}

測試結果:

show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
show
棧空~~
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
push
請輸入一個數：
10
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
push
請輸入一個數：
20
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
push
請輸入一個數：
30
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
push
請輸入一個數：
40
棧滿~~
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
show
stack[2]=30
stack[1]=20
stack[0]=10
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
pop
30 出棧
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
show
stack[1]=20
stack[0]=10
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
push
請輸入一個數：
40
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
show
stack[2]=40
stack[1]=20
stack[0]=10
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
pop
40 出棧
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
pop
20 出棧
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
pop
10 出棧
show：顯示棧
exit：退出程式
push：添加資料入棧
pop 從棧頂取出資料
pop
Exception in thread "main" java.lang.RuntimeException: 棧空~~
	at datastructure.stack.ArrayStack.pop(ArrayStackDemo.java:98)
	at datastructure.stack.ArrayStackDemo.main(ArrayStackDemo.java:31)

棧實作綜合電腦

字首、中綴、字尾表達式

字首表達式(波蘭表達式)

字首表達式又稱波蘭式，字首表達式的運算符位于操作數之前

字首表達式的計算機求值

從右至左掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（棧頂元素和次頂元素），并将結果入棧；重複上述過程直到表達式最左端，最後運算得出的值即為表達式的結果。

例如: (3+4)×5-6 對應的字首表達式就是 - × + 3 4 5 6 , 針對字首表達式求值步驟如下:

1、從右至左掃描，将6、5、4、3壓入堆棧

2、遇到+運算符，是以彈出3和4（3為棧頂元素，4為次頂元素），計算出3+4的值，得7，再将7入棧

3、接下來是×運算符，是以彈出7和5，計算出7×5=35，将35入棧

4、最後是-運算符，計算出35-6的值，即29，由此得出最終結果

中綴表達式

中綴表達式就是常見的運算表達式，如(3+4)×5-6

中綴表達式的求值是人們最熟悉的，但是對計算機來說卻不好操作，是以，在計算結果時，往往會将中綴表達式轉成其它表達式來操作(一般轉成字尾表達式.)。

下面用程式來實作一個中綴表達式的計算：

計算表達式: 20+3*5-10

分析

通過一個 index 值（索引），來周遊表達式。
如果我們發現是一個數字, 就直接入數棧。
如果發現掃描到是一個符号, 就分如下情況：

3.1 如果發現目前的符号棧為空，就直接入棧。

3.2 如果符号棧有操作符，就進行比較, 如果目前的操作符的優先級小于或者等于棧中的操作符，就需要從數棧中pop出兩個數, 在從符号棧中pop出一個符号，進行運算，将得到結果，入數棧，然後将目前的操作符入符号棧，如果目前的操作符的優先級大于棧中的操作符，就直接入符号棧。
當表達式掃描完畢，就順序的從數棧和符号棧中pop出相應的數和符号，并運作。
最後在數棧隻有一個數字，就是表達式的結果。

代碼實作

在這裡說明下，下面代碼隻是簡單實作加減乘除基本計算，為了進一步加深對棧的了解和使用。

package datastructure.stack;

/**
 * @author wsh
 * @date 2020/9/8 3:31 下午
 */
public class Calculator {

    public static void main(String[] args) {
        String expression = "20+3*5-10";
        // 數棧
        ArrayStack2 numStack = new ArrayStack2(10);
        // 符号棧
        ArrayStack2 operStack = new ArrayStack2(10);

        // 需要用到的一些變量
        // 掃描的下标
        int index = 0;
        int num1;
        int num2;
        int oper;
        int res;
        // 記錄每次掃描的結果
        char ch;
        // 用與拼接多位數
        String numStr = "";
        // 表達式掃描
        while (true) {
            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 {
                // 如果是數, 可能是多位數哦
                numStr += ch;
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(numStr));
                } else {
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(numStr));
                        // 清空多位數收集的字元串，友善下次使用
                        numStr = "";
                    }
                }

            }
            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);
        }
        int res2 = numStack.pop();
        System.out.printf("表達式: %s=%d", expression, res2);
    }
}

class ArrayStack2 {
    /**
     * 棧大小
     */
    private int maxSize;
    /**
     * 數組模拟棧
     */
    private int[] stack;
    /**
     * 棧頂指針
     */
    private int top = -1;

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

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

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

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

    /**
     * 出棧
     *
     * @return 棧頂的值
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("棧空~~");
        }
        return stack[top--];
    }

    /**
     * 顯示棧（從棧頂開始）
     */
    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]);
        }
    }

    /**
     * 檢視棧頂的值，不出棧
     */
    public int peek() {
        return stack[top];
    }

    /**
     * 傳回運算符的優先級，數字越大，優先級越高（隻支援 + - * /）
     *
     * @param oper 運算符
     * @return 優先級
     */
    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 = num1 - num2;
                break;
            case '*':
                res = num1 * num2;
                break;
            case '/':
                res = num1 / num2;
                break;
            default:
                break;
        }
        return res;
    }
}

測試結果:

字尾表達式(逆波蘭表達式)

字尾表達式又稱逆波蘭表達式,與字首表達式相似，隻是運算符位于操作數之後。

字尾表達式的計算機求值

從左至右掃描表達式，遇到數字時，将數字壓入堆棧，遇到運算符時，彈出棧頂的兩個數，用運算符對它們做相應的計算（次頂元素和棧頂元素），并将結果入棧；重複上述過程直到表達式最右端，最後運算得出的值即為表達式的結果。

分析

完成一個逆波蘭電腦，要求如下:

輸入一個逆波蘭表達式(字尾表達式)，使用棧(Stack), 計算其結果。
支援小括号和多位數整數，對電腦進行簡化，隻支援對整數的計算。
思路分析：

例如: (3+4)×5-6 對應的字尾表達式就是 3 4 + 5 × 6 - , 針對字尾表達式求值步驟如下:

1．從左至右掃描，将 3 和 4 壓入堆棧；

2．遇到+運算符，是以彈出 4 和 3（4 為棧頂元素，3 為次頂元素），計算出 3+4

的值，得 7，再将 7 入棧；

3．将 5 入棧；

4．接下來是×運算符，是以彈出 5 和 7，計算出 7×5=35，将 35 入棧；

5．将 6 入棧；

6．最後是-運算符，計算出 35-6 的值，即 29，由此得出最終結果

這裡說一下，像這種我們能看懂得表達式： (3+4)×5-6，這是中綴表達式，轉化為字尾表達式為 3 4 + 5 × 6 - 怎麼轉換，這個後面來闡述，這裡先實作怎麼通過棧來計算字尾表達式。

代碼實作

package datastructure.stack;

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

/**
 * @author wsh
 * @date 2020/9/11 11:11 上午
 */
public class PolandNotation {

    public static void main(String[] args) {
        String suffixExpression = "3 4 + 5 * 6 -";
        String[] array = suffixExpression.split(" ");
        List<String> list = arrayToList(array);
        int res = calculate(list);
        System.out.println("計算結果：" + res);
    }

    public static List<String> arrayToList(String[] array) {
        return new ArrayList<>(Arrays.asList(array));
    }

    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        list.forEach(item -> {
            if (item.matches("\\d+")) {
                // 數直接入棧
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num2 + num1;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("運算符錯誤");
                }
                stack.push(String.valueOf(res));
            }
        });
        return Integer.parseInt(stack.pop());
    }
}

測試結果:

中綴表達式轉換為字尾表達式

字尾表達式适合計算式進行運算，但是人卻不太容易寫出來，尤其是表達式很長的情況下，是以在開發中，我們需要将中綴表達式轉成字尾表達式。

具體步驟:

初始化兩個棧：運算符棧s1和儲存中間結果的棧s2；
從左至右掃描中綴表達式；
遇到操作數時，将其壓s2；
遇到運算符時，比較其與s1棧頂運算符的優先級：

如果s1為空，或棧頂運算符為左括号“(”，則直接将此運算符入棧；

否則，若優先級比棧頂運算符的高，也将運算符壓入s1；

否則，将s1棧頂的運算符彈出并壓入到s2中，再次轉到(4-1)與s1中新的棧頂運算符相比較；
遇到括号時：

如果是左括号“(”，則直接壓入s1

如果是右括号“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括号為止，此時将這一對括号丢棄
重複步驟2至5，直到表達式的最右邊
将s1中剩餘的運算符依次彈出并壓入s2
依次彈出s2中的元素并輸出，結果的逆序即為中綴表達式對應的字尾表達式。

例如：将中綴表達式“1+((2+3)×4)-5”轉換為字尾表達式：

Java資料結構和算法（五）棧介紹棧的應用場景棧的快速入門棧實作綜合電腦

代碼示範:

public class PolandNotation {

    public static void main(String[] args) {
        String infixExpression = "10+((2+3)*4)-5";
        System.out.println("中綴表達式為："+infixExpression);
        List<String> infixExpressionList = getInfixExpressionList(infixExpression);
        System.out.println("中綴表達式轉化成list："+infixExpressionList);
        List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
        System.out.println("字尾表達式list："+suffixExpressionList);
        int calculate = calculate(suffixExpressionList);
        System.out.println("計算結果：10+((2+3)*4)-5="+calculate);
    }

    public static List<String> arrayToList(String[] array) {
        return new ArrayList<>(Arrays.asList(array));
    }

    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<>();
        list.forEach(item -> {
            if (item.matches("\\d+")) {
                // 數直接入棧
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num2 + num1;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("運算符錯誤");
                }
                stack.push(String.valueOf(res));
            }
        });
        return Integer.parseInt(stack.pop());
    }

    /**
     * 中綴表達式轉字尾表達式
     * @param infixList 中綴表達式list
     * @return 字尾表達式list
     */
    public static List<String> parseSuffixExpressionList(List<String> infixList) {
        // 符号棧
        Stack<String> s1 = new Stack<>();
        // 中間結果棧
        Stack<String> s2 = new Stack<>();
        // 從左至右掃描中綴表達式
        infixList.forEach(item -> {
            if (item.matches("\\d+")) {
                // 遇到操作數時，将其壓s2
                s2.push(item);
            } else if (item.equals("(")) {
                // 如果是左括号“(”，則直接壓入s1
                s1.push(item);
            } else if (item.equals(")")) {
                // 如果是右括号“)”，則依次彈出s1棧頂的運算符，并壓入s2，直到遇到左括号為止，此時将這一對括号丢棄
                while (!s1.peek().equals("(")) {
                    s2.push(s1.pop());
                }
                // "(" 從s1棧中彈出，消除括号
                s1.pop();
            } else {
                // 遇到運算符時，比較其與s1棧頂運算符的優先級：
                //如果s1為空，或棧頂運算符為左括号“(”，則直接将此運算符入棧；
                //否則，若優先級比棧頂運算符的高，也将運算符壓入s1；
                //否則，将s1棧頂的運算符彈出并壓入到s2中，再次重新與s1中新的棧頂運算符相比較；
                while (s1.size() != 0 && Operation.getValue(item) <= Operation.getValue(s1.peek())) {
                    s2.push(s1.pop());
                }
                s1.push(item);
            }
        });
        // 将s1 符号棧中剩餘的運算符彈出後壓入s2
        while (s1.size() != 0) {
            s2.push(s1.pop());
        }
        // 逆序列印s2，把結果加入list中
        Stack<String> tempStack = new Stack<>();
        s2.forEach(tempStack::push);
        return new ArrayList<>(tempStack);
    }

    /**
     * 掃描中綴表達式，轉化成list
     * @param infixStr 中綴表達式
     */
    public static List<String> getInfixExpressionList(String infixStr) {
        List<String> list = new ArrayList<>();
        int index = 0;
        String str;
        while (index < infixStr.length()) {
            // 不是數 ascll 碼 48 - 57 表示 數字 0-9
            if (infixStr.charAt(index) < 48 || infixStr.charAt(index) > 57) {
                list.add(String.valueOf(infixStr.charAt(index)));
                index++;
            } else {
                // 是一個數
                str = "";
                while (index < infixStr.length() && infixStr.charAt(index) >= 48 && infixStr.charAt(index) <= 57) {
                    str += infixStr.charAt(index);
                    index++;
                }
                list.add(str);
            }
        }
        return list;
    }
}

class Operation {
    private static final int ADD = 1;
    private static final int SUB = 1;
    private static final int MUL = 2;
    private static final int DIV = 2;

    /**
     * 傳回優先級，數字越大，優先級越高
     */
    public static int getValue(String operation) {
        int val = 0;
        switch (operation) {
            case "+":
                val = ADD;
                break;
            case "-":
                val = SUB;
                break;
            case "*":
                val = MUL;
                break;
            case "/":
                val = DIV;
                break;
            default:
                break;
        }
        return val;
    }

}

測試結果:

中綴表達式為：10+((2+3)*4)-5
中綴表達式轉化成list：[10, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
字尾表達式list：[10, 2, 3, +, 4, *, +, 5, -]
計算結果：10+((2+3)*4)-5=25

逆波蘭電腦完整版

功能實作：

支援 + - * / ( )
多位數，支援小數,
相容處理, 過濾任何空白字元，包括空格、制表符、換頁符

代碼實作：

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
import java.util.regex.Pattern;

/**
 * @author jue
 * @date 2020/9/11 23:02
 * @describe
 */
public class ReversePolishMultiCalc {

    /**
     * 比對 + - * / ( ) 運算符
     */
    static final String SYMBOL = "\\+|-|\\*|/|\\(|\\)";
    static final String LEFT = "(";
    static final String RIGHT = ")";
    static final String ADD = "+";
    static final String MINUS = "-";
    static final String TIMES = "*";
    static final String DIVISION = "/";
    /**
     * 加減 + -
     */
    static final int LEVEL_01 = 1;

    /**
     * 乘除 * /
     */
    static final int LEVEL_02 = 2;
    /**
     * 括号
     */
    static final int LEVEL_HIGH = Integer.MAX_VALUE;
    static Stack<String> stack = new Stack<>();
    static List<String> data = Collections.synchronizedList(new ArrayList<String>());

    /**
     * 去除所有空白符
     *
     * @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();
    }

    /**
     * 判斷是不是運算符
     *
     * @param s
     * @return
     */
    public static boolean isSymbol(String s) {
        return s.matches(SYMBOL);
    }

    /**
     * 比對運算等級
     *
     * @param s
     * @return
     */
    public static int calcLevel(String s) {
        if ("+".equals(s) || "-".equals(s)) {
            return LEVEL_01;
        } else if ("*".equals(s) || "/".equals(s)) {
            return LEVEL_02;
        }
        return LEVEL_HIGH;
    }

    /**
     * 比對
     *
     * @param s
     * @throws Exception
     */
    public static List<String> doMatch(String s) throws Exception {
        if (s == null || "".equals(s.trim())) throw new RuntimeException("data is empty");
        if (!isNumber(s.charAt(0) + "")) throw new RuntimeException("data illeagle,start not with a number");
        s = replaceAllBlank(s);
        String each;
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isSymbol(s.charAt(i) + "")) {
                each = s.charAt(i) + "";
                //棧為空，(操作符，或者 操作符優先級大于棧頂優先級 && 操作符優先級不是( )的優先級 及是 )不能直接入棧
                if (stack.isEmpty() || LEFT.equals(each)
                        || ((calcLevel(each) > calcLevel(stack.peek())) && calcLevel(each) < LEVEL_HIGH)) {
                    stack.push(each);
                } else if (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                    //棧非空，操作符優先級小于等于棧頂優先級時出棧入列，直到棧為空，或者遇到了(，最後操作符入棧
                    while (!stack.isEmpty() && calcLevel(each) <= calcLevel(stack.peek())) {
                        if (calcLevel(stack.peek()) == LEVEL_HIGH) {
                            break;
                        }
                        data.add(stack.pop());
                    }
                    stack.push(each);
                } else if (RIGHT.equals(each)) {
                    // ) 操作符，依次出棧入列直到空棧或者遇到了第一個)操作符，此時)出棧
                    while (!stack.isEmpty() && LEVEL_HIGH >= calcLevel(stack.peek())) {
                        if (LEVEL_HIGH == calcLevel(stack.peek())) {
                            stack.pop();
                            break;
                        }
                        data.add(stack.pop());
                    }
                }
                start = i; //前一個運算符的位置
            } else if (i == s.length() - 1 || isSymbol(s.charAt(i + 1) + "")) {
                each = start == 0 ? s.substring(start, i + 1) : s.substring(start + 1, i + 1);
                if (isNumber(each)) {
                    data.add(each);
                    continue;
                }
                throw new RuntimeException("data not match number");
            }
        }
        //如果棧裡還有元素，此時元素需要依次出棧入列，可以想象棧裡剩下棧頂為/，棧底為+，應該依次出棧入列，可以直接翻轉整個 stack 添加到隊列
        Collections.reverse(stack);
        data.addAll(new ArrayList<>(stack));
        System.out.println(data);
        return data;
    }

    /**
     * 算出結果
     *
     * @param list
     * @return
     */
    public static Double doCalc(List<String> list) {
        Double d = 0d;
        if (list == null || list.isEmpty()) {
            return null;
        }
        if (list.size() == 1) {
            System.out.println(list);
            d = Double.valueOf(list.get(0));
            return d;
        }
        ArrayList<String> list1 = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            list1.add(list.get(i));
            if (isSymbol(list.get(i))) {
                Double d1 = doTheMath(list.get(i - 2), list.get(i - 1), list.get(i));
                list1.remove(i);
                list1.remove(i - 1);
                list1.set(i - 2, d1 + "");
                list1.addAll(list.subList(i + 1, list.size()));
                break;
            }
        }
        doCalc(list1);
        return d;
    }

    /**
     * 運算
     *
     * @param s1
     * @param s2
     * @param symbol
     * @return
     */
    public static Double doTheMath(String s1, String s2, String symbol) {
        Double result;
        switch (symbol) {
            case ADD:
                result = Double.valueOf(s1) + Double.valueOf(s2);
                break;
            case MINUS:
                result = Double.valueOf(s1) - Double.valueOf(s2);
                break;
            case TIMES:
                result = Double.valueOf(s1) * Double.valueOf(s2);
                break;
            case DIVISION:
                result = Double.valueOf(s1) / Double.valueOf(s2);
                break;
            default:
                result = null;
        }
        return result;
    }

    public static void main(String[] args) {
        //String math = "9+(3-1)*3+10/2";
        String math = "12.8 + (2 - 3.55)*4+10/5.0";
        try {
            doCalc(doMatch(math));
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

測試結果：

[12.8, 2, 3.55, -, 4, *, +, 10, 5.0, /, +]
[8.600000000000001]

Java資料結構和算法（五）棧介紹棧的應用場景棧的快速入門棧實作綜合電腦

介紹

棧的應用場景

棧的快速入門

思路分析

代碼示範

棧實作綜合電腦

字首表達式(波蘭表達式)

字首表達式的計算機求值

中綴表達式

分析

代碼實作

字尾表達式(逆波蘭表達式)

字尾表達式的計算機求值

分析

代碼實作

中綴表達式轉換為字尾表達式

逆波蘭電腦完整版

繼續閱讀

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

詳解STM32單片機的堆棧

Linux裝置模型（中）之上層容器