中缀表达式转换为后缀表达式
思路分析
代码实现
package com.atguigu.stack;import javax.swing.plaf.nimbus.State;import java.security.AlgorithmConstraints;import java.util.ArrayList;import java.util.List;import java.util.Stack;/*** @创建人 wdl* @创建时间 /3/20* @描述*/public class PolandNotation {public static void main(String[] args) {//完成一个中缀表达式转换成后缀表达式的功能//说明//1."1+((2+3)×4)-5"=>"1 2 3 + 4 × + 5 –"//2.因为直接对一个str进行操作，不方便，因此先将"1+((2+3)×4)-5"=>中缀的表达式对应的List//即"1+((2+3)×4)-5"=>ArrayList[....//3.将得到的中缀表到时对应的List转换成后缀表达式ListString expression="1+((2+3)*4)-5";List<String> infixExpressionList = toInfixExpressionList(expression);System.out.println("中缀表达式对应的List"+infixExpressionList);List<String> parseSuffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);System.out.println("后缀表达式对应的List"+parseSuffixExpreesionList);System.out.println("expression="+calculate(parseSuffixExpreesionList));// //先定义一个逆波兰表达式// // (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 -// //说明为了方便，逆波兰表达式的数字和符号使用空格隔开// String suffixExpression="3 4 + 5 * 6 -";// //思路// //1.先将"3 4 + 5 × 6 -"放到ArrayList中// //2.将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算// List<String> rpnList=getListString (suffixExpression);// System.out.println(rpnList);//// int res=calculate(rpnList);// System.out.println("计算的结果是="+res);}public static List<String> parseSuffixExpreesionList(List<String> ls){//定义两个栈Stack<String> s1=new Stack<String>();//符号栈//说明：因为s2这个栈，在整个转换过程中，没有pop操作，而且我们后面还需要逆序输出//因此比较麻烦，这里我们就不用Stack<String>直接使用List<String> s2//Stack<String> s2=new Stack<String>();存储中间结果的栈s2List<String> s2 = new ArrayList<>();//存储中间结果的List2//遍历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栈顶的运算符弹出并加入到s2中，// 再次转到(4.1)与s1中新的栈顶运算符相比较；//问题：我们缺少一个比较优先级高低的方法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;//注意因为是存放到List，因此按顺序输出就是对应的后缀表达式对应的List}//方法：将中缀表达式转换成对应的Listpublic static List<String> toInfixExpressionList(String s){//定义一个List，存放中缀表达式对应的内容List<String> ls = new ArrayList<>();int i=0;//这时是一个指针，用于遍历中缀表达式字符串String str;//对多位数的拼接工作char c;//每遍历一个字符，就放入到cdo{//如果c是一个非数字，我们就需要加入到lsif((c=s.charAt(i))<48||(c=s.charAt(i))>57){ls.add(c+"");i++;//i需要后移}else {//如果是一个数，需要考虑多位数str="";//先将str置成""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;//返回}//将一个逆波兰表达式，依次将数据和运算符放到ArrayList中public static List<String> getListString(String suffixExpression){//将suffixExpression分割String[] split = suffixExpression.split(" ");List<String> list = new ArrayList<>();for(String ele:split){list.add(ele);}return list;}//完成对逆波兰表达式的运算// 从左至右扫描，将3和4压入堆栈；// 遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；// 将5入栈；// 接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；// 将6入栈；// 最后是-运算符，计算出35-6的值，即29，由此得出最终结果public static int calculate(List<String> ls){//创建一个栈，只需要一个栈即可Stack<String> stack = new Stack<>();//遍历 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("-")){res=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;switch (operation){case "+":result=ADD;break;case "-":result=SUB;break;case "*":result=MUL;break;case "/":result=DIV;break;default:System.out.println("不存在该运算符");break;}return result;}}
