文章目录
数组模拟栈类
中缀表达式计算器类(测试类)
数组模拟栈类
主要实现栈的一些基本功能,以及在该场景下的功能。
//先创建一个栈 class AStack { private int maxSize; //栈的大小 private int[] stack; //数组模拟栈 private int top = -1; //栈顶,初始化-1 //构造器 public AStack(int maxSize) { this.maxSize = maxSize; stack = new int[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("栈空,出栈失败!"); } return stack[top--]; //先得到stack[top],然后top-- } //返回栈顶值 public int peek(){ return stack[top]; } //遍历(从栈顶向下) public void show(){ if (isEmpty()){ System.out.println("栈空!"); return; } for (int i = top; i >= 0; i--) { System.out.printf("stack[%d] = %d\n",i,stack[i]); } } //返回运算符优先级(约定数值越大,优先级越高) public int priority(char operator){ if (operator == '*' || operator == '/'){ return 1; }else if (operator == '+' || operator == '-'){ return 0; }else return -1; //假设只有加减乘除 } //判断是不是运算符 public boolean isOperator(char value){ return value == '+' || value == '-' || value == '*' || value == '/'; } //两数计算方法 public int cal(int num1,int num2,char operator){ int result = 0; //计算结果 switch (operator){ case '+': result = num2 + num1; break; case '-': result = num2 - num1; break; case '*': result = num2 * num1; break; case '/': result = num2 / num1; break; } return result; } }
中缀表达式计算器类(测试类)
主要实现计算的逻辑。
public class Calculate { public static void main(String[] args) { String expression = "5+40*4-3"; //162 AStack numStack = new AStack(10); //数栈 AStack opeStack = new AStack(5); //运算符栈 //定义需要的变量 int index = 0; //用于扫描表达式 int num1 = 0; int num2 = 0; int ope = 0; int res = 0; //用于临时保存两数运算结果 char ch = ' '; //每次扫描得到的字符 String keepNum = ""; //用于拼接多位数 //扫描表达式 while (true){ //扫描一个表达式字符 ch = expression.substring(index,index+1).charAt(0); //判断ch是数还是运算符,并处理 if (opeStack.isOperator(ch)) { //是运算符 if (opeStack.isEmpty()){ //运算符栈为空,直接入栈 opeStack.push(ch); }else { //不为空 if (opeStack.priority(ch) > opeStack.priority((char) opeStack.peek())){ //新的运算符优先级大于栈顶运算符的优先级,直接入栈 opeStack.push(ch); }else { //小于等于,则数栈pop两个,运算符栈pop一个进行运算,将结果入数栈、新运算符入运算符栈 num1 = numStack.pop(); num2 = numStack.pop(); ope = opeStack.pop(); res = numStack.cal(num1,num2, (char) ope); numStack.push(res); opeStack.push(ch); } } }else { //是数 keepNum += ch; if (index == expression.length() - 1){ numStack.push(Integer.parseInt(keepNum)); }else { if (numStack.isOperator(expression.substring(index+1,index+2).charAt(0))){ //后一位是运算符,则当前的可以直接入数栈 numStack.push(Integer.parseInt(keepNum)); keepNum = ""; //清空 } } } index++; if (index >= expression.length()){ //扫描到最后 break; } } //扫描结束,就顺序pop运算符栈和数栈进行运算,如何每次将结果入数栈 while (true){ if (opeStack.isEmpty()){ //运算符栈为空,则运算结束 break; } num1 = numStack.pop(); num2 = numStack.pop(); ope = opeStack.pop(); res = numStack.cal(num1,num2, (char) ope); numStack.push(res); } //数栈最后一个数即为表达式结果 System.out.printf("表达式 %s = %d",expression,numStack.pop()); } }