目录

1. 课堂思路分析1.1 使用栈计算表达式的思路1.2 举例分析 2. 出现bug的原因分析3. Debug分析3.1 Debug分析3.2 举例分析3.3 改进的完整思路表述 4. 改进的完整代码

1. 课堂思路分析

原视频链接：link.P33.P34

1.1 使用栈计算表达式的思路

1° 通过一个 index 值（索引），来遍历表达式；

2° 如果扫描到的是一个数字, 就直接入numStack；

3° 如果发现扫描到的是一个符号, 需分情况讨论

​ 3.1 如果当前的operStack为空，就直接入operStack；

​ 3.2 如果符号栈有操作符，再进行比较

​ 3.2.1 如果当前的操作符的优先级小于或者等于operStack栈中的操作符， 就需要从numStack中pop出两个数，再从operStack中pop出一个符号，进行运算，将得到的结果放入numStack，然后将当前的操作符放入operStack；

​ 3.2.2 如果当前的操作符的优先级大于栈中的操作符， 直接入符号栈；

4° 当表达式扫描完毕，就顺序的从numStack和operStack中pop出相应的数和符号，进行运算；

5° 最后在numStack只有一个数字，就是表达式的结果。

1.2 举例分析

使用上述思路计算表达式：3+2*6-2

过程分析：

1° 数字 3 入numStack；由于operStack为空，+ 直接入operStack；2入numStack；

2° 由于 * 的优先级高于 +，则 * 直接入operStack；6 入numStack；

3° - 优先级低于 * ，先将 6 、 2 和 * 出栈进行计算，将结果 12 放入numStack；之后 - 入operStack；最后 2 入numStack；此时表达式扫描完毕；

4° 顺序的从numStack和operStack中取出相应的数和符号，进行运算，最后numStack存放的数字 13 即为计算结果。

2. 出现bug的原因分析

目录1.1中表述的思路在计算类似 3-2*6+2 、3-2/6+2 ，这种在 * 和 / 运算符之前的符号是 - 时，存在问题

以计算表达式 3-2*6+2 为例，按照上述思路进行计算，最终结果为：-11，如下图。而正确答案为：-7

其根本原因为：

由于 * 和 / 的运算优先级高于 - ，operStack中 - 运算符会被保存，而由于 - 在运算时，可能需要变号的特性，在上图第三步完成表达式遍历后，之后的运算为 3-(12+2)，但是实际的运算过程应为 3-12+2

3. Debug分析

3.1 Debug分析

如果当前的operStack为空，就直接入operStack；如果当前的操作符的优先级大于operStack栈中的操作符，直接入operStack；**如果当前的操作符的优先级等于operStack栈中的操作符，且当前的操作符为 + 或 - **，直接入operStack；其他情况均需要从numStack中pop出两个数，再从operStack中pop出一个符号，进行运算，将得到的结果放入numStack，然后将当前的操作符放入operStack；

3.2 举例分析

以计算表达式 3-2*6+2-1 为例，按照上述思路进行计算，过程如下图所示

当遍历完整个表达式后，numStack与operStack中存储的数据如4°所示，发现正确的计算过程应该按绿色箭头标注所示，为 3-12+2-1，应该从栈底进行计算

接着3.1的第4点进行分析

为了解决从栈底进行计算的问题，可以创建一个numStack2和operStack2，从numStack和operStack中分别pop出一个，就分别向numStack2和operStack2中push一个，如下图

最后再从numStack2中pop中两个数，从operStack2中pop出一个符号，进行计算，注意是先pop出的数在前，后pop出的数在后，直到operStack2为空

代码改进分析：

由于从前向后遍历表达式，最后又将栈底和栈顶颠倒。因此，可以从表达式尾部开始向前遍历，这样可以省去颠倒栈底和栈顶的操作。但是要注意：在进行连除运算时，如果当前的运算符与pop出的运算符都为 /，则需要将pop出的运算符改为 *，如计算 6/3/2，需注意计算过程应为 6/(3*2)

3.3 改进的完整思路表述

1° 通过一个 index 值（索引），来遍历表达式；考虑使用String的toCharArray()方法，将String转为字符数组，并向前遍历；

2° 如果扫描到的是一个数字, 就直接入numStack；

3° 如果扫描到的是一个符号，以下三种情况，可以直接符号push入operStack

​ (1)如果当前的operStack为空，就直接入operStack；

​ (2)如果当前的操作符的优先级大于operStack栈中的操作符，直接入operStack；

​ (3)**如果当前的操作符的优先级等于operStack栈中的操作符，且当前的操作符为 + 或 - **，直接入operStack；

