JAVA: 实现 Infix To Postfix（中缀到后缀转换）算法 —— 教学详解

1. 项目背景详细介绍

在计算机科学中，表达式的解析与求值是编译原理、解释器、计算器设计中的重要环节。我们常用的算术表达式通常是 中缀表达式（Infix Expression），例如：

A + B * C - D

这种表达方式非常直观，但对于计算机来说却不够直接，因为它必须处理 运算符优先级 与 括号 等规则才能正确求值。

相比之下，后缀表达式（Postfix Expression，也称逆波兰表达式 RPN） 更适合计算机处理，因为它不需要括号，也不依赖运算符优先级规则。例如：

A + B * C - D

转换成后缀表达式为：

A B C * + D -

计算机在读取后缀表达式时，只需用一个 栈（Stack） 就能高效求值。

因此，在实际开发中，编写 中缀转后缀算法 是许多计算器、编译器以及表达式解析器的基础。

---

2. 项目需求详细介绍

需求目标：

• 输入：一个 中缀表达式（例如 "A+B*C-D"）。

• 输出：一个 后缀表达式（例如 "ABC*+D-"）。

功能要求：

1. 处理基本的运算符：+ - * / ^；

2. 处理括号 ( 和 )；

3. 正确应用运算符优先级和结合律规则；

4. 支持字母（A、B、C）、数字（1、2、3）作为操作数；

5. 使用 Java 栈 实现。

---

3. 相关技术详细介绍

3.1 中缀表达式（Infix Expression）

• 运算符位于操作数之间；

• 例如 A + B；

• 人类直观，但计算机难以解析。

3.2 后缀表达式（Postfix Expression / RPN）

• 运算符位于操作数之后；

• 例如 A B +；

• 无需括号，计算机只需顺序读取并用栈求值。

3.3 算法核心 —— Shunting Yard Algorithm

该算法由 Edsger Dijkstra 提出，用于将中缀表达式转换为后缀表达式。

核心思想：

• 遍历中缀表达式；

• 遇到操作数，直接输出；

• 遇到运算符，按照优先级处理栈顶运算符；

• 遇到 ( 入栈，遇到 ) 出栈直到匹配 (；

• 最后把栈中剩余运算符依次输出。

3.4 运算符优先级与结合律

优先级：

• ^ 最高（右结合）

• * / 次高（左结合）

• + - 最低（左结合）

结合律：

• 左结合：从左到右计算，如 A - B - C = (A - B) - C

• 右结合：从右到左计算，如 A ^ B ^ C = A ^ (B ^ C)

---

4. 实现思路详细介绍

1. 创建一个 Stack<Character> 用于保存运算符。

2. 创建一个 StringBuilder 用于拼接后缀表达式。

3. 遍历中缀表达式：

   • 如果是 操作数（字母/数字），直接加入结果；

   • 如果是 左括号 (，入栈；

   • 如果是 右括号 )，弹出运算符直到遇到左括号；

   • 如果是 运算符：

     • 弹出栈顶运算符，直到栈顶运算符优先级低于当前运算符；

     • 然后将当前运算符入栈。

4. 遍历完成后，将栈中剩余运算符依次弹出并加入结果。

---

5. 完整实现代码

import java.util.Stack;

// =============================================
// Infix To Postfix 转换类
// =============================================
class InfixToPostfix {

    // 判断字符是否为操作数（字母或数字）
    private static boolean isOperand(char c) {
        return Character.isLetterOrDigit(c);
    }

    // 获取运算符的优先级
    private static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }

    // 判断运算符是否是右结合
    private static boolean isRightAssociative(char op) {
        return op == '^';
    }

    // 中缀转后缀算法
    public static String convert(String infix) {
        StringBuilder result = new StringBuilder();
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < infix.length(); i++) {
            char c = infix.charAt(i);

            // 1. 操作数，直接加入结果
            if (isOperand(c)) {
                result.append(c);
            }
            // 2. 左括号，入栈
            else if (c == '(') {
                stack.push(c);
            }
            // 3. 右括号，弹出直到遇到左括号
            else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    result.append(stack.pop());
                }
                if (!stack.isEmpty() && stack.peek() == '(') {
                    stack.pop();
                }
            }
            // 4. 运算符
            else {
                while (!stack.isEmpty() &&
                        precedence(stack.peek()) > precedence(c) ||
                        (!isRightAssociative(c) && precedence(stack.peek()) == precedence(c))) {
                    if (stack.peek() == '(') break;
                    result.append(stack.pop());
                }
                stack.push(c);
            }
        }

        // 5. 处理栈中剩余运算符
        while (!stack.isEmpty()) {
            result.append(stack.pop());
        }

        return result.toString();
    }
}

// =============================================
// 测试类 Main
// =============================================
public class Main {
    public static void main(String[] args) {
        String infix = "A+B*(C^D-E)^(F+G*H)-I";
        System.out.println("中缀表达式: " + infix);

        String postfix = InfixToPostfix.convert(infix);
        System.out.println("后缀表达式: " + postfix);
    }
}

6. 代码详细解读

1. isOperand 方法

   • 判断当前字符是否是字母或数字；

   • 如果是，直接加入结果字符串。

2. precedence 方法

   • 定义运算符的优先级；

   • + - → 1，* / → 2，^ → 3。

3. isRightAssociative 方法

   • 判断运算符是否是右结合；

   • 只有 ^ 是右结合。

4. convert 方法

   • 核心逻辑：遍历字符串，区分操作数、运算符和括号；

   • 利用栈存储运算符，保证出栈顺序符合优先级；

   • 最终输出拼接成后缀表达式。

5. 测试类 Main

   • 输入：A+B*(C^D-E)^(F+G*H)-I

   • 输出：ABCD^E-FGH*+^*+I-

---

7. 项目详细总结

• 中缀表达式对人类友好，但对计算机不友好；

• 后缀表达式对计算机非常友好，可以直接用栈求值；

• 本项目使用了 栈 与 运算符优先级规则 实现了中缀到后缀的转换；

• 算法核心基于 Dijkstra 的 Shunting Yard Algorithm；

• 实现简单高效，能处理括号、优先级、结合律等复杂情况。

---

8. 项目常见问题及解答

Q1：如果输入表达式中有空格怎么办？
答：可以在遍历时忽略空格，或者预处理去掉空格。

Q2：能否支持多位数字？
答：需要改写 isOperand 逻辑，将连续的数字拼接成一个完整数字。

Q3：如果有非法字符怎么办？
答：可以增加异常处理，当遇到未知字符时抛出错误。

Q4：是否能直接在转换时求值？
答：可以，但更常见的做法是先转换成后缀表达式，再写一个 后缀求值算法。

---

9. 扩展方向与性能优化

1. 支持多位数和小数

   • 需要修改操作数解析逻辑；

   • 例如输入 "12+3.5*4" 也能正确解析。

2. 支持更多运算符

   • 如取模 %、逻辑运算符 &&、||。

3. 后缀表达式求值扩展

   • 在完成转换后，可以进一步实现 后缀表达式求值算法。

4. 表达式树扩展

   • 将中缀表达式转为 表达式树，再基于树进行前序/后序遍历。