有向无环图 DAG 描述表达式与最少顶点数模型
核心心法(刻在脑子里)
- 叶子定操作数,内部定操作符:表达式中每个不重复的变量或常量,全局只建立 1 个叶子节点。
- 相同三元组绝不重复建:若当前要计算的
(运算符, 左操作数指针, 右操作数指针)已经存在,直接复用该节点,顶点数 +0!- 最少顶点数秒杀公式:
- 非交换律左右顺序不可颠倒:加法乘法满足交换律可同构合并;但减法、除法严格区分左右操作数(如
x - y与y - x绝对不能共享同一个节点)!- 考场绝密辨析:选 5 还是选 9? 同一个表达式
(x+y)*((x+y)/x):若问 DAG 最少顶点数选 5(公共子表达式消除合并);若问 二叉树(表达式树) 顶点数直接选 9(每个操作数和运算符物理占位各算一个节点,绝不合并)!
🧭 一、题型认知与底层逻辑(二叉树 vs DAG)
在编译器语法分析和 408 数据结构中,表达式通常可以用二叉语法树或**有向无环图(DAG)**表示:
| 表示形式 | 底层结构特征 | 重复子表达式处理 | 空间效率 |
|---|---|---|---|
| 二叉语法树(Tree) | 严格树形结构,每个节点入度至多为 1 | 即使完全相同,也必须重复建立完整子树 | 占用空间多,存在大量冗余节点 |
| 有向无环图(DAG) | 有向无环图,共享公共子表达式,允许入度 > 1 | 多父共享:多个上层运算符指向同一个子节点 | 极度精简,顶点数达到理论极限最少 |
核心思想:公共子表达式消除(Common Subexpression Elimination)
DAG 描述表达式的本质就是**“找相同、并节点、拉指针”**。凡是已经算出来的中间结果,后续运算直接牵一根箭头指过去复用,绝不重复生成新节点。
🛠️ 二、解题标准化流程(SOP:四步消重法)
在考场草稿纸上求解最少顶点数时,切勿盲目凭直觉画图,严格遵循以下机械化 4 步走:
flowchart TD A["Step 1: 扫描所有操作数<br/>(变量/常量去重,确定叶子节点数)"] --> B["Step 2: 划分运算优先级<br/>(由内层括号到外层,列出运算操作序列)"] B --> C["Step 3: 自底向上逐个建符<br/>(查验 (op, left, right) 是否已存在)"] C --> D{"三元组是否已存在?"} D -- "已存在" --> E["直接复用原节点指针<br/>(顶点数 +0)"] D -- "不存在" --> F["新建运算符节点<br/>(顶点数 +1)"] E --> G["Step 4: 统计求和得出最终顶点数"] F --> G
详细实操规则:
- Step 1(建叶子表):列出表达式中所有不重复的变量或常数,设其数量为 。
- Step 2(定优先级):将中缀表达式按数学运算优先级(先括号内、先乘除后加减)拆解为基础二元运算三元组序列:
E1, E2, ...。 - Step 3(判重与复用):
- 逐个检查当前运算三元组
(op, left, right); - 若左右输入来源与已有节点的左右完全一致,直接复用已有节点标号;
- 否则分配一个新的运算符节点标号。
- 逐个检查当前运算三元组
- Step 4(汇总算总数):统计所有独立的操作数节点数和新建的运算符节点数,相加即为所求。
🎯 三、实战精讲:2019 年 408 统考第 6 题
【2019 年 408 统考真题 第 6 题】
用有向无环图描述表达式(x+y)*((x+y)/x),需要的顶点个数至少是( )。
A. 5 B. 6 C. 8 D. 9
完整四步推导过程:
1. 扫描操作数(叶子节点):
表达式中仅出现变量 x 和 y。
建立 2 个操作数叶子顶点:
- 节点 ①:
x - 节点 ②:
y
2. 自底向上拆解与查重(运算符节点):
- 第 1 步:计算第一个括号内的加法
(x + y)- 运算符:
+,左操作数为节点 ①(x),右操作数为节点 ②(y)。 - 之前未建过此运算 新建 节点 ③:
+(代表 )。
- 运算符:
- 第 2 步:计算第二个括号内的加法
(x + y)- 运算符:
+,左操作数也是节点 ①(x),右操作数也是节点 ②(y)。 - 与节点 ③ 完全相同 直接复用节点 ③,不增加新顶点!
- 运算符:
- 第 3 步:计算除法
((x+y)/x)- 运算符:
/,左操作数是(x+y)(即节点 ③),右操作数是x(即节点 ①)。 - 组合
(/, 节点 ③, 节点 ①)之前未建过 新建 节点 ④:/(代表 )。
- 运算符:
- 第 4 步:计算最外层乘法
*- 运算符:
*,左操作数是第一个(x+y)(即节点 ③),右操作数是((x+y)/x)(即节点 ④)。 - 组合
(*, 节点 ③, 节点 ④)之前未建过 新建 节点 ⑤:*(代表最终根表达式)。
- 运算符:
3. 统计节点总数:
- 叶子操作数顶点(2 个):
x,y - 运算符内部顶点(3 个):
+,/,* - 顶点总数: 个。
📊 四、该表达式的 DAG 拓扑图示
graph BT X["x (节点 ①)"] Y["y (节点 ②)"] PLUS["+ (节点 ③)"] DIV["/ (节点 ④)"] MUL["* (节点 ⑤)"] X --> PLUS Y --> PLUS PLUS --> DIV X --> DIV PLUS --> MUL DIV --> MUL
拓扑图解析
仔细观察上面的 DAG:
- 节点
+ (节点 ③)的出度为 2(它同时被节点*和节点/引用指向),这正是 DAG 区别于普通二叉树的根本特征(在普通二叉树中,x+y必须画两份,总节点数将膨胀至 个)!- 变量
x既参与了加法,又参与了除法,同样被多处共享复用。
⚠️ 五、命题人考场陷阱与变式对比
命题人设坑三绝(不可乱合并的情形)
- 非交换律运算符操作数颠倒绝对不能合并:
- 加法
x + y与y + x在数学上等价,但在严格的数据结构求值中,若题目强调操作数顺序,通常只有左、右孩子一致才合并;- 减法与除法严格区分左右顺序:
(x - y)与(y - x)、(x / y)与(y / x)是完全不同的两个运算,绝对不能共享同一个运算符节点!- 千万别数括号:
- 括号只是用来在文本中规定计算优先级的,在树和图结构中,层级关系本身就表达了优先级,任何括号都不占顶点!
- 区分“顶点数(Vertices)”与“边数(Edges)”:
- 408 有时会反向提问“该 DAG 的有向边数至少是多少?”
- 每个二元运算符节点都正好有 2 条入边(指向它的两个操作数)。
- 本题中共有 3 个运算符节点(
+,/,*),因此有向边数恒为 条边!
经典历年真题变式对比表:
| 题目来源 | 待表示表达式 | 唯一操作数 | 不可合并运算符 | 最少顶点数 |
|---|---|---|---|---|
| 2019 年 408 第 6 题 | (x+y)*((x+y)/x) | x, y(2 个) | +, /, *(3 个) | 5 |
| 2014 年 408 真题变式 | ((a+b)*b+c)/(a+b) | a, b, c(3 个) | +, *, +, /(其中 a+b 复用,剩 4 个) | 7 |
| 减法不可逆变式 | (x-y)*(y-x) | x, y(2 个) | - (x,y), - (y,x), *(3 个不可合并) | 5 |
🥊 六、孪生兄弟大对决:表达式二叉树(含括号还原)vs 有向无环图 DAG
考生在考场上极易将 “DAG 描述表达式” 与 “表达式二叉树(二叉语法树)”、以及 “括号匹配还原表达式” 混淆。学长带你把这三个亲兄弟的底裤一次性扒干净!
1. 结构与顶点数决战:为什么 2019 真题的 D 选项恰好是 9?
面对同一个表达式:(x+y)*((x+y)/x)
✍️ 考场手画表达式二叉树秒杀 SOP(自顶向下剥洋葱法)
很多同学考场上一拿到长表达式就发懵不知道先画谁。记住高分学长的八字口诀:==“最后算的做根,递归切分左右”==!
flowchart TD Step1["Step 1: 扫描表达式,找出【最后计算】的操作符<br/>(作为当前二叉树/子树的根节点)"] --> Step2["Step 2: 沿该运算符将表达式切为左、右两半<br/>(左半部分成为左子树,右半部分成为右子树)"] Step2 --> Step3["Step 3: 脱掉各子表达式的最外层括号,递归执行 Step 1<br/>(直到只剩下孤立的变量/常量作为叶子节点)"]
针对本题 (x+y)*((x+y)/x) 手动画树实操步骤:
- 找总根节点:整个式子最外层由两团括号相乘,最后计算的一定是中间的乘号
*在纸上画出总根节点*! - 切分左右两翼:
*的左边是(x + y)构成*的左子树;*的右边是((x + y) / x)构成*的右子树。
- 递归画左子树
(x + y):- 剥掉括号只剩加法,
+是左子树的根; +的左孩子画变量x,右孩子画变量y(左翼搞定!)。
- 剥掉括号只剩加法,
- 递归画右子树
((x + y) / x):- 剥掉最外层括号变成
(x + y) / x; - 括号里的加法先算,除号
/是这一整坨里最后计算的符号/成为右子树的根节点; /的左边是(x + y),右边是x;/的右孩子直接连变量x;/的左孩子递归画加法节点+,该+下面分别连出x和y(右翼搞定!)。
- 剥掉最外层括号变成
一棵标准的、包含 9 个顶点的表达式二叉树就在 10 秒内跃然纸上!
graph TD subgraph Tree ["普通表达式二叉树 (入度必须 <= 1,严禁共享,共 9 个顶点)"] T_MUL["*"] T_P1["+"] T_X1["x"] T_Y1["y"] T_DIV["/"] T_P2["+"] T_X2["x"] T_Y2["y"] T_X3["x"] T_MUL --> T_P1 T_P1 --> T_X1 T_P1 --> T_Y1 T_MUL --> T_DIV T_DIV --> T_P2 T_P2 --> T_X2 T_P2 --> T_Y2 T_DIV --> T_X3 end subgraph DAG ["有向无环图 DAG (入度可 > 1,共享公共子式,仅 5 个顶点)"] D_MUL["* (节点 ⑤)"] D_DIV["/ (节点 ④)"] D_PLUS["+ (节点 ③)"] D_X["x (节点 ①)"] D_Y["y (节点 ②)"] D_MUL --> D_PLUS D_MUL --> D_DIV D_DIV --> D_PLUS D_DIV --> D_X D_PLUS --> D_X D_PLUS --> D_Y end
揭秘 2019 年真题 D 选项的恶毒陷阱
- 如果题目要求画的是 “表达式二叉树”:
- 树中每个节点的入度至多为 1,绝对不允许合并任何节点!
- 叶子节点数 = 操作数物理出现的次数 = 5 次(
x出现 3 次,y出现 2 次);- 内部运算符数 = 运算符总个数 = 4 个(
+,+,/,*);- 二叉树总节点数 = ==9 个==!
- 命题人把 9 放在 D 选项,就是专门用来坑那些“把 DAG 当成普通二叉树来数”的考生的!
- 审题看到 “有向无环图(DAG)” 必须合并公共子式,秒选 5(A);
- 审题看到 “二叉树 / 二叉语法树” 严格树形不能合并,秒选 9(D)!
2. 考法延伸:表达式二叉树的中序遍历与“括号匹配加括号规则”(2017 年 408 第 41 题大题核心)
很多题目会反过来考:“给你一棵表达式二叉树,让你写出带括号的中缀表达式”。
表达式二叉树三种遍历的秘密
- 前序遍历(Pre-order) 前缀表达式(波兰式):天然不需要任何括号!
- 后序遍历(Post-order) 后缀表达式(逆波兰式):天然不需要任何括号!
- 中序遍历(In-order) 中缀表达式:必须智能添加括号!不加括号会彻底颠覆运算顺序!
到底什么时候必须加括号?(中序遍历加括号黄金法则)
对二叉树做中序递归遍历时:
- 叶子节点(操作数):直接输出字符,绝不加括号。
- 根节点(最外层):最外层绝不需要加括号(例如不需要写成
(a+b)的最外层包围)。 - 子树(分支运算符节点):
- 比较 子节点运算符优先级 与 当前父节点运算符优先级;
- 若子节点优先级 < 父节点优先级(例如子节点是
+或-,父节点是*或/):- 为了防止先算乘除破坏先算加减的初衷,必须在递归遍历该子树前后输出
(和)!
- 为了防止先算乘除破坏先算加减的初衷,必须在递归遍历该子树前后输出
- 若子节点优先级 父节点优先级:自然按照左结合性从左到右计算,无需加括号。
3. 考法延伸:括号匹配构建二叉树(广义表表示法 / 括号表示法)
题目常给出如 A(B(D,E),C(,F)) 这种带括号的字符串,要求画出二叉树或求树的深度/叶子节点。
栈与括号匹配解构流程(SOP):
- 遇到 英文字母:建立新节点;若栈不为空,说明它是栈顶节点的子节点(根据当前是逗号前还是逗号后,挂为左孩子或右孩子)。
- 遇到 左括号
(:说明前面的字母有子树,将该字母节点 入栈(Push),并标记接下来处理的是它的 左子树! - 遇到 逗号
,:说明左子树已解析完毕,标记接下来处理的是栈顶节点的 右子树! - 遇到 右括号
):说明当前以栈顶为根的子树构建完毕,将栈顶节点 出栈(Pop)!
📋 考场 5 秒防混对比总表
| 考察对象 | 核心本质 | 是否允许指针汇聚(入度 > 1) | 重复表达式处理方式 | 同一表达式 (x+y)*((x+y)/x) 节点数 |
|---|---|---|---|---|
| 有向无环图(DAG) | 消除公共子表达式的图结构 | ✅ 允许(多父共享同一个子节点) | 无论变量还是算式,只要重复全部合并 | 5(2个操作数 + 3个运算符) |
| 表达式二叉树 | 语法分析生成的标准语法树 | ❌ 严格禁止(入度恒 ) | 每个出现的字符独立建点,绝不合并 | 9(5个操作数 + 4个运算符) |
| 括号表达式(广义表) | 用 ( ) 和 , 序列化表达二叉树分支 | ❌ 严格树形 | 仅用于树的序列化存储与栈解析建树 | 视树的具体节点而定 |