原文地址：https://blog.csdn.net/guorui_java/article/details/106215643

一、中缀表达式

中缀表达式是一个通用的算术或逻辑公式表示方法。我们小学学的加减乘除就是所谓的中缀表达式，便于人类计算的表达式。
例如：（3+4）* 5 - 6

二、前缀表达式和后缀表达式

（3+4） 5 - 6的前缀表达式是- + 3 4 5 6
（3+4） 5 - 6的后缀表达式是 3 4 + 5 6 -
后缀表达式较为常用，计算机熟悉的表达式，真狗。
后缀表达式（逆波兰表达式）是一种十分有用的表达式，它将复杂表达式转换为可以依靠简单的操作得到计算结果的表达式。

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

1、初始化两个栈：运算符栈s1和储存中间结果栈s2；
2、从右至左扫描中缀表达式；
3、遇到操作数时，将其压入s2；
4、遇到运算符时，比较其与s1栈顶运算符的优先级：
（1）如果s1为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈；
（2）否则，若优先级比栈顶运算符的高，也将运算符压入s1；
（3）否则，将s1栈顶的运算符弹出并压入s2中，再次转到（1），与s1中新的栈顶运算符相比较；
5、遇到括号时：
（1）如果是左括号“（”，则直接压入s1；
（2）如果是右括号“）”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃；
6、重复步骤2至5，直到表达式的最右边
7、将s1中剩余的运算符依次弹出并压入s2；
8、依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式。

四、逆波兰计算器

大体思路：
1、中缀表达式转为后缀表达式，然后通过逆波兰计算器计算后缀表达式；
2、先将中缀表达式转为对应的List，方便运算 ；（3+4） 5 - 6 转成 [(, 3, +, 4, ), , 5, -, 6]
3、将list转为后缀表达式对应的list； [(, 3, +, 4, ), , 5, -, 6] 转为 [3, 4, +, 5, , 6, -]
4、完成逆波兰计算器

