一行文章让你搞懂什么是前缀、中缀、后缀表达式以及它们之间的相互转换

一、什么前缀、中缀、后缀表达式（使用 8*(5+6)-1的例子）

1.中缀表达式：8*（5+6）-1；（也就是我们平常所见的运算式）
2.后缀表达式：8 5 6 + * 1 - ；计算机是怎么运算的呢？
从左向右进行遍历，数字放到数据栈中，也就是8 5 6；当遍历到+号时，从数据栈中弹出两个距离+号最近的数据进行相加，也就是5 和 6，得到结果13入栈中；接着遍历，当遇到 *号时，从栈中弹出距离 *最近的两个数据进行相乘，也就是13和8，将结果104入栈中；遍历到1入数据栈，接着遍历到-号，同样从数据栈中取出距离-号最近的两个数据进行相减，也就是104和1，最后的结果103入栈中，遍历结束
3.前缀表达式：- 1 *+ 6 5 8（类似与后缀表达式，只不过是从右向左进行遍历）

这三个表达式的结果都是相同的，只不过计算机更倾向于后缀表达式（波兰表达式）

二、中缀表达式转前缀表达式

1.思路：

*1.如果使用两个栈进行操作，发现数据栈没有出栈的操作，所以可以使用List代替数据栈
* 2.遍历表达式
* 3.如果是数字，则入加入集合
* 4.如果是运算符，需要考虑以下这几种情况
* 情况一：运算符栈如果为空，则将运算符直接入栈；
* 情况二：如果栈顶为"(",则直接将运算符入栈
* 情况三：如果该运算符大于栈顶的运算符，则直接将该运算符入栈
* 否则，将栈顶运算符添加到集合中，继续重复这几种情况，直到该运算符入栈
* 5.如果遇到“）”，判断栈顶的符号是否是“（”，如果不是，则将栈顶运算符加入到集合中；如果是，则将这两个括号丢弃
* 6.遍历表达式结束，就将剩余栈中的数据加入到集合中
* 7.将list反转，形成前缀表达式

2.代码

