Java数据结构与算法（四）：栈

浅浅的花香味﹌ 2022-12-10 14:51 184阅读 0赞

## 1. 栈的介绍 ##

1.  栈（stack）是一个先入后出（FILO-First In Last Out）的有序列表
2.  栈是限制性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶（Top），另一端为固定 的一端，称为栈底（Bottom）；
3.  根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除；

**出入栈示意图：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]

## 2. 栈的应用场景 ##

1.  子程序的调用：在跳往子程序前，会将下个指令的地址存到堆栈中，直到子程序执行完后再将地址取出，以回到原来的程序中；
2.  处理递归调用：和子程序的调用类似，只是除了储存下一个指令的地址外，也将参数、区域变量等数据存入堆栈中；
3.  表达式的转换\[中缀表达式转后缀表达式\]与求值（实际解决）
4.  二叉树的遍历
5.  图形的深度优先遍历搜索法

## 3. 数组模拟栈 ##

用数组模拟栈的使用，由于栈是一种有序列表，当然可以使用数组的结构来存储栈的数据内容，下面我们就用数组模拟栈的出栈、入栈等操作。

**示意图**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]  
**代码实现**

package com.lele.stack;
    
    import java.util.Scanner;
    
    /**
     * author: hwl
     * date: 2020/9/27 20:43
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class ArrayStackDemo {
        
    
        public static void main(String[] args) {
        
            // 测试 ArrayStack 是否正确
            // 先创建一个 ArrayStack 对象 表示栈
            ArrayStack stack = new ArrayStack(4);
            String key = "";
            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:表示从栈取出数据（出栈）");
                System.out.println("请输入你的选择");
                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":
                        try {
        
                            int res= stack.pop();
                            System.out.printf("出栈的数据是 %d\n", res);
                        } catch (Exception e) {
        
                            System.out.println(e.getMessage());
                        }
                        break;
                    case "exit":
                        scanner.close();
                        loop = false;
                        break;
                    default:
                        break;
                }
            }
    
            System.out.println("程序退出~~~");
        }
    }
    
    // 定义一个 ArrayStack 表示栈
    class ArrayStack {
        
        private int maxSize; // 栈的大小
        private int[] stack; // 数组，数组模拟栈，数据就放在该数组
        private int top = -1; // 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;
        }
    
        // 入栈 push
        public void push(int value) {
        
            // 先判断栈是否满
            if (isFull()) {
        
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
    
        // 出栈 pop，将栈顶的数据返回
        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]);
            }
        }
    }

## 4. 栈实现综合计算器（中缀表达式） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]  
**代码实现**

package com.lele.stack;
    
    /**
     * author: hwl
     * date: 2020/9/30 7:13
     * version: 1.0.0
     * modified by:
     * description:
     */
    public class Calculator {
        
    
        public static void main(String[] args) {
        
            String expression = "72*2-5+1-5+3-4"; //   如何处理多位数的问题
            // 创建两个栈，数栈，一个符号栈
            ArrayStack2 numStack = new ArrayStack2(10);
            ArrayStack2 operStack = new ArrayStack2(10);
            // 定义需要的相关变量
            int index = 0; //用于扫描
            int num1 = 0;
            int num2 = 0;
            int oper = 0;
            int res = 0;
            char ch = ' '; // 将每次扫描得到 char 保存到ch
            String keepNum = "";// 用于拼接 多位数
            // 开始 while 循环的扫描expression
            while(true) {
        
                // 依次得到 expression 的每一个字符
                ch = expression.substring(index, index+1).charAt(0);
                // 判断 ch 是什么，然后做相应处理
                if (operStack.isOper(ch)) {
        // 如果是运算符
                    // 判断当前的符号栈是否为空
                    if (!operStack.isEmpty()) {
        
                        // 如果符号栈有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中pop出两个数，
                        // 再从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的操作符入符号栈
                        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); // 1+3
                    }
                } else {
          // 如果是数，则直接入数栈
                    // numStack.push(ch - 48); // ?"1+3" '1' => 1
                    // 分析思路
                    // 1、当处理多位数时，不能发现是一个数就立即入栈，因为他可能是多位数
                    // 2、在处理数，需要向expression的表达式的index后再看一位，如果是数就进行扫描，如果是符号才入栈
                    // 3、因此我们需要定义一个变量 字符串，用于拼接
    
                    // 处理多位数
                    keepNum += ch;
    
                    // 如果ch已经是expression的最后一位，就直接入栈
                    if (index == expression.length() - 1) {
        
                        numStack.push(Integer.parseInt(keepNum));
                    } else {
        
                        // 判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，则入栈
                        // 注意是看后一位，不是index++
                        if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {
        
                            // 如果后一位是运算符，则入栈 keepNum = "1"或者 "123"
                            numStack.push(Integer.parseInt(keepNum));
                            // 重要的！！！，keepNum 清空
                            keepNum = "";
                        }
                    }
                }
    
                // 让 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出，就是结果
            int res2 = numStack.pop();
            System.out.printf("表达式 %s = %d", expression, res2);
    
        }
    
    
    }
    
    // 先创建一个栈
    class ArrayStack2 {
        
        private int maxSize; // 栈的大小
        private int[] stack; // 数组，数组模拟栈，数据就放在该数组
        private int top = -1; //top表示栈顶，初始化为-1
    
        // 构造器
        public ArrayStack2(int maxSize) {
        
            this.maxSize = maxSize;
            stack = new int[this.maxSize];
        }
    
        // 增加一个方法，可以返回当前栈顶的值，但不是真正的pop
        public int peek() {
        
            return stack[top];
        }
    
        // 栈满
        public boolean isFull() {
        
            return top == maxSize - 1;
        }
    
        // 栈空
        public boolean isEmpty() {
        
            return top == -1;
        }
    
        // 入栈 push
        public void push(int value) {
        
            // 先判断栈是否满
            if (isFull()) {
        
                System.out.println("栈满");
                return;
            }
            top++;
            stack[top] = value;
        }
    
        // 出栈 pop，将栈顶的数据返回
        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]);
            }
        }
    
        // 返回运算符的优先级，优先级是程序员来确定，优先级使用数字表示
        // 数字越大，则优先级就越高
        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;// res用于存放计算的结果
            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;
        }
    }

