1. 引言
本文将深入探讨数学表达式中缀表示法转后缀表示法的算法原理及Java实现。后缀表达式（逆波兰表示法）在计算机科学中具有重要地位，尤其在表达式求值场景下优势明显。
2. Java中的表达式
编程语言如Java支持定义和处理多种数学表达式。表达式由变量、常量和运算符组合而成，常见类型包括算术表达式和逻辑表达式。
2.1. 算术表达式
算术表达式包含加(+)、减(-)、乘(*)、除(/)和取模(%)等运算符，与变量或常量结合产生算术结果：
int x = 100;
int y = 50;
int sum = x + y;
int prod = x * y;
int remainder = x % y;
2.2. 逻辑表达式
逻辑表达式使用逻辑运算符替代算术运算符，常见运算符包括逻辑与(AND)、或(OR)、非(NOT)和异或(XOR)：
boolean andResult = (true && false); // 逻辑与
boolean orResult = (true || false); // 逻辑或
boolean notResult = !false; // 逻辑非
关系表达式主要用于比较逻辑，产生布尔值true/false：
int x = 10;
int y = 8;
boolean bigger = x > y; // true
3. 表达式表示法
数学表达式有不同表示方式，称为**表示法(Notation)**，根据运算符和操作数的相对位置区分。
3.1. 中缀表示法
中缀表示法中运算符位于操作数之间，是最常见的表达式形式：
int sum = (a + b) + (c * d);
⚠️ 运算符优先级会导致歧义，需使用括号明确优先级。
3.2. 前缀表示法
前缀表示法（波兰表示法）中运算符位于操作数之前：
int result = * + a b - c d;
3.3. 后缀表示法
后缀表示法（逆波兰表示法）中运算符位于操作数之后：
int result = a b + c d - *;
✅ 前缀和后缀表示法消除了运算符优先级歧义，无需括号，在表达式求值中效率更高。
4. 问题定义
给定中缀表达式作为输入，设计算法将其转换为后缀表达式（逆波兰表示法）。
示例：
输入: (a + b) * (c - d)
输出: ab+cd-*
输入: a+b*(c^d-e)^(f+g*h)-i
输出: abcd^e-fgh*+^*+i-
输入始终是有效中缀表达式，无需额外验证。
5. 解决方案
将问题分解为多个子步骤逐步解决。
5.1. 运算符与操作数识别
输入是字符串形式的中缀表达式，实现转换前需区分运算符和操作数。操作数可以是大小写英文字母：
private boolean isOperand(char ch) {
return (ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z');
}
输入包含2种括号字符和5种运算符（除操作数外）。
5.2. 优先级与结合性
定义运算符优先级并分配整数值：
^（幂运算）优先级最高（3）*和/优先级次之（2）+和-优先级最低（1）
int getPrecedenceScore(char ch) {
switch (ch) {
case '^':
return 3;
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
}
return -1;
}
相同优先级运算符的扫描顺序（结合性）通常为左到右，幂运算例外（右到左）：
char associativity(char ch) {
if (ch == '^') {
return 'R';
}
return 'L';
}
6. 转换算法
中缀表达式中运算符引用其相邻操作数，而后缀表达式中运算符引用其前两个操作数。转换过程需处理嵌套括号，最内层括号优先转换，这种后进先出特性暗示使用栈数据结构。
6.1. 栈与优先级条件
使用栈跟踪运算符，需定义规则决定运算符加入后缀表达式还是保留在栈中：
- 遇到运算符时，若栈为空则直接压栈
- 若栈非空，比较当前运算符与栈顶运算符优先级：
- 当前运算符优先级高于栈顶运算符时压栈
- 优先级相等且结合性为左到右时也压栈
核心逻辑封装如下：
boolean operatorPrecedenceCondition(String infix, int i, Stack<Character> stack) {
return getPrecedenceScore(infix.charAt(i)) < getPrecedenceScore(stack.peek())
|| getPrecedenceScore(infix.charAt(i)) == getPrecedenceScore(stack.peek())
&& associativity(infix.charAt(i)) == 'L';
}
6.2. 扫描与转换流程
完整转换算法步骤：
- 遍历输入字符串
- 操作数直接加入结果
- 运算符按优先级条件处理：
- 满足条件则弹出栈顶运算符到结果
- 当前运算符压栈
- 扫描结束后弹出栈中所有运算符
String infixToPostfix(String infix) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
if (isOperand(ch)) {
result.append(ch);
} else {
while (!stack.isEmpty() && (operatorPrecedenceCondition(infix, i, stack))) {
result.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}
6.3. 算法执行示例
以表达式 a + b * c - d 为例：
符号 结果 栈
a a []
+ a [+]
b ab [+]
* ab [+,*]
c abc [+,*]
- abc*+ [-]
d abc*+d- []
最终后缀表达式：abc*+d-
6.4. 带括号的转换算法
中缀表达式常用括号解决优先级歧义，需调整算法处理括号：
- 遇到
(直接压栈 - 遇到
)弹出栈中运算符直到(
改进后的完整实现：
String infixToPostfix(String infix) {
StringBuilder result = new StringBuilder();
Stack<Character> stack = new Stack<>();
for (int i = 0; i < infix.length(); i++) {
char ch = infix.charAt(i);
if (isOperand(ch)) {
result.append(ch);
} else if (ch == '(') {
stack.push(ch);
} else if (ch == ')') {
while (!stack.isEmpty() && stack.peek() != '(') {
result.append(stack.pop());
}
stack.pop(); // 弹出 '('
} else {
while (!stack.isEmpty() && (operatorPrecedenceCondition(infix, i, stack))) {
result.append(stack.pop());
}
stack.push(ch);
}
}
while (!stack.isEmpty()) {
result.append(stack.pop());
}
return result.toString();
}
带括号表达式 (a+b)*(c-d) 的转换过程：
符号 结果 栈
( [] [(]
a a [(]
+ a [(,+]
b ab [(,+]
) ab+ []
* ab+ [*]
( ab+ [*,(]
c ab+c [*,(]
- ab+c [*,(,-]
d ab+cd [*,(,-]
) ab+cd-* []
最终结果：ab+cd-*
7. 补充思考
虽然中缀表达式更符合人类阅读习惯，但后缀表达式具有显著优势：
- 无需括号：操作数和运算符的顺序已明确运算顺序
- 消除歧义：彻底解决运算符优先级和结合性导致的歧义
- 计算效率：天然适合栈结构求值，成为编程语言实现的事实标准
8. 总结
本文系统介绍了数学表达式的三种表示法（中缀、前缀、后缀），重点阐述了中缀转后缀的算法原理及Java实现。通过示例演示了算法执行过程，并展示了带括号表达式的处理方案。
本文源代码可在 GitHub 获取。