[数据结构与算法]数据结构-栈实现综合计算器（中缀表达式）

package com.example.sgg.data.stack;

/**
 * 栈实现综合计算器（中缀表达式）
 * 说明：输入一个表达式，如：70+2*6-4，点击计算，输入结果
 * Created by 奔跑的蜗牛 on 2021/7/21 0021.
 * 每天学习一点点，每天进步一点点
 *
 * <p>
 * 使用栈完成表达式的计算的思路分析：
 * 1.创建一个数栈，一个符号栈
 * 2.通过一个index索引，来扫描我们的表达式；
 * 3.如果发现是一个数字，就直接入数栈
 * 4.如果发现扫描到运算符，就分如下情况：
 * 4.1如果发现当前的符号栈为空，则直接入栈
 * 4.2如果符号栈有运算符，则比较当前的运算符和符号栈顶的运算符的优先级，
 * 4.2.1如果符号栈顶的运算符优先级高，则从数栈中pop出两个数，从符号栈中pop出一个运算符，
 * 进行运算，运算的结果入数栈，然后将当前的运算符入符号栈；
 * 4.2.2如果符号栈顶的运算符优先级低，就直接入符号栈
 * 5.当表达式扫描完毕，就顺序从数栈和符号栈中pop出相应的数和符号，并运行
 * 6.最后数栈中只有一个数字就是表达式的结果
 * <p>
 * <p>
 * 以下计算器还有bug：如果前面是减号则后面的加减需要变换
 * <p>
 * 课后作业：加入小括号
 */
public class Calculator {

    public static void main(String[] args) {
        //表达式
        String expression = "70+2*6-4";
        int calResult = calResult(expression);

        System.out.printf("表达式 %s=%d", expression, calResult);
    }

    /**
     * 计算功能
     *
     * @param expression 表达式
     * @return 结果
     */
    private static int calResult(String expression) {
        //创建一个数栈，一个符号栈
        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 = ' ';//将每次扫描的结果放到这里
        String keepNum = "";//用于存放数值

        //开始while循环扫描expression
        while (true) {
            ch = expression.substring(index, index + 1).charAt(0);
            if (ArrayStack2.isOper(ch)) {//如果是运算符
                //判断当前符号栈是否为空
                if (!operStack.isEmpty()) {
                    //如果符号栈有符号，就进行比较，如果当前的运算符的优先级小于或等于栈顶的运算符，就从数栈中pop出两个数
                    //再从符号栈中pop出一个符号，进行运算，将得到结果，入数栈，然后将当前的符号入符号栈
                    //否则直接入符号栈
                    if (ArrayStack2.priority(ch) <= ArrayStack2.priority(operStack.peek())) {
                        num1 = numStack.pop();
                        num2 = numStack.pop();
                        oper = operStack.pop();
                        res = ArrayStack2.cal(num1, num2, oper);
                        numStack.push(res);
                        operStack.push(ch);
                    } else {
                        operStack.push(ch);
                    }
                } else {
                    operStack.push(ch);
                }


            } else {
                //思路
                //如果是数，不能直接入数栈，因为有可能多位数运算，因此需要判断后一位是否也是数字
                //因此定义一个变量用于拼接
                keepNum += ch;

                //如果ch已经是最后一位了，则直接入栈
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {

                    //判断下一个字符是否是数字，如果是，则继续扫描，如果是运算符，则直接入栈
                    ch = expression.substring(index + 1, index + 2).charAt(0);
                    if (ArrayStack2.isOper(ch)) {
                        numStack.push(Integer.parseInt(keepNum));
                        keepNum = "";//重要：清空
                    }
                }
            }

            //让index+1,并判断是否扫描到最后
            index++;
            if (index == expression.length()) {
                break;
            }
        }

        //当表达式扫描完毕，就顺序从数栈和符号栈中pop出相应的数和符号，并运算
        while (true) {
            //如果符号栈为空，则代表扫描结束，数栈中最后一个数为结果
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = ArrayStack2.cal(num1, num2, oper);
            numStack.push(res);
        }
        return numStack.pop();
    }
}


//用数组模拟栈
class ArrayStack2 {
    private int maxSize;
    private int[] stack;
    private int top = -1;//表示栈顶，初始值为-1

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

    public boolean isFull() {
        return top == this.maxSize - 1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * 压栈
     *
     * @param value 数据
     */
    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 int peek() {
        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 static int priority(int oper) {
        if (oper == '*' || oper == '/') {
            return 1;
        } else if (oper == '+' || oper == '-') {
            return 0;
        } else {
            return -1; //假定目前的表达式只有加减乘除
        }
    }

    //判断是否是一个运算符
    public static boolean isOper(int val) {
        return val == '*' || val == '/' || val == '+' || val == '-';
    }

    //计算方法
    public static 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;
    }
}