Java 实例 – 利用堆栈将中缀表达式转换成后缀表达式（超详细）

Java 实例 – 利用堆栈将中缀表达式转换成后缀表达式

在日常编程中，我们经常会遇到表达式求值的问题，比如计算器、公式解析、编译器前端等场景。而表达式有多种写法，其中最常见的是中缀表达式，例如 3 + 4 * 5，它的特点是运算符在两个操作数之间。但计算机处理这种表达式时效率不高，因为需要考虑运算符优先级和括号。

这时候，后缀表达式（也叫逆波兰表达式）就派上用场了。它的形式是 3 4 5 * +，运算符放在操作数之后。这种写法的好处是：无需括号、无需考虑优先级，可以直接用栈结构从左到右顺序处理，非常高效。

今天我们就来通过一个经典的 Java 实例，深入理解如何用堆栈（Stack）将中缀表达式转换为后缀表达式。整个过程不仅锻炼了我们对数据结构的理解，也提升了对表达式处理的实战能力。

为什么需要中缀转后缀？

想象一下，你正在做一道数学题：(3 + 4) * 5。你看到括号，先算括号里的 3 + 4，再乘以 5。这个顺序是人为规定的，但计算机并不“懂”括号。它必须通过规则来判断。

中缀表达式虽然直观，但计算机处理起来复杂，因为：

• 运算符有优先级（如 * 比 + 优先）
• 括号改变了运算顺序
• 需要临时保存中间结果

而后缀表达式解决了这些问题。只要我们能将中缀表达式转换为后缀，就可以用一个简单的栈机制来求值。

这就像把“人话”翻译成“机器能听懂的话”——中缀是自然语言，后缀是机器语言。

核心思想：利用堆栈处理运算符优先级

转换的核心思想是：

遇到操作数就直接输出；遇到运算符，根据优先级决定是否压入栈，或者先弹出栈顶的高优先级运算符。

我们用一个栈来暂存运算符。栈的特点是“后进先出”，正好符合运算优先级的“先处理高优先级”的逻辑。

运算符优先级规则（关键）

括号的优先级最低，目的是让括号内部的表达式先算完。当遇到右括号 ) 时，就要不断弹出栈顶元素，直到遇到左括号 ( 为止。

实现步骤详解

我们分三步来实现这个转换过程：

1. 从左到右遍历中缀表达式中的每一个字符
2. 根据字符类型进行不同处理
3. 最终输出后缀表达式

下面是一个完整的 Java 实现，每一步都有详细注释。

import java.util.*;

public class InfixToPostfix {

    // 判断是否为操作数（数字）
    private static boolean isOperand(char ch) {
        return Character.isDigit(ch);
    }

    // 判断是否为运算符
    private static boolean isOperator(char ch) {
        return ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^';
    }

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

    // 主方法：将中缀表达式转换为后缀表达式
    public static String infixToPostfix(String infix) {
        StringBuilder postfix = new StringBuilder(); // 存储结果后缀表达式
        Stack<Character> operatorStack = new Stack<>(); // 用于暂存运算符的栈

        // 遍历中缀表达式中的每个字符
        for (int i = 0; i < infix.length(); i++) {
            char ch = infix.charAt(i);

            // 1. 如果是操作数（数字），直接添加到结果中
            if (isOperand(ch)) {
                postfix.append(ch);
            }

            // 2. 如果是左括号 '('，压入栈
            else if (ch == '(') {
                operatorStack.push(ch);
            }

            // 3. 如果是右括号 ')'，弹出栈中元素直到遇到左括号
            else if (ch == ')') {
                while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
                    postfix.append(operatorStack.pop());
                }
                operatorStack.pop(); // 弹出左括号，不输出
            }

            // 4. 如果是运算符，处理优先级
            else if (isOperator(ch)) {
                // 弹出栈顶中优先级大于等于当前运算符的运算符
                while (!operatorStack.isEmpty() &&
                       operatorStack.peek() != '(' && // 遇到左括号停止
                       getPrecedence(operatorStack.peek()) >= getPrecedence(ch)) {
                    postfix.append(operatorStack.pop());
                }
                // 当前运算符入栈
                operatorStack.push(ch);
            }

            // 5. 空格跳过（可选处理）
            else if (ch == ' ') {
                continue;
            }
        }

        // 4. 遍历结束后，将栈中剩余的运算符全部弹出
        while (!operatorStack.isEmpty()) {
            postfix.append(operatorStack.pop());
        }

        return postfix.toString();
    }

    // 测试方法
    public static void main(String[] args) {
        String infixExpression = "3 + 4 * 5";
        String postfixExpression = infixToPostfix(infixExpression);
        System.out.println("中缀表达式: " + infixExpression);
        System.out.println("后缀表达式: " + postfixExpression);
    }
}

