利用栈实现综合计算器（中缀表达式 + 数组实现栈）

问题：使用栈完成计算一个表达式的结果，如

思路：使用栈（中缀）完成表达式的计算：

建立两个栈 —— 数栈：存放数据，符号栈：存放运算符。

1. 通过一个 index（索引）来遍历我们的表达式；
2. 如果我们发现是一个数字，就直接入栈
3. 如果扫描到是一个 运算符，需要分情况讨论
   3.1 如果发现当前符号栈为空，则直接入栈；
   3.2 如果符号栈中有符号，则比较两个符号的优先级，如果当前运算符的优先级小于或者等于栈中的操作符，就需要从数栈中 pop 出两个数据、从 符号栈中pop 出一个符号，并进行运算，将运算结果 push 到数栈中，并将当前的运算符入符号栈，如果当前运算符的优先级大于符号栈中栈顶的优先级，则直接将当前的运算符入栈；
4. 当表达式扫描完成，就依次顺序的从数栈中取出两个数据，从符号栈中取出一个符号，进行运算；
5. 直到当数栈中只有一个数字，也就是表达式的结果。

第一步：读取到表达式中的index(0)位置，发现为数字，将其放入到数栈中

第二步：继续往后读取，发现是运算符，查看符号栈中没有数据，则将其入栈

第三步：类比第一步

第四步：类比第二步，不过入栈是因为，当前的符号 * 大于符号栈的栈顶元素 +

第五步：类比第一步

第六步：当前的运算符是 - 而符号栈中栈顶的元素为 * ，- 的优先级小于 * ，则需要从数栈中出两个数据，从符号栈中出一个运算符，并进行运算，然后将运算结果入数栈，并将当前的运算符入符号栈

第七步：2 入数据栈，入栈操作完成

代码实现：

public class Calculator {
    public static void main(String[] args) {
        String expression = "10+20*4-2";
        // 创建两个栈
        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 = ' '; // 将扫描表达式扫描到的值保存到 ch 中
        String num = "";  // 用来拼接多位数的各个位用的
        // 开始扫描 expression 表达式
        while(true){
            // 依次得到 expression 的每一个字符
            ch = expression.charAt(index);
            // 判断 ch 是什么，然后做相应的处理
            if(!Character.isDigit(ch)){ // 判断得到 ch 是运算符
                // 判断符号栈是否为空
                if(!operStack.isEmpty()){ // 判断得到符号栈不为空
                    // 判断当前运算符的优先级 与 符号栈中栈顶运算符优先级的大小关系
                    if(operStack.priority(ch) <= operStack.priority(operStack.peek())){  // 判断得到当前运算符的优先级 小于等于 符号栈中栈顶运算符的优先级
                        // 1. 从数栈中栈顶取出两个数据
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        // 2. 从符号栈栈顶取出一个数据
                        oper = operStack.pop();
                        // 3. 运算得到结果
                        res = numStack.cal(num1, num2, oper);
                        // 4. 将运算结果入数栈
                        numStack.push(res);
                        // 5. 将当前运算符入符号栈
                        operStack.push(ch);
                    }else{  // 判断得到当前运算符的优先级 大于等于 符号栈中栈顶运算符的优先级
                        // 直接入栈
                        operStack.push(ch);
                    }
                }else{  // 判断得到 符号栈为空
                    operStack.push(ch);
                }
            }else{ // 判断得到 ch 是数字
                // 判断 当前数据是否为多位数
                // 即当前扫描的值是数字，但是下一位还是数字
                // 如果是多位数，不能立即入栈。
                num += ch;

                //  1. 如果 ch 已经是 expression 的最后一位，就不用再判断了，直接入栈即可
                if(index == expression.length() - 1){
                    numStack.push(Integer.parseInt(num));
                }else {
                    // 2. 不是 expression 的最后一位
                    if (!Character.isDigit(expression.charAt(index + 1))) {  // 下一位不是数字
                        numStack.push(Integer.parseInt(num));
                        // 注意：如果下一位不再是数字，一定要将拼接数字用的 num 清空
                        num = "";
                    }
                }
            }
            // 每次扫描，index 往后挪一位
            index++;
            // 入栈结束
            if(index >= expression.length()){
                break;
            }
        }
        // 入栈结束，按序（数栈出两，符号栈出一）计算栈中剩下的值
        while(true){
            // 如果符号栈为空，则计算完毕，此时数栈中只剩下一个数值（即为 表达式结果）
            if(operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.cal(num1, num2, oper);
            numStack.push(res);
        }
        System.out.printf("表达式 %s = %d",expression,res);
    }
}

// 我们这里用到的栈是自己用数组实现的栈，也可以自己用 Java 的栈，这样就不用写 push、pop等方法了
class ArrayStack2{
    private int maxSize;
    private int[] stack;
    private int top = -1;

    // 构造器

    public ArrayStack2(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[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("栈空，没有异常");
        }
        return stack[top--];
    }

    // 遍历栈
    public void list(){
        if(isEmpty()){
            System.out.println("栈空");
            return;
        }
        for(int i = top; i >= 0; i--){
            System.out.printf("此时出栈的是 %d",stack[top]);
        }
    }

    // 查看栈顶元素，不取出
    public int peek(){
        if(isEmpty()){
            throw new RuntimeException("栈为空");
        }
        return stack[top];
    }

    // 自定义运算符的优先级目前我们的表达式只能计算 + - * /，若要计算(),只需要在此处 加上 是否为括号的判断
    public int priority(int oper){
        if(oper == '*' || oper == '/'){
            return 1;
        }else if(oper == '+' || oper == '-'){
            return 0;
        }else{
            return -1;
        }
    }

    // 运算
    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;
    }
}

运算结果：

逆波兰计算器（用后缀表达式实现的计算器）