我们在计算机器中输入“7*2*2-5+1-5+3-4”，就能很快得到结果18，那么如何利用栈结构模拟实现计算机呢？下面就来聊聊在编写代码时的思路，注意点以及代码（我只考虑了简单的加减乘除运算，其中包含多位数的计算）。
思路：
- 先创建两个栈，一个数据栈和一个操作符栈；
- 通过index值，初始值为0，遍历表达式；
- 若是数，直接入数字栈；
- 若是操作符，判断操作符栈是否为空，空则直接入操作符栈，否则，判断当前操作符与操作符栈的栈顶元素的优先级，若当前操作符优先级<=操作符栈的栈顶元素的优先级，则从数栈中pop出两个元素，从操作符栈中pop出一个元素，进行运算，将计算结果入数栈，当前操作符入符号栈；若当前操作符优先级>操作符栈的栈顶元素的优先级,则将当前操作符入符号栈。
- 循环2-4步，直至index = 表达式长度-1；
- 此时表达式遍历完成，顺序从数栈和操作符栈中pop出相应的数和符合运行，直到操作符栈为空，此时数栈中剩余的数就是表达式的结果。
注意点：
- 由于栈的先进后出特点，在做减法和除法时，需要是第二次pop出的数减去或者除以第一次pop出的数！
- 若表达式中的数是多位数，在将数入栈后，需要将keepNum清空（keepNum是拼接多位数的一个变量）！
实现代码如下：
ArrayCaculator.java
public class ArrayCaculator {private int maxSize;private int[] stack;private int top = -1;//指向栈顶元素public ArrayCaculator(int maxSize){this.maxSize = maxSize;stack = new int[this.maxSize];}public boolean isFull(){return top == maxSize-1;}public boolean isEmpty(){return top == -1;}public void push(int value){if (isFull()){System.out.println("栈已满，不能再添加元素！");return;}top++;stack[top] = value;}public int pop(){if (isEmpty()){throw new RuntimeException("栈是空栈，没有元素可出！");}int res = stack[top];top--;return res;}public void show(){if (isEmpty()){System.out.println("栈是空栈，无法遍历");return;}for (int i = top; i >= 0 ; i--) {System.out.printf("当前元素为%d！",stack[i]);}}//显示栈顶元素，不出栈public int peek(){return stack[top];}//判断操作符优先级，优先级越高，越先执行public int priority(int ch){if (ch == '*' || ch == '/'){return 1;}if (ch == '+' || ch == '-'){return 0;}return -1;}//判断是不是操作符public boolean isOper(int ch){return ch == '-' || ch == '+' || ch == '*' || ch == '/';}//计算public int cal(int num1,int num2,int oper){int res =0;switch (oper){case '+':res = num1 + num2;break;case '-':res = num2 - num1;break;case '*':res = num1 * num2;break;case '/':res = num2 / num1;break;default:break;}return res;}
}
Test.java
public class Test {public static void main(String[] args) {
// String expre = "3+2*6-2";String expre = "7*2*2-5+1-5+3-4";ArrayCaculator numStack = new ArrayCaculator(10);ArrayCaculator operStack = new ArrayCaculator(10);int num1 =0;int num2 = 0;int index = 0;int oper = 0;int res = 0;char ch = ' ';String keepNum = "";while (true){//通过index遍历expressch = expre.substring(index,index+1).charAt(0);//ch是不是操作符if (operStack.isOper(ch)){//ch是操作符if (!operStack.isEmpty()){//操作符栈不为空if (operStack.priority(ch) <= operStack.priority(operStack.peek())){//ch操作符优先级小于或等于栈顶元素，数栈出两个数，操作符栈顶元素出栈//计算结果，将结果放入数栈，ch入操作符栈num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1,num2,oper);numStack.push(res);operStack.push(ch);}else {//ch优先级大于栈顶操作符优先级，ch入操作符栈operStack.push(ch);}}else {//操作符栈为空，ch入操作符栈operStack.push(ch);}}else {keepNum += ch;if (index == expre.length()-1){//最后一个数，直接入数栈numStack.push(Integer.parseInt(keepNum));}else {//ch是数字,先看看下一位是不是也是数字if (operStack.isOper(expre.substring(index+1,index+2).charAt(0))){//下一位不是数，将当前数入栈，keepNum清空numStack.push(Integer.parseInt(keepNum));keepNum = "";}}}//多位数或者向下一位遍历，index都要++index++;if (index >= expre.length()){break;}}while (true){//遍历完表达式，将两个栈中的元素都出栈，并运算if (operStack.isEmpty()){break;}num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1,num2,oper);numStack.push(res);}//此时全部计算完，数栈中剩余的这个元素就是最终结果int res2 = numStack.pop();System.out.printf("表达式%s的计算结果是%d",expre,res2);}}
有不足之处欢迎批评指正！