介绍

栈(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设备模型（中）之上层容器