package com.company;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;/*** @author:抱着鱼睡觉的喵喵* @date:2021/2/20* @description:*/
public class InfixToPrefix {public static void main(String[] args) {String str = "8*((6-4)+1)";List<String> strList = toInfixStrList(str);for (String temp : strList) {System.out.printf(temp);}System.out.println();List<String> list = toInfixTransformPrefix(strList);for (String temp : list) {System.out.printf(temp);}int result = cal(list);System.out.printf("结果为：%d",result);}/*** 将表达式存入list集合中* @param str* @return*/public static List<String> toInfixStrList(String str) {char ch;int i = 0;String cs = "";List<String> list = new ArrayList<>();do {if ((ch = str.charAt(i)) < 48 || (ch = str.charAt(i)) > 57) {   //数字的区间[48,56]list.add("" + ch);i++;} else {        //这里是为了考虑多位数的情况while (i < str.length() && (ch = str.charAt(i)) >= 48 && (ch = str.charAt(i)) <= 57) {cs += ch;   //字符的拼接  "5" + "6" = "56";i++;}list.add(cs);cs = "";}} while (i < str.length());return list;}/*** 中缀转前缀思路：* 1.如果使用两个栈进行操作，发现数据栈没有出栈的操作，所以可以使用List代替数据栈* 2.遍历表达式* 3.如果是数字，则入加入集合* 4.如果是运算符，需要考虑以下这几种情况*  情况一：运算符栈如果为空，则将运算符直接入栈；*  情况二：如果栈顶为"(",则直接将运算符入栈*  情况三：如果该运算符大于栈顶的运算符，则直接将该运算符入栈*  否则，将栈顶运算符添加到集合中，继续重复这几种情况，直到该运算符入栈* 5.如果遇到“）”，判断栈顶的符号是否是“（”，如果不是，则将栈顶运算符加入到集合中；如果是，则将这两个括号丢弃* 6.遍历表达式结束，就将剩余栈中的数据加入到集合中* 7.将list反转，形成前缀表达式* @param list* @return*/public static List<String> toInfixTransformPrefix(List<String> list) {Stack<String> opStack = new Stack<>();List<String> numList = new ArrayList<>();String temp = "";for (int i = 0; i < list.size(); i++) {     //遍历temp = list.get(i);                     //使用临时遍历temp记录每一次遍历的数据if (temp.matches("\\d+")) {         //使用正则表达式(/d+)，是否是数字numList.add(temp);                      //如果是则加入集合中} else if (temp.equals(")")) {              //判断是否是“）”，如果是要循环将栈顶的运算符加入到集合中，直到遇到“（”,并将两个括号丢弃while (!opStack.peek().equals("(")) {numList.add(opStack.pop());}opStack.pop();  //丢弃括号continue;} else if (Operation.isOperation(temp)) {   //如果是运算符,考虑三种情况while (!opStack.isEmpty() && !opStack.peek().equals("(") && (Operation.priority(temp) <= Operation.priority(opStack.peek()))) {numList.add(opStack.pop());}opStack.push(temp);         //将运算符入栈}else if (temp.equals("(")) {       //如果是左括号直接入栈opStack.push(temp);} else {throw new RuntimeException("你输入的表达式有误!");}}while (!opStack.isEmpty()) {        //遍历结束，将栈中剩余数据加入到集合中numList.add(opStack.pop());}Collections.reverse(numList);       //list反转return numList;}public static int cal(List<String> list) {Stack<String> stack = new Stack<>();int num1 = 0;int num2 = 0;int result;String ele="";for (int i = list.size() - 1;i >= 0; i--) {ele = list.get(i);if (ele.matches("\\d+")) {      //匹配的是一位数或者多位数(\d+)stack.push(ele);} else {result = 0;num1 = Integer.parseInt(stack.pop());num2 = Integer.parseInt(stack.pop());if (ele.equals("+")) {result = num2 + num1;} else if (ele.equals("-")) {result = num2 - num1;} else if (ele.equals("*")) {result = num2 * num1;} else if (ele.equals("/")) {result = num2 / num1;} else {throw new RuntimeException("运算符有误!");}stack.push(""+result);}}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 DEL = 2;public static boolean isOperation(String s) {return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");}/*** 使用1 2 表示运算符的优先级* @param s* @return*/public static int priority(String s) {switch (s) {case "+":return ADD;case "-":return SUB;case "*":return MUL;case "/":return DEL;default:throw new RuntimeException("符号有误!");}}
}

三、中缀表达式转前缀表达式

1.思路：

* 1.定义两个栈，数据栈numStack和运算符栈opStack* 2.从左到右遍历中缀表达式* 3.如果是数字则压入numStack数据栈中* 4.如果是运算符，则需要考虑三种情况：* 第一种：如果opStack栈为空,或者opStack栈顶运算符为（，则将该运算符压入该栈中* 第二种：让该运算符与opStack栈顶运算符进行比较优先级，如果该运算符的优先级大于等于opStack栈顶运算符，则将该运算符压入该栈中* 第二种：不满足以上两种情况，则将opStack栈顶的运算符弹出并压入numStack栈中，再次考虑这三种情况，直到满足前两种情况中的某一个情况为止* 5.如果遇到括号：如果是"(",则直接压入opStack中；如果是“）”，则依此弹出opStack栈中的运算符，并压入numStack中，直到遇到左括号为止，并将这两个括号舍弃* 6.当表达式遍历完毕，结束* 7，将opStack栈中的运算符依次弹出，并压入numStack栈中* 8.将数据反转即可

2.代码

package com.company;import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;/*** @author:抱着鱼睡觉的喵喵* @date:2021/2/19* @description:*/
public class InfixToSuffix {public static void main(String[] args) {String str = "4 * ( ( 3 + 8 ) - 6 )";List<String> list = transform(str);System.out.println("中缀表达式转后缀表达式如下:");for (String temp : list) {System.out.printf("%s ", temp);}System.out.println();int result = cal(list);System.out.printf("结果为:%d",result);}/*** 中缀表达式转后缀表达式步骤* 1.定义两个栈，数据栈numStack和运算符栈opStack* 2.从左到右遍历中缀表达式* 3.如果是数字则压入numStack数据栈中* 4.如果是运算符，则需要考虑三种情况：* 第一种：如果opStack栈为空,或者opStack栈顶运算符为（，则将该运算符压入该栈中* 第二种：让该运算符与opStack栈顶运算符进行比较优先级，如果该运算符的优先级大于等于opStack栈顶运算符，则将该运算符压入该栈中* 第二种：不满足以上两种情况，则将opStack栈顶的运算符弹出并压入numStack栈中，再次考虑这三种情况，直到满足前两种情况中的某一个情况为止* 5.如果遇到括号：如果是"(",则直接压入opStack中；如果是“）”，则依此弹出opStack栈中的运算符，并压入numStack中，直到遇到左括号为止，并将这两个括号舍弃* 6.当表达式遍历完毕，结束* 7，将opStack栈中的运算符依次弹出，并压入numStack栈中* 8.将数据反转即可** @param s* @return  转为后缀表达式之后的list集合*/public static List<String> transform(String s) {Stack<String> numStack = new Stack<>();     //数据栈Stack<String> opStack = new Stack<>();      //运算符栈String str = "";String[] split = s.split(" ");          //以空格将数据分割for (int i = 0; i < split.length; i++) {       //遍历分割后的数据str = split[i];if (isOperator(str)) {      //如果是操作符if (str.equals(")")) {      //如果是右括号的情况while (!opStack.peek().equals("(")) {numStack.push(opStack.pop());}opStack.pop();          //丢弃右括号continue;}while (true) {if (opStack.isEmpty() || opStack.peek().equals("(")) {opStack.push(str);break;} else if (priority(str) >= priority(opStack.peek())) {opStack.push(str);break;} else {numStack.push(opStack.pop());}}} else if (str.matches("\\d+")) {       //如果是数字numStack.push(str);} else {throw new RuntimeException("你定义的表达式有误!~");}}while (!opStack.isEmpty()) {    //遍历结束，将运算符栈中的运算符加入到数据栈中numStack.push(opStack.pop());}List<String> list = new ArrayList<>(); //   存入list集合中while (!numStack.isEmpty()) {list.add(numStack.pop());}Collections.reverse(list);      //反转listreturn list;}/*** 判断是否是运算符** @param s* @return*/public static boolean isOperator(String s) {return s.equals("*") || s.equals("/") || s.equals("+") || s.equals("-") || s.equals("(") || s.equals(")");}/*** 使用0 1 2定义优先级** @param s* @return*/public static int priority(String s) {if (s.equals("*") || s.equals("/")) {return 1;} else if (s.equals("+") || s.equals("-")) {return 0;} else if (s.equals("(")) {return 2;} else {throw new RuntimeException("表达式有误!");}}/*** 计算表达式的结果* @param list* @return result*/public static int cal(List<String> list) {Stack<String> stack = new Stack<>();int num1 = 0;int num2 = 0;int result;for (String ele : list) {if (ele.matches("\\d+")) {      //匹配的是一位数或者多位数(\d+)stack.push(ele);} else {result = 0;num1 = Integer.parseInt(stack.pop());num2 = Integer.parseInt(stack.pop());if (ele.equals("+")) {result = num2 + num1;} else if (ele.equals("-")) {result = num2 - num1;} else if (ele.equals("*")) {result = num2 * num1;} else if (ele.equals("/")) {result = num2 / num1;} else {throw new RuntimeException("运算符有误!");}stack.push(""+result);}}return Integer.parseInt(stack.pop());}
}

愿你孤独的努力都有回报，愿你前行的路上有人陪伴~
加油~

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！