[数据结构与算法]Java数据结构Day10--栈实现个位数计算器

实现的代码很简单,注释里都写得很清楚,主要的是个思路

输入一个字符串,例如"1*9+5-6*8",怎么让他们按照先乘除后加减去计算?这个才是难点,想通了代码逻辑就很简单.

有以下的一个逻辑.
先创建两个栈,一个数字栈stack1 用来存放数字,一个操作符栈stack2 用来存放操作符

1.遍历字符串中的各个字符

2.如果是数字,就直接push进数字栈;

3.如果是操作符,先判断操作符栈是否为空,
? ?????????如果为空,直接push进操作符栈;
? ?????????如果不为空,进行优先级的判断;
? ?????????????????如果当前的操作符优先级小于等于操作符栈顶的操作符(说明栈顶的操作符应该被先使用)
? ?????????????????????????就从数字栈中依次pop出两个数字,从操作符栈pop出一个操作符,进行计算,将得到的值push回数字栈
? ? ? ? ? ?????????如果当前的操作符优先级大于操作符栈顶的操作符(说明当前的操作符应该被先使用)
? ? ? ? ? ? ? ? ? ?????????就直接push进操作符栈

4.字符串遍历结束之后
? ?就重复从数字栈中依次pop出两个数字,从操作符栈pop出一个操作符,进行计算,将得到的值push回数字栈
? ?直到数字栈中只剩下一个数字,该数字便是结果值.

整体代码(个位数之间的计算)

import java.util.Scanner;

public class Calculator {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入计算表达式:");
        String question = scanner.next();
        ArrayStack_New arrayStack_num = new ArrayStack_New(question.length() + 1);
        ArrayStack_New arrayStack_operator = new ArrayStack_New(question.length() + 1);
        int num1,num2;
        char operator;
        for (int i = 0; i < question.length(); i++) {
            int x = question.charAt(i);
            if (ArrayStack_New.isOperator(x)){
                //如果是操作符,如果操作符栈为空,就直接入栈,否则比较优先级
                if (arrayStack_operator.top != -1){
                    //不为空,比较优先级
                    if (ArrayStack_New.priority(x) <= ArrayStack_New.priority(arrayStack_operator.array[arrayStack_operator.top])){
                        //新加入的小于等于,就要计算了
                        num1 = arrayStack_num.pop();
                        num2 = arrayStack_num.pop();
                        operator = (char) arrayStack_operator.pop();
                        int calculate = ArrayStack_New.calculate(num1, num2, operator);
                        arrayStack_num.push(calculate);
                    }
                    //新加入的大于操作符栈内的,直接加入
                    arrayStack_operator.push(x);


                }else{
                    //为空
                    arrayStack_operator.push(x);
                }
            }
            else{
                //如果不是操作符,直接入栈.因为是char变为int,在ascall码上需要-48
                //数字1在char中是49,数字2在char中是50
                arrayStack_num.push(x-48);
            }
        }
        //运行完之后,将栈中的数字与操作符进行计算,直到数字栈中仅剩一个数字
        while (arrayStack_num.top != 0){
            num1 = arrayStack_num.pop();
            num2 = arrayStack_num.pop();
            operator = (char) arrayStack_operator.pop();
            System.out.println(operator);
            int calculate = ArrayStack_New.calculate(num1, num2, operator);
            arrayStack_num.push(calculate);
        }
        System.out.println(arrayStack_num.pop());
    }
}
//
class ArrayStack_New{
    int maxSize;
    int[] array;
    //栈顶指针默认指向-1,当有数据push后,top++,指向0号位
    int top = -1;
    public ArrayStack_New(int maxSize) {
        this.maxSize = maxSize;
        array = new int[maxSize];
    }
    public void push(int num){
        if (top == maxSize - 1){
            System.out.println("栈满,无法添加");
            return;
        }
        array[++top] = num;
    }
    public int pop(){
        if (top == -1){
            System.out.println("栈空,无法出栈");
            return -9999999;
        }
        return array[top--];
    }
    public void popall(){
        if (top == -1){
            System.out.println("栈空,无法出栈");
            return;
        }
        int i = 1;
        while (top != -1){
            System.out.println("第" + i++ + "个为" + array[top--]);
        }
    }
    public void showall(){
        if (top == -1){
            System.out.println("栈空,无法出栈");
            return;
        }
        for (int i = 0; i <= top; i++) {
            System.out.println("第" + i + "个为" +array[i]);
        }
    }
    // TODO: 2021/12/3 针对计算器代码做的提升
    /*
    * @Author: 徐一闪_BigData
    * @Description: 判断优先级
    * @Para: [operation] 操作符
    * @Date: 20:50 2021/12/3
    */
    public static int priority(int operator){
        //char字符可以转为int型,依据ascall码表
        if ('*' == operator || '/' == operator){
            return 1;
        }
        if ('+' == operator || '-' == operator){
            return 0;
        }
        return -1;
    }
    /*
    * @Author: 徐一闪_BigData
    * @Description: 判断是否为操作符
    * @Para: [char] 读取到的字符
    * @Date: 20:56 2021/12/3
    */
    public static boolean isOperator(int value){
        return value == '+' || value == '-' || value == '*' || value == '/';
    }
    /*
    * @Author: 徐一闪_BigData
    * @Description:计算函数
    * @Para: [int,int] 第一个弹出的数为num1,第二个弹出的数为num2
    * @Date: 21:00 2021/12/3
    */
    public static int calculate(int num1,int num2,char operator){
        switch (operator){
            case '+':
                return num1 + num2;
            //因为要用要用后弹出的减去先弹出的,减数是先进栈的,所以后出,所以是num2
            case '-':
                return num2 - num1;
            case '*':
                return num1 * num2;
            case '/':
                return num1 / num2;
        }
        // 因为上面已经包含了所有可能性,所以这个return不会被用到,但是不写会报错
        return 0;
    }
}