栈的三种表达式：前缀、中缀和后缀表达式，后缀也叫逆波兰表达式

前缀（波兰表达式）

中缀（对人来讲很好理解，对于计算机来讲就方便了，一般会把中缀表达式转换成后缀表达式）

后缀（逆波兰表达式）

计算过程

例字

这里就用java自带的栈了Stack（多位数也可以）（自己写个栈也可以，这里为了方便）

（这里输入的是后缀表达式，中缀转后缀往下看）

package stack;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class PolandNotation {public static void main(String []args){//先定义一个逆波兰表达式//（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> list = getListString(suffixExpression);int res = calculate(list);System.out.println(res);}//将表达式，依次将输入和运算符 方法欧ArrayList中public static List<String> getListString(String suffixExperssion){//分割String[] split = suffixExperssion.split(" ");ArrayList<String> list = new ArrayList<>();for (String ele : split){list.add(ele);}return list;}public static int calculate(List<String> ls){//创建栈，只需要一个栈Stack<String> stack = new Stack<>();//遍历for (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());}}

中缀表达式 转 后缀表达式

1）操作步骤：

2）例

代码几乎每行都有注释，根据思路一步一步分析来自己实现一下。

1）中缀转后缀代码

public static List<String> parseSuffixExpressionList(List<String> ls){//定义两个栈Stack<String> s1 = new Stack<>(); //符号栈//说明：因为S2栈，并没有用到pop，而且后面还需要逆序说出，比较麻烦//Stack<String> stack2 = new Stack<>(); //中间结果的栈//这里就用List来代替ArrayList<String> s2 = new ArrayList<String>();//遍历lsfor (String item : ls){//如果是数就入栈if (item.matches("\\d+")){s2.add(item);} else if (item.equals("(")){s1.push(item);} else if (item.equals(")")){while (!s1.peek().equals("(")){//s1内容加入s2s2.add(s1.pop());}s1.pop(); // 将（弹出s1栈} else {//当s1栈顶的运算符的优先级 大于等于 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中剩下的运算符依次弹出加入s2中while (s1.size() != 0){s2.add(s1.pop());}//因为存放了List里，直接顺序输入就是对应的逆波兰表达式return s2;}

2）判断符号优先级

//编写一个类，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:result = 0;//这里是栈中是(,那么结果设成0，不管什么运算符都存进来break;}return result;}}

完整代码（以及上面的运算）

package stack;import java.util.ArrayList;import java.util.List;import java.util.Stack;public class PolandNotation {public static void main(String []args){//完成中缀表达式转成后缀表达式//说明// 1.因为直接对str 进行操作，不方便， 因此先将"1+((2+3)*4)-5" =》中缀表达式转成对应的List// 2.即"1+((2+3)*4)-5" =》 ArrayList[1,+,(,(,2,+,3,*,4,),-,5]String expression = "1+((2+3)*4)-5";//中缀表达式转成ListList<String> list = toInfixExpressionList(expression);System.out.println("中缀表达式：" + list);//中缀表达式：[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]//把ArrayList[1,+,(,(,2,+,3,*,4,),-,5] =》"1 2 3 + 4 × + 5 –"List<String> parseSuffixExpressionList = parseSuffixExpressionList(list);System.out.println("后缀表达式：" + parseSuffixExpressionList);//后缀表达式：[1, 2, 3, +, 4, *, +, 5, -]//计算转换后的后缀表达式int calculate = calculate(parseSuffixExpressionList);System.out.println("后缀表达式计算结果：" + calculate);/*//先定义一个逆波兰表达式//（3+4）*5-6 => 3 4 + 5 * 6 -//测试(30+4)*5-6//为了方便数字和符号使用空格隔开String suffixExpression = "30 4 + 5 * 6 -";//思路// 1.先将3 4 + 5 * 6 -放入ArrayList中// 2.将ArrayList 传递给一个方法，遍历ArrayList 配合栈完成计算List<String> list = getListString(suffixExpression);int res = calculate(list);System.out.println(res);*/}//方法：将得到的中缀表达式转换成后缀表达式具体步骤如下:// //初始化两个栈：运算符栈s1和储存中间结果的栈s2；// //从左至右扫描中缀表达式；// //遇到操作数时，将其压s2；// //遇到运算符时，比较其与s1栈顶运算符的优先级：// //如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈；// //否则，若优先级比栈顶运算符的高，也将运算符压入s1；// //否则，将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；// //遇到括号时：(1) 如果是左括号“(”，则直接压入s1(2) 如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃// //重复步骤2至5，直到表达式的最右边// //将s1中剩余的运算符依次弹出并压入s2// //依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式public static List<String> parseSuffixExpressionList(List<String> ls){//定义两个栈Stack<String> s1 = new Stack<>(); //符号栈//说明：因为S2栈，并没有用到pop，而且后面还需要逆序说出，比较麻烦//Stack<String> stack2 = new Stack<>(); //中间结果的栈//这里就用List来代替ArrayList<String> s2 = new ArrayList<String>();//遍历lsfor (String item : ls){//如果是数就入栈if (item.matches("\\d+")){s2.add(item);} else if (item.equals("(")){s1.push(item);} else if (item.equals(")")){while (!s1.peek().equals("(")){//s1内容加入s2s2.add(s1.pop());}s1.pop(); // 将（弹出s1栈} else {//当s1栈顶的运算符的优先级 大于等于 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中剩下的运算符依次弹出加入s2中while (s1.size() != 0){s2.add(s1.pop());}//因为存放了List里，直接顺序输入就是对应的逆波兰表达式return s2;}//方法：将字符串中缀表达式转为Listpublic static List<String> toInfixExpressionList(String s){//电影以一个List，存放中缀表达式ArrayList<String> list = new ArrayList<>();int i = 0;//相当于一个指针，用于遍历字符串String str;//对多位数进行拼接char c; //每遍历到一个字符就放到c中do {//如果c是一个非数字，我们就需要加入到list里if ((c = s.charAt(i)) < 48 || (c= s.charAt(i)) >57){list.add("" + c);i++; //i后移} else {// 如果是一个数，需要考虑多位数str = ""; //str清空while (i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57){str += c; //拼接i++;}list.add(str);}}while(i < s.length());return list;}//将表达式，依次将输入和运算符 方法欧ArrayList中public static List<String> getListString(String suffixExperssion){//分割String[] split = suffixExperssion.split(" ");ArrayList<String> list = new ArrayList<>();for (String ele : split){list.add(ele);}return list;}public static int calculate(List<String> ls){//创建栈，只需要一个栈Stack<String> stack = new Stack<>();//遍历for (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:result = 0;break;}return result;}}

结果：中缀表达式：[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]后缀表达式：[1, 2, 3, +, 4, *, +, 5, -]后缀表达式计算结果：16

数据结构 - 栈 （逆波兰计算器）（栈的三种表达式）（前缀 中缀和后缀表达式 后缀也叫逆波兰表达式）（中缀表达式转后缀表达式实现步骤及完整代码）