前缀表达式（波兰表达式）

介绍

前缀表达式的运算符位与操作数之前

举例

(3+4)5-6对应的前缀表达式就是-+3456

前缀表达式的计算机求值

从右至左扫描表达式，遇到数字时，先将数字压入栈堆，遇到运算符时，弹出栈顶的两个数，用运算符对它们做相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式最左端，最后运算得出的值即为表达式的结果

中缀表达式

介绍

中缀表达式就是常见的运算表达式

举例

(3+4)*5-6

中缀表达式的计算机求值

中缀表达式的求值是我们最熟悉的，但是对于计算机来说却不好操作，因此，在计算结果时，往往会将中缀表达式转成其他表达式来操作

后缀表达式（逆波兰表达式）

介绍

后缀表达式又叫逆波兰表达式，与前缀表达式相似，只是运算符位于操作数之后

举例

(3+4)5-6对应的后缀表达式就是35+56-

后缀表达式的计算机求值

从左至右扫描表达式，遇到数字时，将数字压入栈堆，遇到运算符时，弹出栈顶的两个数，用运算符对它们作相应的计算（栈顶元素和次顶元素），并将结果入栈；重复上述过程直到表达式的最右端，最后运算得出的值即为表达式结果

表达式之间的相互转换

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

步骤分析

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

应用

逆波兰计算器

