中缀表达式转后缀表达式（代码实现）及前缀表达式思路补充 后缀表达式适合计算机式的计算，因此在开发中，我们需要将中缀表达式转为后缀表达式。
三种表达式 这⾥再次区分⼀下前缀表达式、中缀表达式、后缀表达式（以（3+4）*5-6为例） 中缀表达式就是我们正常遇见的（3+4）*5-6这样的式⼦ 前缀表达式⼜称为波兰式，其运算符是在数之前 中缀表达式转前缀表达式思路：从右⾄左扫描表达式，遇到数字时，将数字压⼊堆栈，遇到运算符时，弹出栈顶的两个数，⽤运算符对它们做相应的计算（栈顶元素 top 次顶元素），并将结果⼊栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果 例如：- * + 3 4 5 61. 从右⾄左扫描，将6、5、4、3压⼊堆栈2. 遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素，注意与后缀表达式做⽐较），计算出3+4的值，得7，再将7⼊栈3. 接下来是×运算符，因此弹出7和5，计算出7×5=35，将35⼊栈4. 最后是-运算符，计算出35-6的值，即29，由此得出最终结果中缀表达式转后缀表达式具体步骤 1).初始化两个栈：运算符栈s1和存储中间结果的栈s2； 2).从左到右扫描中缀表达式； 3).遇到操作数时，将其压⼊s2; 4).遇到运算符时，⽐较其与s1栈顶运算符的优先级； 1.如果s1为空，或栈顶运算符为左括号"("，则直接将此运算符⼊栈 2.否则，若优先级⽐栈顶运算符的⾼，也将运算符压⼊s1 3.否则，将s1栈顶的运算符弹出并压⼊s2中，再次转到(4-1)与s1中新的栈顶运算符相⽐较； 5)遇到括号时： (1)如果时左括号"("，则直接压⼊s1 (2)如果是右括号")"，则依次弹出s1栈顶的运算符，并压⼊s2,直到遇到左括号为⽌，此时将这⼀对括号丢弃 6)重复2⾄5,直到表达式的最右边 7)将s1中剩余的运算符依次弹出并压⼊s2 8）依次弹出s2中的元素并输出，结果的逆序为中缀表达式对应的后缀表达式举例说明 将中缀表达式"1+((2+3)*4)-5"转换为后缀表达式为："1 2 3 + 4 * + 5 -"过程如下：举例代码package com.atxihua;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class PolandNotation1 {public static void main(String[] args) {//完成将⼀个中缀表达式转成后缀表达式的功能//1+((2+3)*4)-5转成1 2 3 + 4 * + 5 -//因为直接对str进⾏操作，不⽅便，因此，先将1+((2+3)*4)-5存⼊对应的list//即1+((2+3)*4)-5=》ArrayList[1,+,(,(,2,+,3,),*,4),-,5]//将得到的中缀表达式对应的List=》后缀表达式对应的List//即ArrayList[1,+,(,(,2,+,3,),*,4),-,5]=>ArrayList[1,2,3,+,4,*,+,5,-]String expression="1+((2+3)*4)-5";List<String> infixExpreesionList=toInfixExpreesionList(expression);System.out.println("中缀表达式="+infixExpreesionList);//ArrayList[1,+,(,(,2,+,3,),*,4),-,5] List<String> suffixExpreesionList=parseSuffixExpreesionList(infixExpreesionList);System.out.println("后缀表达式="+suffixExpreesionList);//ArrayList[1,2,3,+,4,*,+,5,-]System.out.println("结果为："+calculate(suffixExpreesionList));}//将中缀表达式转成对应的listprivate static List<String> toInfixExpreesionList(String s) {//定义⼀个List,存放中缀表达式对应的内容List<String> ls=new ArrayList<String>();int i=0;//⽤于遍历中缀表达式字符串String str;//⽤于拼接多位数char c;//每遍历到⼀个字符，就放到cdo{//如果c是⼀个⾮数字，我们需要加⼊到lsif((c=s.charAt(i))<48||(c=s.charAt(i))>57){ls.add(""+c);i++;}else {//如果是⼀个数，需要考虑多位数str="";//先将str设置为0[48]-9[57]while (i<s.length()&&(c=s.charAt(i))>=48&&(c=s.charAt(i))<=57){str+=c;//拼接i++;}ls.add(str);}}while (i<s.length());return ls;}//将得到的中缀表达式对应的List=>后缀表达式private static List<String> parseSuffixExpreesionList(List<String> ls) {//定义两个栈Stack<String> s1=new Stack<String>();//符号栈//说明：s2这个栈，在整个转换过程中，没有pop操作，⽽且后⾯需要逆序输出，就不使⽤栈，直接使⽤list存储//Stack<String> s2=new Stack<String>();//数栈List<String> s2=new ArrayList<String>();//存储中间结果的list//遍历lsfor(String item:ls){//如果是⼀个数，加⼊s2if(item.matches("\\d+")){s2.add(item);}else if(item.equals("(")){s1.push(item);}else if(item.equals(")")){//如果是右括号")"，则依次弹出s1栈顶的运算符，并压⼊s2，直到遇到左括号为⽌，此时，将这⼀对括号丢弃while (!s1.peek().equals("(")){s2.add(s1.pop());}s1.pop();//将 ( 弹出s1栈，消除⼩括号}else {//当item的优先级⼩于等于s1栈顶运算符，将s1栈顶运算符弹出并加⼊到s2,直到遇到左括号为⽌，此时将这⼀对括号丢弃 //我们缺少⼀个⽐较优先级⾼低的⽅法while (s1.size()!=0&& Operation.getValue(s1.peek())>=Operation.getValue(item)){s2.add(s1.pop());}//还需要将item压⼊栈s1.push(item);}}//将s1中剩余的运算符依次弹出并加⼊s2while (s1.size()!=0){s2.add(s1.pop());}return s2;//}private static int calculate(List<String> ls) {//创建⼀个栈Stack<String> stack = new Stack<String>();//遍历lsfor(String item:ls){//使⽤正则表达式来取数if(item.matches("\\d+")){//匹配多为数//⼊栈stack.push(item);}else {//pop出两个数并运算，再⼊栈int num2=Integer.parseInt(stack.pop());int num1=Integer.parseInt(stack.pop());int res=0;if(item.equals("+")){res=num1+num2;}else if(item.equals("-")){//注意num2⽐num1先出栈，所以是num1-num2res=num1-num2;}else if(item.equals("/")){res=num1/num2;}else if(item.equals("*")){res= num1*num2;}else {throw new RuntimeException("运算符有误");}//把res⼊栈stack.push(""+res);}}//最后留在stack中的数据即运算结果return Integer.parseInt(stack.pop());}}//编写⼀个类Operation可以返回⼀个运算符，对应的优先级class Operation{private static int Add=1;private static int SUB=1;private static int MUL=2;private static int DIV=2;//写⼀个⽅法，返回对应的优先级数字public static int getValue(String operation){int result=0;if(operation.equals("+")){result=Add;}else if(operation.equals("-")){result=SUB;}else if(operation.equals("*")){result=MUL;}else if(operation.equals("/")){result=DIV;}else {System.out.println("不存在该运算符");}return result;}}运⾏结果因为我们在写代码时，遇到左括号时，压⼊栈中，在遇到右括号时在处理，因此，计算机将左括号当作运算符处理，在处理逻辑中只对加减乘除进⾏了处理，相信这点很容易理解，就不再处理了。