五、代码实现

  1. package dataStructure.stack;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Stack;
  7. public class PolandNotation {
  8.     public static void main(String[] args) {
  9.         String expression = "(3+4)*5-6";//注意表达式
  10.         List<String> infixExpressionList = toInfixExpressionList(expression);
  11.         System.out.println("中缀表达式对应的List=" + infixExpressionList); // ArrayList [(, 3, +, 4, ), *, 5, -, 6]
  12.         List<String> suffixExpreesionList = parseSuffixExpreesionList(infixExpressionList);
  13.         System.out.println("后缀表达式对应的List" + suffixExpreesionList); //ArrayList [3, 4, +, 5, *, 6, -]
  14.         System.out.printf("expression=%d", calculate(suffixExpreesionList));
  15.     }
  17.     //方法：将 中缀表达式转成对应的List
  18.     //  s="(3+4)*5-6";
  19.     public static List<String> toInfixExpressionList(String s) {
  20.         //定义一个List,存放中缀表达式 对应的内容
  21.         List<String> ls = new ArrayList<String>();
  22.         int i = 0; //这时是一个指针，用于遍历 中缀表达式字符串
  23.         String str; // 对多位数的拼接
  24.         char c; // 每遍历到一个字符，就放入到c
  25.         do {
  26.             //如果c是一个非数字，我需要加入到ls
  27.             if((c=s.charAt(i)) < 48 ||  (c=s.charAt(i)) > 57) {
  28.                 ls.add("" + c);
  29.                 i++; //i需要后移
  30.             } else { //如果是一个数，需要考虑多位数
  31.                 str = ""; //先将str 置成"" '0'[48]->'9'[57]
  32.                 while(i < s.length() && (c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57) {
  33.                     str += c;//拼接
  34.                     i++;
  35.                 }
  36.                 ls.add(str);
  37.             }
  38.         }while(i < s.length());
  39.         return ls;//返回
  40.     }
  43.     //方法：将得到的中缀表达式对应的List => 后缀表达式对应的List
  44.     //即 ArrayList [(, 3, +, 4, ), *, 5, -, 6]  =》 ArrayList [3, 4, +, 5, *, 6, -]
  45.     public static List<String> parseSuffixExpreesionList(List<String> ls) {
  46.         //定义两个栈
  47.         Stack<String> s1 = new Stack<String>(); // 符号栈
  48.         //说明：因为s2 这个栈，在整个转换过程中，没有pop操作，而且后面我们还需要逆序输出
  49.         //因此比较麻烦，这里我们就不用 Stack<String> 直接使用 List<String> s2
  50.         //Stack<String> s2 = new Stack<String>(); // 储存中间结果的栈s2
  51.         List<String> s2 = new ArrayList<String>(); // 储存中间结果的Lists2
  52.         //遍历ls
  53.         for(String item: ls) {
  54.             //如果是一个数，加入s2
  55.             if(item.matches("\\d+")) {
  56.                 s2.add(item);
  57.             } else if (item.equals("(")) {
  58.                 s1.push(item);
  59.             } else if (item.equals(")")) {
  60.                 //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
  61.                 while(!s1.peek().equals("(")) {
  62.                     s2.add(s1.pop());
  63.                 }
  64.                 s1.pop();//!!! 将 ( 弹出 s1栈， 消除小括号
  65.             } else {
  66.                 //当item的优先级小于等于s1栈顶运算符, 将s1栈顶的运算符弹出并加入到s2中，再次转到(4.1)与s1中新的栈顶运算符相比较
  67.                 //问题：我们缺少一个比较优先级高低的方法
  68.                 while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item) ) {
  69.                     s2.add(s1.pop());
  70.                 }
  71.                 //还需要将item压入栈
  72.                 s1.push(item);
  73.             }
  74.         }
  75.         //将s1中剩余的运算符依次弹出并加入s2
  76.         while(s1.size() != 0) {
  77.             s2.add(s1.pop());
  78.         }
  79.         return s2; //注意因为是存放到List, 因此按顺序输出就是对应的后缀表达式对应的List
  80.     }
  82.     //完成对逆波兰表达式的运算
  83.     /*
  84.      * 1)从左至右扫描，将3和4压入堆栈；
  85.        2)遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
  86.        3)将5入栈；
  87.        4)接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
  88.        5)将6入栈；
  89.        6)最后是-运算符，计算出35-6的值，即29，由此得出最终结果
  90.      */
  91.     public static int calculate(List<String> ls) {
  92.         // 创建给栈, 只需要一个栈即可
  93.         Stack<String> stack = new Stack<String>();
  94.         // 遍历 ls
  95.         for (String item : ls) {
  96.             // 这里使用正则表达式来取出数
  97.             if (item.matches("\\d+")) { // 匹配的是多位数
  98.                 // 入栈
  99.                 stack.push(item);
  100.             } else {
  101.                 // pop出两个数，并运算， 再入栈
  102.                 int num2 = Integer.parseInt(stack.pop());
  103.                 int num1 = Integer.parseInt(stack.pop());
  104.                 int res = 0;
  105.                 if (item.equals("+")) {
  106.                     res = num1 + num2;
  107.                 } else if (item.equals("-")) {
  108.                     res = num1 - num2;
  109.                 } else if (item.equals("*")) {
  110.                     res = num1 * num2;
  111.                 } else if (item.equals("/")) {
  112.                     res = num1 / num2;
  113.                 } else {
  114.                     throw new RuntimeException("运算符有误");
  115.                 }
  116.                 //把res 入栈
  117.                 stack.push("" + res);
  118.             }
  120.         }
  121.         //最后留在stack中的数据是运算结果
  122.         return Integer.parseInt(stack.pop());
  123.     }
  124. }
  126. //编写一个类 Operation 可以返回一个运算符 对应的优先级
  127. class Operation {
  128.     private static int ADD = 1;
  129.     private static int SUB = 1;
  130.     private static int MUL = 2;
  131.     private static int DIV = 2;
  133.     //写一个方法，返回对应的优先级数字
  134.     public static int getValue(String operation) {
  135.         int result = 0;
  136.         switch (operation) {
  137.             case "+":
  138.                 result = ADD;
  139.                 break;
  140.             case "-":
  141.                 result = SUB;
  142.                 break;
  143.             case "*":
  144.                 result = MUL;
  145.                 break;
  146.             case "/":
  147.                 result = DIV;
  148.                 break;
  149.             default:
  150.                 System.out.println("不存在该运算符" + operation);
  151.                 break;
  152.         }
  153.         return result;
  154.     }
  156. }

六、控制台输出

6.中缀表达式转为后缀表达式，实现逆波兰计算器 - 图1