中缀表达式转逆波兰表达式（后缀表达式）_中缀表达式转波兰表达式

  中缀表达式是人熟悉的表达式，对人友好，但是对计算机就不太友好了，需要关注运算符的优先级，例如 3 + 5 * 6，需要先计算 5 * 6

  前缀表达式与后缀表达式对计算机相对友好，对人就不太友好了，不需要关注运算符的优先级。

---

  前缀表达式，也称波兰表达式，运算符写在操作数前面。

  例如 (3 + 4) * 5 - 6 对应的前缀表达式为：- * + 3 4 5 6

  百度百科——前缀表达式

---

  后缀表达式，也称逆波兰表达式，运算符写在操作数后面。

  例如 (3 + 4) * 5 - 6 对应的后缀表达式为：3 4 + 5 * 6 -

  百度百科——后缀表达式

---

  求值规则：自右向左扫描表达式，遇到数字时压栈，遇到运算符则弹出栈顶两个数做对应运算，并将结果压入栈中。

  中缀表达式：( 3 + 4 ) * 5 - 6

  前缀表达式：- * + 3 4 5 6

执行计算过程：

  1 将表达式 自右向左 扫描，将 6 5 4 3 依次压入栈中，此时栈存储如下：

  2 遇到 + 时，将 3 、4 弹出，计算 3 + 4，然后将结果 7 压入栈中，此时栈存储如下：

  3 遇到 * 时，将 7、5 弹出，计算 7 * 5，然后将结果 35 压入栈中，此时栈存储如下：

  4 遇到 - 时，将 35、6 弹出，计算 35 - 6，然后将结果 29 压入栈中，此时栈存储如下：

---

  求值规则：从左至右 依次扫描表达式，遇到数字压入栈中，遇到运算符则弹出栈顶两个数做对应运算，并将结果压入栈中。

  中缀表达式：( 3 + 4 ) * 5 - 6

  后缀表达式：3 4 + 5 * 6 -

执行计算过程：

  1 将表达式 从左至右 扫描，将 3、4 压入栈中，此时栈存储如下：

  2 遇到 + 时，将 4、3 弹出，计算 3 + 4，然后将结果 7 压入栈中，此时栈存储如下：

  3 将 5 压入栈中，左边为栈

  4 遇到 * 时，将 5、7 弹出，计算 7 * 5，然后将结果 35 压入栈中，此时栈存储如下：

  5 将 6 压入栈中，此时栈存储如下：

  6 遇到 - 时，将 35、6 弹出，计算 35 - 6，然后将结果 29 压入栈中，此时栈存储如下：

---

  转化规则：把每个运算符都移到它的两个操作数的后面，然后删除括号即可。

  下面表以 2 * ( ( 5 - 3 ) * 4 ) - 16 / 2 作为样例演示转换的步骤。

  创建两个栈 a 和 b，a 用于存储转换过程，b 用于临时存储操作符与小括号。

  每次扫描到的 数字 直接压入 a 栈

  每次扫描到的符号 x 需要与 b 栈顶部的符号 y 比较优先级，如果 x > y，则 x 压入 b 栈，如果 x <= y，将 b 栈顶元素弹出后压入 a，继续比较 x 与 下一个 y。

  最终获取的表达式为：2 5 3 - 4 * * 16 2 / -，需要将 a 中的元素弹出后再逆序。

---

实现思路与步骤：

• 1 将表达式字符串中的符号转转存到 list 集合 ls 中，方便遍历
  • 首先遍历字符串，对字符串中的每个字符进行处理。
  • 如果遍历到操作符号，如 + - * / ( ) 直接添加到 ls 中。
  • 如果遍历到数，需要判断是否为多位数。
    • 如果是单位数，直接添加到 ls 中。
    • 如果是多位数，需要拼接这个多位数，然后再添加到 ls 中。
  • 最后将转存后的 ls 返回。

