如何判断一个算术表达式是否为另一个算术表达式的子表达式？

核心思路 #

要解决这个问题，核心是先将表达式转换为规范化的抽象语法树（AST），再基于AST做匹配——原始字符串匹配会被表达式的等价形式（如a+b和b+a）干扰，而AST规范化后能消除这类形式差异。

具体实现步骤 #

1. 表达式解析与AST构建 #

用递归下降解析器将待判断的两个表达式（记为目标表达式E、子表达式候选S）转换为AST。AST会自动处理运算优先级和括号，比如a(a+c)会被解析为*节点，子节点是a和+节点（后者子节点为a、c）。

2. AST规范化处理 #

为了匹配等价表达式，需对AST做规范化，消除形式差异：

• 交换律统一：对加法、乘法这类交换性运算符，将子节点按固定规则排序（如变量名字典序、常量值升序）。比如b+a的AST子节点会被排序为a在前、b在后，与a+b的AST结构完全一致。
• 代数化简：合并可化简项，比如3*a + a化简为4*a；a*a统一表示为固定结构（如保留乘法形式或转为pow(a,2)）。
• 冗余结构去除：AST本身已隐含运算优先级，无需保留括号节点，直接按优先级构建树结构。

3. 子树匹配算法 #

规范化完成后，可通过以下两种方式判断S的AST是否是E的AST的子结构：

• 朴素递归匹配：遍历E的AST每个节点，与S的AST根节点对比，若匹配则递归检查所有子节点。实现简单，但时间复杂度为O(n*m)（n、m分别为两个AST的节点数）。
• 树哈希优化匹配：预处理时为每个AST节点计算哈希值，哈希值包含节点类型、运算符、规范化后的子节点哈希。之后只需在E的所有节点哈希中查找S根节点的哈希值，再对候选节点做精确匹配。预处理时间O(n+m)，查询时间O(n)，效率更高。

4. 实例化等价的子表达式匹配 #

如果需要支持用户示例中a*a+b匹配a(a+c)+b这类场景（即通过变量实例化使S成为E的一部分），需用树形模式匹配：

• 将S的AST作为模式树，允许部分节点作为可匹配的“占位符”（比如a*a中的第二个a可匹配a+c）。
• 递归遍历E的AST，尝试将模式树节点与E的节点绑定，检查是否存在一组绑定让模式树完全匹配E的某个子树。这种方法复杂度更高，但能覆盖语义等价的子表达式场景。

特殊情况处理 #

• 非交换运算符：减法、除法不满足交换律，必须严格匹配节点顺序，比如a-b和b-a的AST结构完全不同，不会被判定为等价。
• 隐式乘法：解析阶段需处理a(a+c)这类语法，将其转为显式的*节点，确保AST结构正确。

内容的提问来源于stack exchange，提问作者aboilque