March.11.2022——中缀表达式转化为后缀表达式统一思路

本文主要是介绍March.11.2022——中缀表达式转化为后缀表达式统一思路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

March.11.2022

中缀表达式转化为后缀表达式统一思路（8步）

初始化两个栈：运算符栈s1和储存中间结果的栈s2；
从左至右扫描中缀表达式；
遇到操作数时，将其压s2；
遇到运算符时，比较其与s1栈顶运算符的优先级：

1). 如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；

2). 否则，若优先级比栈顶运算符的高，也将运算符压入s1；

3). 否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
遇到括号时：
1. . 如果是左括号“(”，则直接压入s1
2. . 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
重复步骤2至5，直到表达式的最右边
将s1中剩余的运算符依次弹出并压入s2
依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式

package Zhan;import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;import java.util.ArrayList;
import java.util.List;
import java.util.Stack;//如果要使用List 包 那必须要导包！！ dlt + enterpublic class ZhongZhuiTOHouZhui {public static void main(String[] args) {//完成将中缀表达式 转化为后缀表达式//说明//1.   1+（（2+3）*4）-5  转换成   1 2 3 + 4 * + 5 -//2. 因为直接对字符串 进行操作 不方便，所以需要将 “1+（（2+3）*4）-5 ”，中缀表达式存到对应的list中// 即“1+（（2+3）*4）-5 ” => Arraylist[1,+,(,(,2,+3,),),*,4,-,5]//3.将得到的中缀表达式对应的list 转化为后缀表达式//即 得到了[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5] 需要转换为  1 2 3 + 4 * + 5 -//没有小括号//具体的步骤 有8步String Expression = "1+((2+3)*4)-5";List<String> infixExpressionlist = toInfixExpressionlist(Expression);System.out.println(infixExpressionlist);//逆波兰表达式 (3+4)*5-6; 其中该式子的逆波兰表达式可以写为 3 4 + 5 * 6 -；String sufficExpression = "3 4 + 5 * 6 -";//思路//1.先将 该计算表达式的逆波兰表达式字符串 放到 Arratlist中//2.将 Arraylist 传给一个方法，遍历 Arraylist 配合栈完成计算List<String> list = getlistString(sufficExpression);System.out.println("list" + list);int res = calculate(list);System.out.println("计算的结果是" + res);}//将中缀表达式转化成对应的Listpublic static List<String> toInfixExpressionlist(String s) {//定义一个List 存放中缀表达式  对应的内容List<String> ls = new ArrayList<String>();int i = 0; //作为扫描的指针String str = "";// 对多位数的拼接char c;//每遍历到一个字符 ，就直接放到cdo {//如果 c 是一个非数字的字符 就直接将遍历得到的c加到字符串中if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {ls.add("" + c);i++;} else {//如果 c 是一个数  不为个位数的话就将字符串拼接起来//这里非常容易出问题！！必须将字符串清空！！！！！！！！！str = "";//数字在ASC码表中的值 即为48-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());//扫描完毕 返回lsreturn ls;}//将中缀表达式转换为后缀表达式public static List<String> parseSufExpresionList(List<String> ls) {//创建一个栈 用于存放运算符Stack<String> stack1 = new Stack<String>();//创建一个栈 用于存放数字//但是考虑到 在中转后缀表达式的时候，数字的栈从来没有使用过出栈操作，并且最后还需要逆序输出//这里直接使用List<String> s2;//Stack<String> stack2 = new Stack<>();List<String> s2 = new ArrayList<String>();//遍历lsfor (String item : ls)//如果遍历得到的是一个数 则入栈到s2if (item.matches("\\d+")) {s2.add(item);//请注意 这里是 .equals 不是 .matchs!!!!!} else if (item.equals("(")) {stack1.push(item);} else if (item.equals(")")) {while (!stack1.peek().equals("(")) {s2.add(stack1.pop());}stack1.pop();///将stack1 弹出栈 消除小括号} else {//当item的运算符的优先级小于等于s1栈顶的运算符，将s1栈顶的运算符弹出并加入s2中，再次转到4.1步骤，与i新的运算符的栈顶比较//问题:缺少一个比较运算符优先级的方法while (stack1.size() != 0 && Operation.getValue(stack1.peek()) >= Operation.getValue(item)) {s2.add(stack1.pop());}//还需要将item入栈stack1.push(item);}//将s1剩余的运算符依次弹出并加入s2while(stack1.size()!=0){s2.add(stack1.pop());}return s2;}private static List<String> getlistString(String sufficExpression) {//将后缀表达式按照空格来拆分，拆分成字符串数组String[] split = sufficExpression.split(" ");//创建一个字符串形式的数组列表 用于接收 被拆分的字符串数组ArrayList<String> list = new ArrayList<>();for(String ele:split){list.add(ele);}return list;}//完成对逆波兰表达式的计算// 1.从左往右扫描， 将 3 和 4 压入栈中；//2.遇到 + 号运算符 弹出 4 和 3 （其中 4为栈顶元素，3为次栈顶元素），计算出 3+4 的值，得到7 将结果7入栈//3.将5 入栈//4.遇到 * 运算符 ，弹出5 和 7  计算出 5*7=35 将35入栈//5.遇到6 将6入栈//6.遇到 - 运算符，计算出来 35-6的值 得到最终结果//扫描的过程其实就是对list 的遍历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出两个数字 第一个出栈的是num2 第二个出栈的数命名为num1int num2 = Integer.parseInt(stack.pop());int num1 = Integer.parseInt(stack.pop());//由于出栈的元素的类型为 string  需要转化为int  类型所以调用Integer.parseInt方法 将字符串类型转化为 int 类型方便计算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("你输入的格式有误，请重新输入");}//请注意 这里使用了一个小技巧：即通过在前后加空格的方法，将整数类型转化为字符串类型stack.push(""+res);}}return Integer.parseInt(stack.pop());}}//编写一个运算符优先级的类 对应不同运算符的优先级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;}}