public static List<String> stringToArray(String s) {
    List<String> ls = new ArrayList<>();
    int i = 0;  // 遍历 String 的索引
    String str;     // 拼接多位数
    char c;     // 每次遍历到的字符
    do {
        c = s.charAt(i);
        if (isOperator(c)) {  // 如果遍历到的是符号，直接添加到 list
            ls.add("" + c);
            i++;
        } else if (isNumber(c)) { //  如果遍历到的是一个数，需要判断是否为多位数，用 str 拼接
            str = "";  // 先将 str 清空
            while (i < s.length() && isNumber(c = s.charAt(i))) {
                str += c;   // 拼接多位数
                i++;
            }
            ls.add(str);
        } else {  // 如果遍历到其他符号，直接滤过，如空格之类
            i++;
        }
    } while (i < s.length());
    return ls;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

判断是否为指定符号

public static boolean isOperator(char c) {
    // 只有当遍历到以下符号时，才存储集合，其他符号过滤
    return c == '+' || c == '-' || c == '*' || c == '/' || c == '(' || c == ')';
}
1
2
3
4

判断是否为数字

public static boolean isNumber(char c) {
	// ascll码中数字 0 ~ 9 对应 48 ~ 57
    return 48 <= c && c <= 57;      
}
1
2
3
4

---

2 将中缀表达式转换为后缀表达式

• 创建两个栈 s1、s2，s1 存储临时字符，s2 存储转换过程。(s2 使用 list 代替栈)
• 遍历后缀表达式的 list
  • 遍历到数字，直接添加到 s2 中。
  • 遍历到符号 + - * / 时，需要与 s1 栈顶符号比较优先级。
    • 如果比 s1 栈顶符号优先级高，则直接压入 s1。
    • 反之，将 s1 栈顶元素弹出并添加到 s2 中，继续与 s1 的次顶元素比较，直至 s1 为空或ls中遍历到的元素优先级高于 s1 栈顶符号。
  • 遍历到 (，直接压入 s1 中。
  • 遍历到 )，弹出 s1 中的符号，直至遇到 (，最后将 ( 弹出，ls 继续向后遍历，这样就删除了一对括号。
• ls 遍历完以后，将 s1 中剩余的符号依次弹出并添加到 s2 中。
• 最终将转换结果 s2 返回即可。

public static List<String> infixConvertToPostfix(List<String> infix) {
    // 创建两个栈，s1 用于存储临时符号
    Stack<String> s1 = new Stack<>();
    // s2 由于没有 pop 操作，并且最终需要逆序输出，所以使用 ArrayList 代替之
    List<String> s2 = new ArrayList<>();
    // 遍历传入的中缀表达式集合
    for (String s : infix) {
        if (s.matches("\\d+")) {  // 正则匹配，匹配到数字，直接添加到 s2
            s2.add(s);
        } else if ("(".equals(s)) {  // 遍历到 (，直接压入 s1
            s1.push(s);
        } else if (")".equals(s)) {  // 遍历到 ) ，弹出 s1 中的符号添加到 s2 中，直至遇到 (
            while (!"(".equals(s1.peek())) {  // peek() 查看栈顶元素
                s2.add(s1.pop());
            }
            s1.pop();  // 当 ( 弹出，消除小括号
        } else {  // 遍历到 + - * /
            // s1 不为空，且当遍历到的符号，小于等于栈顶符号优先级，需要弹栈操作
            // 直到当前符号优先级大于 s1 栈顶元素或 s1 弹空时，结束
            while (!s1.empty() && (getPriority(s) <= getPriority(s1.peek()))) {
                s2.add(s1.pop());  // 将 s1 栈顶符号弹出添加到 s2 中
            }
            // 比较结束后，将当前字符压入 s1 中
            s1.push(s);
        }
    }

    // 将 s1 中剩余符号添加到 s2 中
    while (!s1.empty()) {
        s2.add(s1.pop());
    }
    return s2;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

获取操作符优先级

public static int getPriority(String s) {
    if ("*".equals(s) || "/".equals(s)) {
        return 2;
    }
    if ("+".equals(s) || "-".equals(s)) {
        return 1;
    }
    if ("(".equals(s)) {
        return 0;
    }
    throw new RuntimeException("扫描到未知符号！");
}
1
2
3
4
5
6
7
8
9
10
11
12

• 需要注意的是，栈中永远不会有 )，所以不需要管它。
• 当前遍历到的符号是运算符(+ - * /)，且此时 s1 栈顶元素为 ( 时，应当将运算符入栈，而不是弹出 (，所以将 ( 的优先级设为最小，这并不会影响 ( 的存入操作，因为在前面的 if 条件块中，优先处理了数字和 (，所以不会存在 ( ) 与 s1 栈顶元素比较的情况。

---

• 3 计算后缀表达式的值
  • 创建一个栈 num，用于存储结果。
  • 依次遍历 s2 中的元素，对每次遍历到的元素做相应处理。
    • 遍历到数时，直接压入 num 中。
    • 遍历到运算符时，从 num 中弹出两个数，使用该运算符做运算，并将运算结果结果继续压入 num 中。
  • 最后 num 中只会剩下一个数，将这个数弹出返回即可。

public static int compute(List<String> postFix) {
    Stack<Integer> num = new Stack<>();
    int num1 = 0;  // 接收栈顶数
    int num2 = 0;  // 接收次顶数
    int res = 0;  // 每次计算结果
    for (String s : postFix) {
        if (s.matches("\\d+")) {    // 如果是数，就压栈
            num.push(Integer.parseInt(s));
        } else {
            num1 = num.pop();
            num2 = num.pop();
            switch (s) {
                case "+":
                    res = num2 + num1;
                    break;
                case "-":
                    res = num2 - num1;
                    break;
                case "*":
                    res = num2 * num1;
                    break;
                case "/":
                    res = num2 / num1;
                    break;
                default:
                    throw new RuntimeException("扫描到未知符号！");
            }
            num.push(res);
        }
    }
    return num.pop();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

• 4 测试结果

public static void main(String[] args) {
    String s = "2 * ( ( 5 - 3 ) * 4 ) - 16 / 2";
    // 表达式转换为 list
    List<String> ls = stringToArray(s);
    System.out.println("中缀表达式：" + ls);
    // 中缀表达式 list 转 后缀 list
    List<String> ls2 = infixConvertToPostfix(ls);
    System.out.println("中缀表达式：" + ls2);
    // 计算后缀表达式的值
    int res = compute(ls2);
    System.out.println("计算结果：" + res);
}
1
2
3
4
5
6
7
8
9
10
11
12