## 5. 逆波兰计算器 ##

1.  输入一个逆波兰表达式（后缀表达式），使用栈（Stack），计算其结果；
2.  支持小括号和多位数整数，只支持对整数的计算
3.  思路分析

例如：（3+4）*5-6 对应的后缀表达式就是 3 4 + 5 * 6 - ，针对后缀表达式求值步骤如下：
    1. 从左至右扫描，将3和4压入堆栈；
    2. 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
    3. 将5入栈；
    4. 接下来是X运算符，因此弹出5和7,计算出7X5=35，将35入栈；
    5. 将6入栈；
    6. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果

**代码实现**

## 6. 中缀表达式转换为后缀表达式 ##

**步骤如下**

*  1.初始化两个栈：运算符栈s1和存储中间结果的栈s2；
 *  2.从左至右扫描中缀表达式；
 *  3.遇到操作数时，将其压入s2；
 *  4.遇到运算符时，比较其与s1栈顶运算符的优先级；
    
     *  a. 如果s1为空，或栈顶运算符为 左括号“(”，则直接将此运算符入栈；
     *  b. 否则，若优先级比栈顶运算符的高，也将运算符压入s1；
     *  c. 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-a)与s1中新的栈顶运算符相比较；
 *  5.遇到括号时：
    
     *  a. 如果是左括号“（”，则直接压入s1；
     *  b. 如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此事将这一对括号丢弃；
 *  6.重复步骤2至5，直到表达式的最右边；
 *  7.将s1中剩余的运算符依次弹出并压入s2；
 *  8.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式；

**举例说明**  
将中缀表达式“1+((2+3)\*4)-5”转换为后缀表达式的过程如下：  
结果为：“1 2 3 + 4 \* + 5 -”  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]  
**代码实现**

