栈实现综合计算器(升级版,可对多位数操作)) [数据结构][Java]

栈实现综合计算器(升级版)

这里我们来实现多位数的综合计算:

之前的版本的算法中我们只是实现了数值为一位数的综合运算,如果是遇到两位数或者两位数以上的数值我们上述算法就不能实现了

• 那么我们如何实现一位以上的数值的综合运算?

  • 思路分析:
    1. 当处理多位数时,不能发现index是指向了一个数值就立马执行入栈的操作,因为这个时候这个数可能是一个多位数, 我们需要定义一个String类型的变量,刚刚开始的时候这个String类型的变量要为一个空串,然后使用这个空串和每次判断出是数值的数据进行一个拼接的操作
    2. 在处理时,需要判断当前index的下一位还是否是数字,如果还是一个数值,这个时候就继续执行,继续让我们的index++,继续进行拼接, 但是如果下一位不是一个数值而是一个符号,这个时候我们的字符串就要解析为一个整数,然后将这个整数入栈,并且将这个字符串重新置为一个空串,这个时候就可以开始新一轮的入栈操作了
       • 注意: 上面的时候我们是判断当前index指向的下一位是否是一个数值,这个时候index指针是没有移动的,我们只是判断index+1的位置是否是一个数值,如果是数值的时候我们就继续执行,进行index++,然后继续判断index++之后的下一个位置是否是一个数值

具体代码实现:

/**
 * 实现计算器类(升级版 --> 可以处理多位数的情况)
 */
class Calculator2{
    public static void main(String[] args) {
        //创建我们要执行的运算表达式
        String expression = "30+2*6-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; //用于接收每一次算数运算之后的结果
        String keepNum = ""; //这里我们先定义一个字符串变量用于拼接多位数值



        /*
        这个时候注意: 由于扫描的时候我们不知道目前扫描到的数据数值还是一个运算符,但是都是通过charAt()方法获取到的,所以我么都是先使用ch变量来接收
         */
        char ch = ' '; //每次都将扫描得到的char型数据保存到ch变量中

        //while循环开始扫描我们的算数表达式expression
        while(true){
            //一次得到expression中的每一个字符
            ch = expression.charAt(index);

            //判断ch是一个什么,是一个数值还是一个运算符? 并执行相应的操作
            if(operStack.isOper(ch)){ //由于我们是将判断是否为运算符的方法编写到了ArrayStack2类中,所以我们就要使用ArrayStack2类的实例来调用此方法判断ch是否是一个运算符
                //判断符号栈是否为空,如果栈为空,这个时候就直接将我们符号加入到符号栈中
                if(operStack.isEmpty()){
                    operStack.push(ch);
                }else{
                    //如果符号栈中有操作符了,这个时候就要进行一个判断: 判断我们的ch和符号栈栈顶位置的运算符的优先级哪个高
                    //如果ch的优先级高则直接将我们的ch进行一个入栈
                    if(operStack.priority(ch) > operStack.priority(operStack.peek())){
                        operStack.push(ch);
                    }else{
                        //这个时候就是我们的ch的优先级比符号栈中栈顶位置的符号的优先级要高
                        //那么这个时候就要使用符号栈中栈顶位置的符号对我们的数栈中的栈顶位置和次栈顶位置的数据进行一个对应的运算
                        num1 = numStack.pop(); //此时就是我们的符号右边的值
                        num2 = numStack.pop(); //此时就是我们的符号左边的值
                        oper = operStack.pop(); //记录我们的符号栈中出栈的栈顶数据

                        //进行一个运算
                        res = operStack.col(num1,num2,oper);

                        //运算完成之后要让我们的运算结果入数栈,让我们的ch入符号栈
                        operStack.push(ch);
                        numStack.push(res);

                    }
                }
            }else{
                //这个时候不直接入栈,而是继续判断下一位是否是是数值,如果是数值就向下执行,不刷新我们的记录数值的字符串变量
                keepNum += ch;

                //判断下一个字符是不是一个数值,如果是数值就直接跳过,重置字符变量置空的操作
                //如果ch已经是expression(表达式)的最后一位,就直接入栈
                if (index == expression.length() - 1){
                    numStack.push(Integer.parseInt(keepNum));
                }else{
                    if (operStack.isOper(expression.charAt(index + 1))){
                        //如果后一位是运算符,则入栈
                        numStack.push(Integer.parseInt(keepNum));

                        //注意: 每次遇到运算符之后就执行入栈操作,执行了入栈操作之后就这个数值就算是完成扫描了,这个时候我们一定要将keepNum置空
                        keepNum = "";
                    }
                }
            }
            //让index++并且判断index是否是指向了最后
            index++;
            if (index >= expression.length()){
                break;
            }
        }
        //表达式扫描完毕之后,按照顺序从数栈和符号栈中取出数据进行对应的运算
        while(true){
            //如果符号栈为空的时候对应的数栈中就只剩下了一个值,这个值就是我们的最终运算结果
            if (operStack.isEmpty()){
                break;
            }
            num1 = numStack.pop(); //此时就是我们的符号右边的值
            num2 = numStack.pop(); //此时就是我们的符号左边的值
            oper = operStack.pop(); //记录我们的符号栈中出栈的栈顶数据
            res = operStack.col(num1,num2,oper);
            //每次运算之后都要将我们运算的结果入数栈
            numStack.push(res);
        }
        //将数栈中的最后一个值输出(也就是对结果进行一个输出) ---> 我们数栈中剩余的最后一个元素就是我们的运算结果
        int res2 = numStack.pop();
        System.out.printf("表达式%s = %d",expression,res2);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100

问题提出: 为什么字符串变量可以初始化为空字符串 , 而字符变量不可以初始为空字符?

其实是这就是一个规定,java中的字符串变量是一个引用类型变量,底层是使用byte[] (jdk1.9包括之后) 或者 char[] (jdk1.9之前)存储的 , 我们可以创建一个底层数组长度为0的数组,就是一个空数组(注意: 空数组是[], 而不是null, null指的是null),那么也就也就是对应的可以创建一个字符串, 而字符变量是基本数据类型的变量,我们的基本数据类型要给定一个具体的值,比如我们的char类型的变量,就算是给定为一个空格也是要给定的,而不能给定一个空字符

• 字符串是有空字符串的, 但是字符是没有空字符的
  • 我们可以理解为这是一种规定,记下就可以了