一 前缀表达式(波兰表达式)

前缀表达式又称波兰表达式，在前缀表达式中，运算符位于操作数之前
举例说明： (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6

1. 前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素 和 次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果
例如: (3+4)×5-6 对应的前缀表达式就是 - × + 3 4 5 6 , 针对前缀表达式求值步骤如下:
（1）从右至左扫描，依次将6、5、4、3压入堆栈
（2）遇到+运算符，因此弹出3和4（3为栈顶元素，4为次顶元素），计算出3+4的值，得7，再将7入栈
（3）接下来是×运算符，因此弹出7和5，计算出7×5=35，将35入栈
（4）最后是-运算符，计算出35-6的值，即29，由此得出最终结果

二 中缀表达式

中缀表达式就是常见的运算表达式，如(3+4)×5-6。中缀表达式的求值是我们人最熟悉的，但是对计算机来说却不好操作，因为不知道前后计算符号的优先级，因此，在计算结果时，往往会将中缀表达式转成其它表达式来操作(一般转成后缀表达式)。

三 后缀表达式

  1. 后缀表达式又叫 逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后。<br />举例说明： (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 –<br />又比如：
正常的表达式 逆波兰表达式
a+b a b +
a+(b-c) a b c - +
a+(b-c)*d a b c – d * +
a+d*(b-c) a d b c - * +
a=1+3 a 1 3 + =

1. 后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入堆栈，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（次顶元素 和 栈顶元素），并将结果入栈；重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
例如: (3+4)×5-6 对应的后缀表达式就是 3 4 + 5 × 6 - , 针对后缀表达式求值步骤如下:
（1）从左至右扫描，将3和4压入堆栈；
（2）遇到+运算符，因此弹出4和3（4为栈顶元素，3为次顶元素），计算出3+4的值，得7，再将7入栈；
（3）将5入栈；
（4）接下来是×运算符，因此弹出5和7，计算出7×5=35，将35入栈；
（5）将6入栈；
（6）最后是-运算符，计算出35-6的值，即29，由此得出最终结果

四 中缀表达式转换为后缀表达式

后缀表达式适合计算式进行运算，但是人却不太容易写出来，尤其是表达式很长的情况下，因此在开发中，我们需要将 中缀表达式转成后缀表达式。
具体步骤如下:

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

    1.举例说明

    将中缀表达式“1+((2+3)×4)-5”转换为后缀表达式的过程如下：
扫描到的元素 s2(栈底->栈顶) s1 (栈底->栈顶) 说明
1 1 空 数字，直接入栈
+ 1 + s1为空，运算符直接入栈
( 1 + ( 左括号，直接入栈
( 1 + ( ( 同上
2 1 2 + ( ( 数字
+ 1 2 + ( ( + s1栈顶为左括号，运算符直接入栈
3 1 2 3 + ( ( + 数字
) 1 2 3 + + ( 右括号，弹出运算符直至遇到左括号
× 1 2 3 + + ( × s1栈顶为左括号，运算符直接入栈
4 1 2 3 + 4 + ( × 数字
) 1 2 3 + 4 × + 右括号，弹出运算符直至遇到左括号
- 1 2 3 + 4 × + - -与+优先级相同，因此弹出+，再压入-
5 1 2 3 + 4 × + 5 - 数字
到达最右端 1 2 3 + 4 × + 5 - 空 s1中剩余的运算符

因此结果为 “1 2 3 + 4 × + 5 –”

2. 代码说明

  1. package com.atguigu.reversepolishcal;
  3. import java.util.ArrayList;
  4. import java.util.List;
  5. import java.util.Stack;
  9. public class ReversePolishCalCase {
  11. public static void main(String[] args) {
  12. //举例1: 2 + (3-4) => 2 3 4 - +
  13.  //举例2: 4 * 5 - 8 + 60 + 8 / 2 = 4 5 * 8 - 60 + 8 2 / + 
  14.  //举例3: (3+4)×5-6 => 3 4 + 5 * 6 -
  15. //String suffixExperss = "4 5 * 8 - 60 + 8 2 / +";
  16. //String suffixExperss = "2 3 4 - +";
  17. //String suffixExperss = "3 4 + 5 * 6 -";
  18. //
  19. ReversePolishCal reversePolishCal = new ReversePolishCal();
  20. //
  21. //List <String> suffixExpressionList = reversePolishCal.getListBySuffixExpression(suffixExperss);
  22. //
  23. //        System.out.println("计算结果:"+ reversePolishCal.calculate(suffixExpressionList));
  25.         //测试输入中缀表达式是否能计算成功
  26.         String infixExpression = "4*5-8+60+8/2";
  29.         List<String> infixExpressionList = reversePolishCal.toInfixExpression(infixExpression);
  30.         List<String> suffixExpressionList2 = reversePolishCal.parseSuffixExpression(infixExpressionList);
  31.         //输出后缀表达式
  32.         for(String ele : suffixExpressionList2) {
  33.         System.out.print(ele + " ");
  34.         }
  35.         System.out.println();
  36.         //输出结果
  37.         System.out.println("计算结果:"+ reversePolishCal.calculate(suffixExpressionList2));
  40. }
  42. }
  44. class ReversePolishCal {
  46. /**
  47.      * 把字符串转换成中序表达式 : 比如 2+(3-4), 并放入到List中
  48.      * @param s
  49.      * @return
  50.      */
  51.     public List<String> toInfixExpression(String infixExpression) {
  52.         List<String> ls = new ArrayList<String>();//存储中序表达式
  53.         int i = 0;
  54.         String str;
  55.         char c;
  56.         do {
  57.         //如果c 在 < 48 或者 > 57 说明是符号, 这里没有判断是 + , - , * , / 等等
  58.             if ((c = infixExpression.charAt(i)) < 48 || (c = infixExpression.charAt(i)) > 57) {
  59.                 ls.add("" + c);
  60.                 i++;
  61.             } else { // 说明是数字，要进行拼接处理
  62.                 str = "";
  63.                 while (i < infixExpression.length() && (c = infixExpression.charAt(i)) >= 48
  64.                         && (c = infixExpression.charAt(i)) <= 57) {
  65.                     str += c;
  66.                     i++;
  67.                 }
  68.                 ls.add(str);
  69.             }
  71.         } while (i < infixExpression.length());
  72.         return ls;
  73.     }
  75.     /**
  76.      * 将一个中缀表达式对应的List 转成 转换成逆波兰表达式, 放入到List中
  77.      * @param ls
  78.      * @return
  79.      */
  80.     public  List<String> parseSuffixExpression(List<String> ls) {
  81.         Stack<String> s1=new Stack<String>();
  82.         Stack<String> s2=new Stack<String>();
  83.         List<String> lss = new ArrayList<String>();
  84.         for (String ss : ls) {
  85.             if (ss.matches("\\d+")) {
  86.                 lss.add(ss);
  87.             } else if (ss.equals("(")) {
  88.                 s1.push(ss);
  89.             } else if (ss.equals(")")) {
  91.                 while (!s1.peek().equals("(")) {
  92.                     lss.add(s1.pop());
  93.                 }
  94.                 s1.pop();
  95.             } else {
  96.                 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(ss)) {
  97.                     lss.add(s1.pop());
  98.                 }
  99.                 s1.push(ss);
  100.             }
  101.         }
  102.         while (s1.size() != 0) {
  103.             lss.add(s1.pop());
  104.         }
  105.         return lss;
  106.     }
  110. //将一个后缀表达式，依次放入到List<String>中
  111. public List<String> getListBySuffixExpression(String suffixExpression) {
  112. String[] split = suffixExpression.split(" ");
  113. List<String> list = new ArrayList<String>();
  114. for (String element : split) {
  115. list.add(element);
  116. }
  117. return list;
  118. }
  120. /**
  121.  * 
  122.  * @param ls 是一个按照逆波兰表达式得到衣蛾List 
  123.  * @return
  124.  */
  125.     public int calculate(List<String> ls) {
  126.     Stack<String> s=new Stack<String>();
  127.         for (String str : ls) {
  128.             if (str.matches("\\d+")) {
  129.                 s.push(str);
  130.             } else {
  131.                 int b = Integer.parseInt(s.pop());
  132.                 int a = Integer.parseInt(s.pop());
  133.                 int result=0;
  134.                 if (str.equals("+")) {
  135.                     result = a + b;
  136.                 } else if (str.equals("-")) {
  137.                     result = a - b;
  138.                 } else if (str.equals("*")) {
  139.                     result = a * b;
  140.                 } else if (str.equals("/")) {
  141.                     result = a / b;
  142.                 } else {
  143.                 throw new RuntimeException("符号错误");
  144.                 }
  145.                 s.push("" + result);
  146.             }
  147.         }
  148.         //System.out.println(s.peek()); 
  149.         return Integer.parseInt(s.pop());
  150.     }
  152. }
  155. class Operation {
  156.     private static int ADDITION=1;
  157.     private static int SUBTRACTION=1;
  158.     private static int MULTIPLICATION=2;
  159.     private static int DIVISION=2;
  161.     public static int getValue(String operation){
  162.         int result;
  163.         switch (operation){
  164.             case "+":
  165.                 result=ADDITION;
  166.                 break;
  167.             case "-":
  168.                 result=SUBTRACTION;
  169.                 break;
  170.             case "*":
  171.                 result=MULTIPLICATION;
  172.                 break;
  173.             case "/":
  174.                 result=DIVISION;
  175.                 break;
  176.             default:
  177. //                System.out.println("不存在该运算符");
  178.                 result=0;
  179.         }
  180.         return result;
  181.     }
  182. }