栈实现综合计算器(思路分析) [数据结构][Java]

栈实现综合计算器(思路分析)

问题:

计算机底层是如何解决7 * 2 * 2 - 5这样的操作的? 计算机是如何知道执行的先后顺序的?其实计算机底层就是通过了栈来解决这一问题,这里我们就也使用栈内模拟计算机底层的实现方式来实现一个综合计算功能

思路分析:

我们要完成数据的运算,这个时候由于有数据还有操作符,所以这个时候我们就要使用两个栈来完成综合计算功能, 一个是数栈numStack(其中就是放我们的运算式中的数值数据), 一个是符号栈operStack(其中就是放我们的运算式中的符号)

• 那么我们具体要如何实现?

  1. 通过一个index值(索引),来遍历我们的表达式(我们将表达式记录到一个String类型的变量中)

  2. 如果我们发现是一个数字,就直接入数栈

  3. 如果发现扫描到的是一个符号,就分为两种情况来解决

     ①如果发现当前的符号栈为空,就直接让符号入栈

     ②如果发现符号栈中不为空,那么就要进行一个比较,而这里的比较又分为了两种情况:

     1. 如果当前操作符的优先级小于或者等于符号栈中的操作符的优先级, 那么就让数栈中pop出两个数(pop就是我们的出栈的操作) , 再从符号栈中pop出一个符号,进行一个运算,元素之后得到一个结果,并将这个结果入数栈,然后将这个待处理的操作符入符号栈
     2. 如果当前操作符的优先级大于符号栈中的操作符的优先级,那么就直接让这个符号入符号栈即可

  4. 当表达式扫描完毕之后,就顺序的从数栈和符号栈中pop出对应的数和符号,并进行计算,每次都将计算后的结果重新入栈,最后的时候当符号栈中没有元素的时候对应的数栈中就只剩了一个元素,这个元素就是我们的最终运算结果

上面我们为什么是扫描到的符号优先级小于等于符号栈栈顶中的符号的优先级的时候就要先执行一个运算?才能入栈?

因为我们的栈结构是先进后出的一种结构,而我们最后运算的时候就是要将栈中的所有元素全部出栈,这个时候肯定要是出栈的符号的优先级肯定要是从高到底的,所以这个时候我们也就是要入栈的时候是按照优先级从第到高入栈的 —> 所以一点我们入栈的某个符号的优先级没有符号栈中的标签的优先级高的话,这个时候我们就需要将栈中前面的唯一的比我们待添加符号优先级高的符号进行一个执行,那么要执行这个符号,肯定就要有数值给它执行,那么对应的执行的数值就是我们的数栈中的栈顶元素和次栈顶元素,所以我们就要执行两次出栈的操作,执行了两次出栈操作之后我们就拿到了两个数值,我们对这两个数值进行一个指定的运算就可以了 ----> 执行完指定的运算之后我们的元素的结果立马就要进行入栈的操作(运算结果进入到数栈中), 执行完这个指定的操作之后前面的比我们待添加元素优先级高的符号或者是优先级一样的符号就已经是出栈了,所以这个时候我们再执行符号入栈的操作

• 注意: 因为每次的时候我们即使是优先级相同的符号也是要先将我们的符号栈中的符号进行其对应的运算,所以我们的符号栈中一个优先级的符号就永远都只有一个,而我们总共就只有两个优先级,这个时候如果前面的优先级比较高,这个时候我们将前面执行了之后就入栈总是没有问题的,这个时候最多就是符号栈中会出现多个+ - ,但是符号栈中绝对不可能出现多个* /

补充:

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

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