一.中缀变后缀过程分析
给定一个中缀,最后变为后缀的过程其实并不算复杂,下面分析一下过程:
1. 首先面对一个中缀表达式,我们需要两个栈,一个用来存放运算符,即符号栈 operatorstack,一个用来存放数字,运算符,即数字栈 numStack
2. 开始扫描中缀表达式
3.遇到操作数时,我们直接压入数字栈,即numStack;
4.遇到运算符时,需要我们比较一下当前符号与栈顶符号的优先级,这里分以下三种情况
4.1 operatorStack为空,好的,我们直接压入
4.2 operatorStack不为空,且当前符号的优先级大于栈顶符号的优先级,我们也直接压入符号栈
4.3 operatorStack不为空,且当前符号的优先级小于或者等于栈顶符号的优先级,这是我们需要先将operatorStack的栈顶pop出并push到numStack,此处是一个while循环,直到找出当前符号的优先级大于符号栈栈顶符 号的优先级为止,再将当前符号压入operatorStack.
5.遇到括号时,有如下操作
5.1 如果是 "(" ,直接压入符号栈.operatorStack;
5.2 如果是 ")" ,则将符号栈栈内符号依次弹出,push进numStack,直到遇见 "(" 为止,注意的是,这一对括号进入丢弃状态,即 "(" 弹出,不会入任何栈,")" 也不会入任何栈
6.重复2-5,扫描中缀表达式,直到最后结束
7.最后将符号栈中符号顺序弹出并加入数字栈
8.数字栈numStack输出,结果的逆序就是我们要的后缀表达式
二. 代码实现
通过一中的过程分析我们可以看到,数字栈从头到输出之前并没有进行任何弹栈操作,所以为了便于书写,下面将数字栈采用arrayList来代替,且易于输出
并且,如果采用索引去对中队表达式进行扫描的话,会十分麻烦,所以我们采用以下思路,进行转换并计算结果
中缀表达式 -->顺序存放中缀表达式中数字,操作符以及括号的list集合 --> 根据上面一的思路转成存放后缀表达式的元素的集合 rearList-->遍历rearList进行计算
代码如下:
package com.ebiz.stack; import java.util.ArrayList; import java.util.List; import java.util.Stack; /** * @author YHj * @create 2019-07-24 15:51 * * 中缀表达式转后缀表达式 */ public class MiddleToRear { public static void main(String[] args) { //不用索引扫描表达式,将表达式加入到list中 String expression="1+((2+3)*4)-5"; //得到中缀表达式转为list的集合 List<String> list=getList(expression); //将中缀表达式的集合转到后缀表达式的集合 List<String> rearList=getRearList(list); System.out.println("rearList = " + rearList); //输出计算结果 System.out.println(getResult(rearList)); } //中缀表达式的集合转为后缀表达式的集合 private static List<String> getRearList(List<String> list) { ArrayList<String> rearList = new ArrayList<>(); //定义符号栈 Stack<String> operatorStack = new Stack<>(); //定义集合代替数字栈,数字栈本身并没有pop操作,并且最后要倒叙输出,随意用list代替 ArrayList<String> numList = new ArrayList<>(); for (String s : list) { //如果是个数字 if (s.matches("\d+")){ numList.add(s); }else if (s.equals("(")){ operatorStack.push(s); }else if (s.equals(")")){ //符号栈栈顶直到左括号之前的符号放入数字栈 while (!"(".equals(operatorStack.peek())){ numList.add(operatorStack.pop()); } //把左括号弹出来 operatorStack.pop(); //判断优先级,当前符号优先级小于等于符号栈栈顶优先级,将符号栈栈顶弹出加入数字栈, //直到找到当前符号优先级大于符号栈栈顶优先级为止,再将当前符号加入符号栈 }else{ while (operatorStack.size()!=0 && (OperPriority.getPriority(s) <= OperPriority.getPriority(operatorStack.peek()))){ numList.add(operatorStack.pop()); } //将当前符号加入符号栈 operatorStack.push(s); } } //将符号栈中剩余符号加入数字栈 while (operatorStack.size()!=0){ numList.add(operatorStack.pop()); } return numList; } //将中缀表达式的各个字符存到list集合,方面遍历 private static List<String> getList(String expression) { ArrayList<String> list = new ArrayList<>(); int index=0; String str=""; //多位数的拼接 char c; //用于存放每次扫描到的结果 do { //判断是否为数字,非数字直接加入list c=expression.charAt(index); if (c < 48 || c >57){ list.add(""+c); }else {//数字.考虑可能不是一位数,字符串拼接 str+=c; if (index == expression.length()-1){ list.add(str); }else { if (expression.charAt(index+1) < 48 || expression.charAt(index+1) > 57){ list.add(str); str=""; } } } index++; }while (index < expression.length()); return list; } //输出计算结果 private static int getResult(List<String> list) { Stack<String> stack = new Stack<>(); for (String s : list) { //匹配数字 if (s.matches("\d+")){ stack.push(s); }else { int num01=Integer.parseInt(stack.pop()); int num02=Integer.parseInt(stack.pop()); int result=0; if (s.equals("+")){ result=num01+num02; }else if (s.equals("-")){ result=num02-num01; }else if (s.equals("*")){ result=num02*num01; }else if (s.equals("/")){ result=num02/num01; }else { throw new RuntimeException("无法解析的字符串"); } stack.push(""+result); } } return Integer.parseInt(stack.pop()); } }
上面涉及到的判断符号优先级的类
package com.ebiz.stack; /** * @author YHj * @create 2019-07-24 18:14 */ public class OperPriority { private static int AAD =1; //加; private static int SUB =1; //减 private static int MUL =2; //乘 private static int DIV =2; //除 public static int getPriority(String operator){ int result=0; switch (operator){ case "+": result=AAD; break; case "-": result=SUB; break; case "*": result=MUL; break; case "/": result=DIV; break; default: break; } return result; } }
有待完善...