异常教程
Java 实例 – 利用堆栈将中缀表达式转换成后缀表达式（建议收藏）
💡一则或许对你有用的小广告
欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论
- 新项目:《从零手撸：仿小红书（微服务架构）》 正在持续爆肝中，基于
Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;- 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;
截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观
前言：为什么需要将中缀表达式转换为后缀表达式？
在编程和数学计算领域，表达式的解析是一个核心问题。日常使用的中缀表达式（如 3 + 4 * 2）虽然直观易读，但计算机在计算时需要将其转换为更高效的后缀表达式（如 3 4 2 * +）。这种转换的核心工具是堆栈（Stack），它通过“先进后出”的特性，完美解决了操作符优先级和括号嵌套的问题。本文将通过一个 Java 实例，深入讲解如何利用堆栈将中缀表达式转换为后缀表达式，并提供可运行的代码示例，帮助读者掌握这一经典算法。
基础知识：中缀表达式与后缀表达式
什么是中缀表达式？
中缀表达式是人类日常使用的表达式形式，例如 5 + 3 或 (a + b) * c。它的特点是操作符位于两个操作数之间，但解析时需要处理复杂的优先级和括号嵌套问题。
什么是后缀表达式？
后缀表达式（Reverse Polish Notation, RPN）将操作符放在操作数之后，例如 5 3 + 或 a b + c *。这种形式的优点是无需考虑优先级，只需按顺序计算即可，非常适合计算机高效处理。
转换的必要性
计算机在解析中缀表达式时需要额外的逻辑来判断优先级和括号，而解析后缀表达式只需一个简单的循环。因此，将中缀表达式转换为后缀表达式是许多编译器和计算器的核心步骤。
算法核心思想：堆栈的“分拣”作用
堆栈的比喻
堆栈可以想象成一个“盘子堆叠机”：每次放入新盘子时，它会压在最上面；取出时，只能取走最上面的盘子。在表达式转换中，堆栈用于暂存操作符，根据优先级决定何时将它们弹出。
转换的三大规则
- 操作数直接输出：遇到数字或变量时，直接追加到结果列表。
- 操作符处理：根据优先级和堆栈顶操作符的优先级，决定是弹出堆栈中的操作符，还是将当前操作符压入堆栈。
- 括号处理：左括号直接压入堆栈；右括号触发弹出操作符，直到遇到左括号为止。
算法步骤详解：以 3 + 4 * 2 为例
步骤 1：初始化堆栈和结果列表
- 堆栈
stack为空。 - 结果列表
output为空。
步骤 2：逐个处理字符
输入字符：3
- 是操作数 → 直接添加到
output→output = ["3"]。
输入字符：+
- 是操作符 → 比较当前操作符
+与堆栈顶（空）的优先级。 - 堆栈为空 → 直接压入
+→stack = ["+"]。
输入字符：4
- 是操作数 → 添加到
output→output = ["3", "4"]。
输入字符：*
- 是操作符 → 当前堆栈顶是
+，优先级低于*→ 将*压入堆栈 →stack = ["+", "*"]。
输入字符：2
- 是操作数 → 添加到
output→output = ["3", "4", "2"]。
步骤 3：处理完所有字符后清空堆栈
- 弹出堆栈中的所有操作符 →
output = ["3", "4", "2", "*", "+"]。
最终后缀表达式为：3 4 2 * +。
操作符优先级表
在代码实现中，需定义操作符的优先级。以下为常见操作符的优先级（数值越大，优先级越高）：
| 操作符 | 优先级 |
|---|---|
( | 0 |
) | 0 |
+ | 1 |
- | 1 |
* | 2 |
/ | 2 |
Java 实现代码详解
类结构设计
import java.util.*;
public class InfixToPostfix {
private static final Map<Character, Integer> precedence = new HashMap<>();
static {
precedence.put('(', 0);
precedence.put('+', 1);
precedence.put('-', 1);
precedence.put('*', 2);
precedence.put('/', 2);
}
public String convert(String infix) {
Stack<Character> stack = new Stack<>();
StringBuilder output = new StringBuilder();
for (char c : infix.toCharArray()) {
if (Character.isDigit(c)) {
output.append(c);
} else if (c == '(') {
stack.push(c);
} else if (c == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
output.append(stack.pop());
}
stack.pop(); // 移除左括号 '('
} else {
while (!stack.isEmpty() && precedence.get(c) <= precedence.get(stack.peek())) {
if (stack.peek() == '(') break; // 遇到左括号停止弹出
output.append(stack.pop());
}
stack.push(c);
}
if (output.length() > 0 && !Character.isDigit(output.charAt(output.length()-1))) {
output.append(' '); // 添加空格分隔符
}
}
while (!stack.isEmpty()) {
output.append(stack.pop());
if (output.length() > 0 && !Character.isDigit(output.charAt(output.length()-1))) {
output.append(' ');
}
}
return output.toString().trim();
}
}
代码关键点解析
- 操作符优先级表：通过
Map<Character, Integer>存储优先级，0表示括号无优先级。 - 括号处理：遇到右括号时，循环弹出堆栈元素直到左括号，并丢弃左括号。
- 操作符压栈逻辑：只有当前操作符优先级高于堆栈顶时才压栈，否则弹出堆栈顶元素。
- 空格分隔符：在操作符前后添加空格，使后缀表达式更易读（如
3 4 +）。
测试案例与调试技巧
测试案例 1：基本表达式
public static void main(String[] args) {
InfixToPostfix converter = new InfixToPostfix();
String infix = "3 + 4 * 2";
System.out.println(converter.convert(infix)); // 输出：3 4 2 * +
}
测试案例 2：含括号的复杂表达式
String infix = "( 5 + 3 ) * 2 - 7";
System.out.println(converter.convert(infix)); // 输出：5 3 + 2 * 7 -
常见问题与调试方法
- 堆栈溢出或死循环：检查括号是否匹配，确保每对
(和)都正确闭合。 - 操作符顺序错误：在代码中添加
System.out.println打印堆栈状态，观察操作符压栈和弹出的时机。 - 数字与操作符粘连：确保输入表达式中的操作符前后有空格，或在代码中增加分隔符处理逻辑。
扩展与优化方向
1. 支持变量和函数调用
可扩展代码以识别变量名（如 a + b）或函数（如 sin(x) + 2），需在 isDigit 判断中加入字母检测。
2. 错误处理
添加对无效字符（如 $）、括号不匹配或空表达式的检查，抛出 IllegalArgumentException。
3. 性能优化
- 使用
Deque替代Stack以获得更好的性能。 - 将
precedence的Map替换为switch语句，减少哈希计算开销。
结论：从理论到实践的跨越
通过本文的讲解和代码示例，我们掌握了堆栈在表达式转换中的核心作用。这一算法不仅是编译原理的基础，也常用于构建简易计算器或表达式求值工具。建议读者尝试以下实践：
- 将代码扩展为支持浮点数运算。
- 实现后缀表达式求值功能。
- 用其他语言（如 Python）重写该算法，对比不同语言的堆栈实现差异。
掌握这一技能后，你不仅能解决技术面试中的经典问题，还能为更复杂的编程项目（如数学库开发）打下坚实基础。编程的魅力，正在于将看似复杂的逻辑，通过巧妙的数据结构与算法，转化为简洁优雅的代码。