关键代码逻辑拆解

我们来逐行分析几个关键点。

1. 操作数处理

if (isOperand(ch)) {
    postfix.append(ch);
}

当遇到数字（如 3、4），直接加到结果字符串中。这就像把“数字”直接搬进输出区，不加任何处理。

2. 括号处理

else if (ch == '(') {
    operatorStack.push(ch);
}

左括号直接压入栈。它是一个“标记”，表示括号内的表达式需要优先处理。

else if (ch == ')') {
    while (!operatorStack.isEmpty() && operatorStack.peek() != '(') {
        postfix.append(operatorStack.pop());
    }
    operatorStack.pop(); // 弹出左括号
}

遇到右括号时，不断弹出栈顶元素，直到遇到左括号为止。这个过程相当于“把括号里的内容先处理完”。

3. 运算符优先级处理（最核心）

while (!operatorStack.isEmpty() &&
       operatorStack.peek() != '(' &&
       getPrecedence(operatorStack.peek()) >= getPrecedence(ch)) {
    postfix.append(operatorStack.pop());
}
operatorStack.push(ch);

这里的关键是：只有当栈顶运算符优先级大于等于当前运算符时，才弹出。

比如 3 + 4 * 5：

• 遇到 +，栈空，直接压入
• 遇到 *，栈顶是 +，优先级 1 < 2，所以 * 直接入栈
• 最终结果是 3 4 5 * +，正确！

如果写成 3 * 4 + 5，* 会先入栈，+ 时比较 * 优先级更高，所以先弹出 *，再压入 +，结果是 3 4 * 5 +，正确。

实际案例演示

我们来测试几个常见表达式：

这些结果都可以通过上述代码验证。我们也可以扩展支持小数、负数，但需要增加对负号的判断（比如 -3 是负数，不是减号）。

常见误区与调试建议

1. 忽略空格：输入中可能有空格，比如 3 + 4。代码中我们用 ch == ' ' 跳过，避免误判。
2. 括号不匹配：如果输入 3 + (4 * 5，没有右括号，程序可能抛出异常。实际项目中应加校验。
3. 负数处理：如 -3 + 4，第一个 - 是负号，不是运算符。需特殊处理（通常在解析时判断前一个字符是否为操作数或左括号）。
4. 栈为空时弹出：在 pop() 前一定要检查 isEmpty()，否则会抛出异常。

小结与延伸思考

通过这个 Java 实例，我们不仅学会了如何将中缀表达式转为后缀表达式，更深入理解了堆栈在表达式处理中的核心作用。它像一个“临时工”，把高优先级的运算符先存起来，等条件成熟再“派上用场”。

这个技术广泛应用于：

• 编译器词法分析与语法分析
• 计算器类应用（如 Android、桌面计算器）
• 公式引擎（如 Excel 的表达式求值）

下一步，你可以尝试：

• 实现后缀表达式求值（只需一个栈）
• 支持小数和负数
• 添加错误处理机制（如括号不匹配、非法字符）

掌握这一技能，不仅能提升你的算法思维，还能让你在面试中脱颖而出。

最后提醒

Java 实例 – 利用堆栈将中缀表达式转换成后缀表达式，是一个兼具理论深度和实践价值的典型问题。它结合了数据结构（栈）、算法逻辑（优先级判断）和字符串处理，是学习编程进阶的绝佳切入点。

别怕复杂，一步步来。当你第一次看到 3 + 4 * 5 被正确转换为 3 4 5 * + 时，那种“原来如此”的成就感，是代码世界最美的风景。