- 使用栈完成表达式的计算思路
1、通过一个index值(索引),来遍历我们的表达式
2、如果我们发现是数字,则直接入数栈;如果发现扫描到的是符号,就分一下集中情况:
3.1 :如果符号栈有操作符,就需要进行比较 -->
3.1.1 如果当前操作符的优先级小于或者等于栈中的操作符,就需要从数栈中pop出2个数,在从符号栈中pop出1个符号进行运算,将得到的结果,入数栈,然后将当前的操作符入符号栈
3.1.2 如果当前操作符的优先级大于栈中的操作符,就直接入符号栈
4、当表达式扫描完毕,就顺序地从数栈和符号栈中pop除相应的数和符号,并运行
5、最后在数栈中只有一个数字,就是表达式的结果
验证:3+2*6-2 ==> 13
1 class ArrayStack{ 2 private int maxSize; //栈中最多的数据个数 3 private int[] stack; //数组模拟 4 private int top = -1; //栈顶 5 public ArrayStack(int maxSize){ 6 this.maxSize = maxSize; 7 stack = new int[this.maxSize]; 8 } 9 10 //入栈【先检查栈是否满了】 11 public void push(int n) { 12 if (top == maxSize - 1) { 13 System.out.println("栈满,无法加入数据"); 14 return; 15 }else { 16 top++; 17 stack[top] = n; 18 } 19 } 20 21 //栈是否为空 22 public boolean isEmpty() { 23 return top == -1; 24 } 25 26 //出栈【先检查栈是否空了】 27 public int pop() { 28 if (isEmpty()) { 29 throw new RuntimeException("栈空,无数据"); 30 }else { 31 return stack[top--]; 32 } 33 } 34 35 //展示栈中的数据【先检查栈是否空了】 36 public void show() { 37 if (isEmpty()) { 38 System.out.println("栈空,无数据可以展示"); 39 return; 40 }else { 41 for(int i = top;i >= 0; i--) { 42 System.out.printf("stack[%d] = %d\n",i,stack[i]); 43 } 44 } 45 } 46 47 //返回运算符的优先级【*、/ 比 + 、- 高】<返回的数字越大,优先级越高> 48 public int priority(int operator) { 49 switch(operator) { 50 case '*': 51 case '/': 52 return 1; 53 case '+': 54 case '-': 55 return 0; 56 default: 57 return -1; 58 } 59 } 60 61 //判断是否是运算符【假设只有加减乘除】 62 public boolean isOperator(int operator){ 63 return operator == '+' || operator == '-' || operator == '*' || operator == '/'; 64 } 65 66 //根据数栈中弹出来的两个数和符号栈中弹出来的一个符号进行运算 67 public int cal(int num1, int num2, int operator) { 68 int ret = 0; 69 //此处不能在switch内部直接进行return 70 switch(operator) { 71 case '+': 72 ret = num1 + num2; 73 break; 74 case '-': 75 //注意顺序:后弹出来的减去前弹出来的 76 ret = num2 - num1; 77 break; 78 case '*': 79 ret = num1 * num2; 80 break; 81 case '/': 82 ret = num2 / num1; //此处不考虑除数为0的情况 83 break; 84 default: 85 break; 86 } 87 return ret; 88 } 89 90 //偷看一下位于符号栈栈顶的符号,并不取出 91 public int peek() { 92 return stack[top]; 93 } 94 95 }
1 public class Calculator { 2 3 public static void main(String[] args) { 4 //定义表达式 5 String expression = "80+12*600-21"; // 7280 - 21 = 7259 6 //创建数栈、符号栈 7 ArrayStack numberStack = new ArrayStack(10); 8 ArrayStack operatorStack = new ArrayStack(10); 9 //定义相关变量 10 int index = 0; //索引依次取出表达式中的数和符号 11 int num1 = 0; 12 int num2 = 0; //num1 和 num2用于接收连续从数栈出栈的两个值 13 int operator = 0; //接收从符号栈中参与运算的符号 14 int ret = 0; //运算结果 15 char ch = ' '; //接收每次扫描到的数据 16 String str = ""; 17 while(index < expression.length()) { 18 ch = expression.substring(index, index+1).charAt(0); 19 //ch = expression.charAt(index++); //取一个字符等价于本行 20 //如果是符号【分两种情况】 21 if (operatorStack.isOperator(ch)) { 22 //情况1:符号栈为空则直接入符号栈 23 if (operatorStack.isEmpty()) { 24 operatorStack.push(ch); 25 }else { 26 //情况2:符号栈不为空【在分两种情况】 27 //情况2.1:当前运算符的优先级小于或者等于栈顶运算符的优先级,则从数栈中pop出两个数 28 //从符号栈中pop出一个符号进行运算 29 if (operatorStack.priority(ch) <= operatorStack.priority(operatorStack.peek())) { 30 num1 = numberStack.pop(); 31 num2 = numberStack.pop(); 32 operator = operatorStack.pop(); 33 ret = operatorStack.cal(num1, num2, operator); 34 //将运算的结果入数栈 35 numberStack.push(ret); 36 //把当前运算符入符号栈 37 operatorStack.push(ch); 38 }else{ //情况2.2:当前运算符的优先级大于栈底运算符的优先级,直接入符号栈 39 operatorStack.push(ch); 40 } 41 } 42 }else { 43 //如果是数,则直接入数栈 44 //numberStack.push(ch - 48); //注意: 字符'0' --> 48 【只能处理个位数】 45 str += ch; 46 //此时:如果index是表达始终的最后一位数,将其直接压入到数栈中 47 if (index == expression.length() - 1) { 48 numberStack.push(Integer.parseInt(str)); 49 } 50 else { 51 //往后多看一位 52 if (numberStack.isOperator(expression.substring(index+1,index+2).charAt(0))) { 53 //是操作符【入栈】,如果不是操作符则继续拼接 str += ch; 54 numberStack.push(Integer.parseInt(str)); 55 str = ""; 56 } 57 58 } 59 } 60 index++; //继续遍历 61 } 62 //表达式扫描完毕,顺序地从数栈和符号栈中弹出数据和符号进行运算,直到符号栈为空,则最后留在数栈中的数即为最终结果 63 while(!operatorStack.isEmpty()) { 64 num1 = numberStack.pop(); 65 num2 = numberStack.pop(); 66 operator = operatorStack.pop(); 67 ret = operatorStack.cal(num1, num2, operator); 68 //将运算的结果入数栈 69 numberStack.push(ret); 70 } 71 System.out.println("表达式" + expression + "的最终结果是:" + numberStack.pop()); 72 } 73 }