​ 其他情况均需要从numStack中pop出两个数，再从operStack中pop出一个符号，进行运算，将得到的结果放入numStack，然后将当前的操作符放入operStack；注意在进行连除运算时，如果当前的运算符与pop出的运算符都为 /，则需要将pop出的运算符改为 *；

4° 当表达式扫描完毕，就顺序的从numStack和operStack中pop出相应的数和符号，进行运算，注意先pop出的数在前；

5° 最后在numStack只有一个数字，就是表达式的结果。

4. 改进的完整代码

/* 与课堂讲解代码的几点不同： 1. 将三层if-else循环优化为两层 2. 将字符串表达式转换为字符数组进行向前遍历 3. 使用Stringbuffer进行字符拼接并反转 4. 将是否是运算符的判断从ArrayStack类中拿出，放入Calculator类 5. 未添加浮点运算与括号运算的功能 */ public class Calculator2 { public static void main(String[] args) { ArrayStack3 numberStack = new ArrayStack3(50);//数栈 ArrayStack3 operatorStack = new ArrayStack3(50);//符号栈 String expression = "700-2*5*4-4-12/6/2+4";//659 // String expression = "700-6*20*2*2+3";//223 // String expression = "7-6-5-4";//-8 // String expression = "70-60/2/3/5/2+98";//167 char[] arr = expression.toCharArray();//将表达式转换为字符数组 for (int i = arr.length - 1; i >= 0; i--) {//向前遍历 if (isOperator(arr[i])) {//如果是运算符 if (!operatorStack.isEmpty()//3.3分析的三条符号直接入栈条件的代码表示 && (operatorStack.priority(arr[i]) != operatorStack.priority(operatorStack.peek()) || (arr[i] != '+' && arr[i] != '-')) && operatorStack.priority(arr[i]) <= operatorStack.priority(operatorStack.peek())) { int num1 = numberStack.pop(); int num2 = numberStack.pop(); int operator = operatorStack.pop(); if(arr[i] == '/' && operator == '/'){//进行连除时，需要将后一个'/'变为'*' operator = '*'; } int result = numberStack.cal(num1, num2, operator); numberStack.push(result); } operatorStack.push(arr[i]); } else {//如果是数 StringBuffer buffer = new StringBuffer(); while (!isOperator(arr[i])) {//判断是否为符号 buffer.append(arr[i]); i--; if (i == -1) {//防止数组越界 break; } } i++;//保证索引指示正确 String s = buffer.reverse().toString();//反转buffer，并转换为字符串 int num = Integer.parseInt(s); numberStack.push(num); } } while (!operatorStack.isEmpty()) {//遍历完成后进行计算 int num1 = numberStack.pop(); int num2 = numberStack.pop(); int operator = operatorStack.pop(); int result = numberStack.cal(num1, num2, operator); numberStack.push(result); } System.out.println(expression + " = " + numberStack.pop()); } //判断是否是运算符 private static boolean isOperator(char value) { return value == '+' || value == '-' || value == '*' || value == '/'; } } class ArrayStack3 {//ArrayStack3类表示栈 private int maxSize;//栈的大小 private int[] stack;//数组，栈的数据存放在数组中 private int top = -1;//栈顶，初始化为-1 public ArrayStack3(int maxSize) { this.maxSize = maxSize; stack = new int[maxSize]; } //判断栈满 public boolean isFull() { return top == maxSize - 1; } //判断栈空 public boolean isEmpty() { return top == -1; } //入栈：push public void push(int num) { if (isFull()) { System.out.println("栈满"); return; } stack[++top] = num; } //出栈：pop public int pop() { if (isEmpty()) { throw new RuntimeException("栈空"); } int value = stack[top--]; return value; } //遍历栈 public void show() { //从栈顶开始遍历 if (isEmpty()) { System.out.println("栈空"); return; } int subTop = top; while (subTop != -1) { System.out.println(stack[subTop]); subTop--; } } //获取栈顶 public int peek() { return stack[top]; } //返回运算符的优先级，数字越大，优先级越高 public int priority(int operator) { if (operator == '*' || operator == '/') { return 1; } else if (operator == '*' || operator == '/') { return 0; } else { return -1; } } //计算方法，注意'-'和'/'是num1在前，与课堂上讲的有所不同 public int cal(int num1, int num2, int operator) { int result = 0;//存放计算结果 switch (operator) { case '+': result = num1 + num2; break; case '-': result = num1 - num2; break; case '*': result = num1 * num2; break; case '/': result = num1 / num2; break; } return result; } }