用栈实现中缀表达式

中缀表达式"/>

用栈实现中缀表达式

一、定义栈

class ArrayStack { // 定义栈private int maxSize; // 栈的大小private int[] stack; // 数组,存放栈的数据private int top = -1;//指向栈顶public ArrayStack(int maxSize) {this.maxSize = maxSize;this.stack = new int[maxSize];}public ArrayStack(){}/*** 返回栈顶元素,但是并不出栈* @return*/public int peek(){if (isEmpty()){System.out.println("栈为空,无法 peek");}return stack[top];}/*** 从表达式中得到完整的数字* @param expression* @param index1* @param index2* @return*/public static String getAllNum(String expression,int index1,int index2){ArrayStack operStack = new ArrayStack();String keepNum = "";if (!operStack.isOper(expression.substring(index1 + 1,index2 + 1).charAt(0))){keepNum += getAllNum(expression,index1 +1,index2 + 1);}else {keepNum += expression.substring(index1,index2).charAt(0);}return keepNum;}/*** 判断栈是否已满** @return true已满, false未满*/public boolean isFull() {return top + 1 == maxSize;}/*** 判断栈是否为空** @return true为空, false不为空*/public boolean isEmpty() {return top == -1;}/*** 入栈** @param value*/public void push(int value) {// 1.判断栈是否已满if (isFull()) {System.out.println("栈已满,不能继续添加！！！");}top++;stack[top] = value;}/*** 出栈** @return 栈顶元素*/public int pop() {// 1.判断是否为空if (isEmpty()) {throw new RuntimeException("栈为空,不能进行出栈操作！！！");}int value = stack[top];top--;return value;}/*** 遍历栈*/public void list() {// 1.判断栈是否为空if (isEmpty()) {throw new RuntimeException("栈为空,遍历操作失败！！！");}for (int i = top; i >= 0; i--) {System.out.printf("第%d个的栈顶元素为%d", i, stack[i]);System.out.println();}}/*** 判断运算符优先级** @param oper 传入运算符* @return*/public int priority(int oper) {if (oper == '*' || oper == '/') {return 1;} else if (oper == '+' || oper == '-') {return 0;} else {return -1;}}/*** 判断传入的运算符是否合法** @param oper* @return*/public boolean isOper(int oper) {if (oper == '*' || oper == '/' || oper == '+' || oper == '-') {return true;} else {return false;}}/*** 计算** @param num1* @param num2* @param oper* @return*/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;}
}

二、核心代码

    public static void main(String[] args) {//根据思路，完成表达式的计算String expression = "3*9+10/2+1";//创建两个栈，一个是数栈，一个是符号栈ArrayStack numStack = new ArrayStack(10);ArrayStack operStack = new ArrayStack(10);//定义需要的相关变量int index = 0;  //用于扫描int num1 = 0;int num2 = 0;int oper = 0;int res = 0;char ch = ' ';  //将每次扫描得到的char保存到ch中String keepNum = "";  //用于拼接多位数//开始用while循环的扫描expressionwhile (true) {//依 次得到expression的每一个字符//字符串中有一个函数是substring方法，两个参数分别是开始位置和结束位置，这里就是获取了一个字符的字符串//substring获取到的是字符串，但是ch是char类型，只能接收一个字符，所以用charAt来获得substring字符串中的其中一个字符ch = expression.substring(index, index + 1).charAt(0);//判断ch是什么，然后做相应的处理if (operStack.isOper(ch)) {  //如果是运算符//判断当前的符号栈是否为空if (!operStack.isEmpty()) {//如果符号栈中有操作符，就进行比较，如果当前的操作符的优先级小于或者等于栈中的操作符，就需要从数栈中取出两个数//并在符号栈中取出一个符号，进行运算，将得到的结果，入数栈，然后将当前的操作符入符号栈if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1, num2, oper);//把运算的结果加入到数栈中numStack.push(res);operStack.push(ch);}else {  //如果当前的操作符的优先级大于栈中的操作符，就直接入栈operStack.push(ch);}}else {   //如果符号栈为空，直接入栈operStack.push(ch);}}else {  //如果是数字，直接入数栈//分析思路：//1.当处理多位数时，不能发现是一个数的时候就直接入栈，因为它可能是多位数，//2.在处理数时，需要向expression的表达式的index后再看一位，如果是数就进行扫描，如果是符号才入栈//3.因此需要定义一个字符串变量，用于拼接keepNum += ch;//如果ch已经是expression的最后一位，就直接入数栈if (index == expression.length() - 1) {numStack.push(Integer.parseInt(keepNum));}else {//判断下一个字符是不是数字，如果是数字，就继续扫描，如果是运算符，就入数栈//注意是往后看一位，不是index++if (operStack.isOper(expression.substring(index+1,index+2).charAt(0))) {//如果后一位是运算符，则入栈，但是keepNum是一个字符串，需要把它转换成整型才可以，所以可以调用Integer.parseInt方法，把keepNum转换成整型numStack.push(Integer.parseInt(keepNum));//重要！！！，keepNum需要清空keepNum = "";}}}//让index + 1，并判断是否扫描到了expression的最后index++;if (index >= expression.length()) {break;}}//当表达式扫描完毕，就顺序的从数栈和符号栈中pop出相应的数字和符号，并运行while (true) {//如果符号栈为空，则计算已经结束，数栈中只有一个数字【结果】if (operStack.isEmpty()) {break;}num1 = numStack.pop();num2 = numStack.pop();oper = operStack.pop();res = numStack.cal(num1, num2, oper);numStack.push(res);  //入栈}//将数栈中最后的数字pop出，就是表达式的计算结果int res2 = numStack.pop();System.out.printf("表达式 %s = %d\n", expression, res2);}

三、测试结果

表达式 3*9+10/2+1 = 33