package com.lele.stack;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    
    /**
     * author: hwl
     * date: 2020/10/2 9:56
     * version: 1.0.0
     * modified by:
     * description: 逆波兰计算器
     */
    public class PolandNotation {
        
    
        public static void main(String[] args) {
        
    
            //完成将一个中缀表达式转成后缀表达式的功能
            //说明
            // 1. 1+((2+3)*4)-5 => 转成 1 2 3 + 4 * + 5 -
            // 2. 因为直接对str进行操作，不方便，因此 先将 1+((2+3)*4)-5 转换成中缀表达式对应的list
            //   即 将 1+((2+3)*4)-5 转换成 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
            // 3. 将得到的中缀表达式对应的list 转换为 后缀表达式对应的list
            //   即 ArrayList [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("中缀表达式对应的list: " + infixExpressionList); // ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
            List<String> suffixExpressionList = parseSuffixExpressionList(infixExpressionList);
            System.out.println("后缀表达式对应的list: " + suffixExpressionList); // ArrayList [1,2,3,+,4,*,+,5,-]
            System.out.printf("expression=%d", calculate(suffixExpressionList)); // 16
    
    
    //        // 先定义逆波兰表达式  数字和符号使用空格隔开
    //        //(3+4)*5-6   => 3 4 + 5 * 6 -
    //        //4*5-8+60+8/2  => 4 5 * 8 - 60 + 8 2 / +
    //        String suffixExpression = "3 4 + 5 * 6 -";
            String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
    //
    //        /**
    //         * 思路：
    //         * 1.先将 "3 4 + 5 * 6 -" 放到ArrayList中
    //         * 2.将ArrayList传递给一个方法，遍历ArrayList配合栈 完成计算
    //         */
    //        List<String> list = getListString(suffixExpression);
    //        System.out.println("list = " + list);
    //        int res = calculate(list);
    //        System.out.println("计算的结果是：" + res);
    
    
        }
    
        /**
         * 将中缀表达式转成对应的list
         * 将 1+((2+3)*4)-5 转换成 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5]
         * @param s  1+((2+3)*4)-5
         * @return
         */
        public static List<String> toInfixExpressionList(String s) {
        
            // 定义一个list，存放中缀表达式对应的内容
            List<String> ls = new ArrayList<String>();
            int i = 0; // 这是一个指针，用于遍历 中缀表达式字符串
            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;
        }
    
        /**
         * 将得到的中缀表达式对应的list 转换为 后缀表达式对应的list
         * 即将 ArrayList [1,+,(,(,2,+,3,),*,4,),-,5] 转化为 ArrayList [1,2,3,+,4,*,+,5,-]
         * @param ls
         * @return
         */
        public static List<String> parseSuffixExpressionList(List<String> ls) {
        
            //定义两个栈
            Stack<String> s1 = new Stack<>(); // 符号栈
            // 说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出，
            // 比较麻烦，因此这里我们不用Stack<String>,而采用 List<String> s2 = new ArrayList<String>();
    //        Stack<String> s2 = new Stack<>(); // 储存中间结果的栈s2
            List<String> s2 = new ArrayList<>();
    
            // 遍历ls
            for (String item : ls) {
        
                // 如果是一个数，加入到s2
                if (item.matches("\\d+")) {
        
                    s2.add(item);
                } else if (item.equals("(")){
        
                    s1.push(item);
                } else if (item.equals(")")) {
        
                    //如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此事将这一对括号丢弃；
                    while (!s1.peek().equals("(")) {
        
                        s2.add(s1.pop());
                    }
                    s1.pop();// 将“（” 弹出s1栈，消除小括号
                } else {
        
                    // 当item的优先级小于等于s1栈顶运算符，将s1栈顶的运算符弹出并加入s2中，再次转到4-a 与s1中新的栈顶运算符相比较
                    // 问题：缺少一个比较优先级高低的方法
                    while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
        
                        s2.add(s1.pop());
                    }
                    // 还需要将item压入栈中
                    s1.push(item);
                }
            }
            // 将s1中剩余的运算符依次弹出并加入s2
            while (s1.size() != 0) {
        
                s2.add(s1.pop());
            }
            return s2; // 因为存放到list，因此按顺序输出就是对应的后缀表达式对应的list
        }
    
        // 将一个逆波兰表达式，依次将数据和运算符 放入到ArrayList 中
        public static List<String> getListString(String suffixExpression) {
        
            // 将 suffixExpression 分割
            String[] split = suffixExpression.split(" ");
            List<String> list = new ArrayList<String>();
            for (String ele : split) {
        
                list.add(ele);
            }
            return list;
        }
    
        /**
         * 逆波兰表达式的运算
         * 1.从左至右扫描，将3和4压入堆栈；
         * 2.遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
         * 3.将5入栈；
         * 4.接下来是X运算符，因此弹出5和7,计算出7X5=35，将35入栈；
         * 5.将6入栈；
         * 6.最后是-运算符，计算出35-6的值，即29，由此得出最终结果
         * @param ls
         * @return
         */
        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 {
        
                    // pop 出两个数，并运算，再入栈
                    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 = 1;
        private static int DIV = 1;
    
        // 写一个方法，返回对应的优先级数字
        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;
        }
    }

## 7. 逆波兰计算器完整版 ##

**功能**

1.  支持 + - \* /；
2.  多位数，支持小数；
3.  兼容处理，过滤任何空白字符，包括空格、制表符、换页符；

**代码实现**

package com.lele.stack;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Stack;
    import java.util.regex.Pattern;
    
    /**
     * author: hwl
     * date: 2020/10/2 19:00
     * version: 1.0.0
     * modified by:
     * description: 逆波兰计算器完整版
     */
    public class ReversePolishMultiCalc {
        
    
        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();
            }
        }
    
    
        /**
         * 匹配 + - * / ()  运算符
         */
        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;
        }
    
        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;
        }
    
        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;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c7afbdbf6b264f89a9a11cd58c06b1cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/09205544a0034ee1b60ca3d3ed8d3ff1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/63979a3255474dda88e8d71c550f2970.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hvdXdhbmxl_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/0bbf50db6d114cef85a80e2790834cc3.png