1. 简介
在本文中，我们将展示如何将一个用后缀表达式（Postfix Notation）表示的数学表达式转换为对应的表达式树（Expression Tree）。
2. 表达式的表示
在后缀表达式中，运算符始终位于其操作数之后。例如，表达式：
$$ (5 + 2) \times (3 - 1) $$
对应的后缀表达式为：
$$ 5\ 2 + 3\ 1 - \times $$
而表达式树是一种图形化的表达式表示方式：
- 叶子节点代表常量或变量；
- 内部节点代表运算符。
例如，上述表达式可以表示为如下树结构：
后缀表达式不需要括号，因为其计算顺序是明确的，因此它适合用于程序处理。但为了便于阅读和调试，我们通常会将其转换为表达式树。
假设输入为一个后缀表达式数组 $ x = [x_1, x_2, \ldots, x_n] $，其中每个 $ x_i $ 是常量、变量或运算符。我们的目标是将其转换为一棵表达式树。
3. 二元运算符的处理算法
当所有运算符均为二元运算符时（即每个运算符需要两个操作数），我们可以使用栈（Stack）来辅助构建表达式树。
3.1 算法思路
基本思路是：
- 遍历表达式中的每个符号；
- 若为操作数（数字或变量），压入栈；
- 若为运算符，则从栈中弹出两个元素作为其左右子节点，构建新节点后重新压入栈；
- 最终栈中只剩一个元素，即为表达式树的根节点。
3.2 示例伪代码
algorithm ConvertBinaryPostfixExpression(x):
// INPUT
// x = [x1, x2, ..., xn], an array of symbols (constant values, variables, operators)
// representing a postfix expression
// OUTPUT
// The expression tree of x
nodes <- an empty stack
for i <- 1 to n:
if x[i] is not an operator:
nodes.push(x[i])
else:
right <- nodes.pop()
left <- nodes.pop()
new_node <- Node(left, right)
new_node.operator <- x[i]
nodes.push(new_node)
root <- nodes.pop()
return root
3.3 示例执行过程
以表达式 5 2 + 3 1 - × 为例，其构建过程如下图所示：
总共 7 步，正好对应表达式中 7 个符号。
3.4 时间复杂度分析
- 每个操作符最多弹出两个操作数；
- 因此总时间复杂度为 **O(n)**，其中 n 是表达式长度。
3.5 假设与限制
- 表达式必须是合法的后缀表达式；
- 所有运算符必须是二元运算符（如
+,-,*,/）； - 若输入是字符串，需先进行词法分析（Tokenization）；
- 不支持一元运算符（如负号
-5中的-）。
4. 支持任意元数运算符的算法
我们可以将算法扩展，以支持任意元数（Arity）的运算符。例如：
- 一元运算符（如
sin,log）； - 三元运算符（如
a ? b : c）； - 自定义函数（如
max(a, b, c)）。
4.1 算法思路
我们引入一个哈希表 info，用于存储每个运算符的元数（arity）：
algorithm ConvertPostfixExpression(x, info):
// INPUT
// x = an array of symbols (constant values, variables, operators)
// representing a postfix expression
// info = a hash table whose keys are operator symbols and values are their arities
// OUTPUT
// The expression tree of x
nodes <- initialize an empty stack
for i <- 1 to length(x):
if x[i] is not an operator:
nodes.push(x[i])
else:
m <- info[x[i]]
operands <- pop m items from nodes
operands <- reverse operands
new_node <- Node(operands)
new_node.operator <- x[i]
nodes.push(new_node)
root <- nodes.pop()
return root
4.2 关键点说明
- 使用哈希表
info查询每个运算符所需的参数个数； - 弹出栈中前
m个操作数作为子节点； - 因为栈是后进先出（LIFO），所以需要反转顺序；
- 构建新节点并压入栈中。
4.3 时间复杂度分析
- 设最大元数为 m；
- 每个运算符最多弹出 m 个操作数；
- 总时间复杂度为 **O(mn)**，其中 n 为表达式长度；
- 若 m 为常数，则退化为 **O(n)**，与二元运算符版本一致；
- 实际运行效率略低，因为每次弹出更多元素。
5. 总结
✅ 我们介绍了一个线性时间复杂度的算法，用于将后缀表达式转换为表达式树。
✅ 适用于二元运算符的版本简单高效，且易于实现。
✅ 扩展版支持任意元数的运算符，灵活性更强，但需额外维护元数信息。
❌ 该算法不校验输入表达式的合法性，若输入错误，构建过程会失败。
⚠️ 实际使用时应结合词法分析（Tokenization）和语法校验（Validation）模块，以确保输入格式正确。