09--栈实现综合计算器

• 使用栈完成表达式的计算思路

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 }