要求

  1. 输入一个逆波兰表达式（后缀表达式），使用栈（Stark），计算其结果
  2. 支持小括号和多位数整数，因为这里我们主要讲的是数据结构，因此计算器进行简化，值支持对整数的计算
  3. 思路分析
    • 从左至右扫描表达式
    • 遇到数字时，将数字压入栈堆
    • 遇到运算符时，弹出栈顶的两个数，用运算符对它们作相应的计算（栈顶元素和次顶元素），并将结果入栈
    • 重复上述过程直到表达式的最右端，最后运算得出的值即为表达式结果
  4. 代码实现 ```java package inversepolishcalculator;

import java.util.ArrayList; import java.util.List; import java.util.Stack;

public class PolandNotation {

  1. public static void main(String[] args) {
  3.     //先定义一个逆波兰表达式
  4.     //为了方便，使用空格隔开
  6.     //(3 + 4) * 5 - 6 => 3 4 + 5 * 6 -
  7.     //String suffixExpression = "3 4 + 5 * 6 -";
  9.     //4 * 5 - 8 + 60 + 8 / 2 => 4 5 * 8 - 60 + 8 2 / +
  10.     String suffixExpression = "4 5 * 8 - 60 + 8 2 / +";
  12.     //1. 先将suffixExpression放到ArrayList中
  13.     List<String> rpnList = getListString(suffixExpression);
  14.     System.out.println(rpnList);
  16.     //2. 将ArrayList传递给一个方法，遍历ArrayList配合栈完成计算
  17.     int result = calculate(rpnList);
  18.     System.out.println(result);
  19. }
  21. //将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
  22. public static List<String> getListString(String suffixExpression) {
  23.     //将表达式分割
  24.     String[] split = suffixExpression.split(" ");
  25.     List<String> list = new ArrayList<>();
  26.     for (String ele : split) {
  27.         list.add(ele);
  28.     }
  29.     return list;
  30. }
  32. //完成对逆波兰表达式的运算
  33. public static int calculate(List<String> ls) {
  34.     //创建栈，只需要一个栈即可
  35.     Stack<String> stack = new Stack<>();
  36.     //遍历ls
  37.     for (String item : ls) {
  38.         //这里使用正则表达式来取出数
  39.         if(item.matches("\\d+")) {//匹配多位数
  40.             //入栈
  41.             stack.push(item);
  42.         } else {
  43.             //pop出两个数，并进行计算,再入栈
  44.             int number1 = Integer.parseInt(stack.pop());
  45.             int number2 = Integer.parseInt(stack.pop());
  46.             int result = 0;
  47.             if (item.equals("+")) {
  48.                 result = number2 + number1;
  49.             } else if (item.equals("-")) {
  50.                 result = number2 - number1;
  51.             } else if (item.equals("*")) {
  52.                 result = number2 * number1;
  53.             } else if (item.equals("/")) {
  54.                 result = number2 / number1;
  55.             } else {
  56.                 throw new RuntimeException("运算符有误，请核对后再输入...");
  57.             }
  58.             //把result入栈
  59.             stack.push(result + "");
  60.         }
  61.     }
  62.     //最后留在stack中的数据就是运算结果
  63.     return Integer.parseInt(stack.pop());
  64. }

}

  2. 5. 实现中缀表达式转后缀表达式，并实现该计算器
  3. ```java
  4. package inversepolishcalculator;
  6. import java.util.ArrayList;
  7. import java.util.List;
  8. import java.util.Stack;
  10. public class PolandNotation {
  12.     public static void main(String[] args) {
  14.         //完成将一个中缀表达式转为后缀表达式的功能
  15.         //说明：
  16.         //1. 1+((2+3)*4)-5 => 1 2 3 + 4 * + 5 -
  17.         //2. 因为直接对str进行操作，不方便，因此，先将字符串转为一个中缀表达式的List
  18.         //   "1+((2+3)*4)-5"  =>  [1,+,(,(,2,+,3,),*,4,),-,5]
  19.         //3. 将得到的中缀表达式对应的List装化为后缀表达式对应的List
  20.         //   [1,+,(,(,2,+,3,),*,4,),-,5]  =>  [1,2,3,+,4,*,+,5,-]
  23.         String expression = "1+((2+3)*4)-5"; 
  25.         //中缀表达式字符串 转 中缀表达式List
  26.         List<String> infixExpressionList = toInfixExpression(expression);
  27.         System.out.println(infixExpressionList);
  28.         //中缀表达式List 转 后缀表达式List
  29.         List<String> postfixExpressionList = parseSuffixExpressionList(infixExpressionList);
  30.         System.out.println(postfixExpressionList);
  31.         //计算得到结果
  32.         int result = calculate(postfixExpressionList);
  33.         System.out.println(result);
  34.     }
  36.     //将得到的中缀表达式对应的List装化为后缀表达式对应的List
  37.     public static List<String> parseSuffixExpressionList(List<String> ls) {
  38.         //定义两个站
  39.         Stack<String> s1 = new Stack<>();  //符号栈
  40.         //因为s2在整个装换过程中，没有pop操作，而且最后需要逆序输出，为方便没直接使用List<String> s2来存储
  41.         //Stack<String> s2 = new Stack<>();  //中间结果栈
  42.         List<String> s2 = new ArrayList<>();
  44.         //遍历ls
  45.         for (String item : ls) {
  46.             //如果是一个数，就直接加入到s2
  47.             if (item.matches("\\d+")) {
  48.                 s2.add(item);
  49.             } else if (item.equals("(")) {
  50.                 s1.push(item);
  51.             } else if (item.equals(")")) {//如果是右括号")"，则一次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时完成了一对括号的丢弃
  52.                 while (!s1.peek().equals("(")) {
  53.                     s2.add(s1.pop());
  54.                 }
  55.                 s1.pop();
  56.             } else  {
  57.                 //当ite的优先级小于或者等于s1栈顶的运算符，就应该将s1栈顶的运算符弹出并压入到s2中，再次把item与s1中的栈顶运算符进行比较
  58.                 while (s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {
  59.                     s2.add(s1.pop());
  60.                 }
  61.                 //还需要将item压入栈中
  62.                 s1.push(item);
  63.             }
  64.         }
  66.         //最后需要将s1剩余的加入到s2中
  67.         while (s1.size() != 0){
  68.             s2.add(s1.pop());
  69.         }
  71.         return s2;
  72.     }
  76.     //将中缀表达式转为对应的List
  77.     public static List<String> toInfixExpression(String s) {
  78.         //定义一个List，存放
  79.         List<String> ls = new ArrayList<>();
  80.         int i = 0;//这是一个指针，用于遍历中缀字符串s
  81.         String str;//对多位数的拼接
  82.         char c; //每遍历一个字符，就放c
  83.         do {
  84.             //如果c是一个非数字，就需要加入到ls
  85.             if ( (c=s.charAt(i)) < 48 || (c=s.charAt(i)) > 57 ) {
  86.                 ls.add(c + "");
  87.                 i++; //后移
  88.             } else { //如果是一个数，需要考虑多位数的问题
  89.                 str = ""; //先将str置为空
  90.                 while (i < s.length() && ((c=s.charAt(i)) >= 48 && (c=s.charAt(i)) <= 57)) {
  91.                     str += c;
  92.                     i++;
  93.                 }
  94.                 ls.add(str);
  95.             }
  96.         } while (i < s.length());
  97.         return ls;
  98.     }
  100.     //将一个逆波兰表达式，依次将数据和运算符放到ArrayList中
  101.     public static List<String> getListString(String suffixExpression) {
  102.         //将表达式分割
  103.         String[] split = suffixExpression.split(" ");
  104.         List<String> list = new ArrayList<>();
  105.         for (String ele : split) {
  106.             list.add(ele);
  107.         }
  108.         return list;
  109.     }
  111.     //完成对逆波兰表达式的运算
  112.     public static int calculate(List<String> ls) {
  113.         //创建栈，只需要一个栈即可
  114.         Stack<String> stack = new Stack<>();
  115.         //遍历ls
  116.         for (String item : ls) {
  117.             //这里使用正则表达式来取出数
  118.             if(item.matches("\\d+")) {//匹配多位数
  119.                 //入栈
  120.                 stack.push(item);
  121.             } else {
  122.                 //pop出两个数，并进行计算,再入栈
  123.                 int number1 = Integer.parseInt(stack.pop());
  124.                 int number2 = Integer.parseInt(stack.pop());
  125.                 int result = 0;
  126.                 if (item.equals("+")) {
  127.                     result = number2 + number1;
  128.                 } else if (item.equals("-")) {
  129.                     result = number2 - number1;
  130.                 } else if (item.equals("*")) {
  131.                     result = number2 * number1;
  132.                 } else if (item.equals("/")) {
  133.                     result = number2 / number1;
  134.                 } else {
  135.                     throw new RuntimeException("运算符有误，请核对后再输入...");
  136.                 }
  137.                 //把result入栈
  138.                 stack.push(result + "");
  139.             }
  140.         }
  141.         //最后留在stack中的数据就是运算结果
  142.         return Integer.parseInt(stack.pop());
  143.     }
  145. }
  147. //编写一个类，Operation，可返回一个运算符对应的优先级
  148. class Operation {
  149.     private static int ADD = 1;
  150.     private static int SUB = 1;
  151.     private static int MUL = 2;
  152.     private static int DIV = 2;
  154.     //写一个方法返回对应的优先级数字
  155.     public static int getValue(String operation) {
  156.         int result = 0;
  157.         switch (operation) {
  158.             case "+":
  159.                 result = ADD;
  160.                 break;
  161.             case "-":
  162.                 result = SUB;
  163.                 break;
  164.             case "*":
  165.                 result = MUL;
  166.                 break;
  167.             case "/":
  168.                 result = DIV;
  169.                 break;
  170.             default:
  171.                 break;
  172.         }
  173.         return result;
  174.     }
  175. }