有向无环图 DAG 描述表达式与最少顶点数模型

核心心法(刻在脑子里)

  1. 叶子定操作数,内部定操作符:表达式中每个不重复的变量或常量,全局只建立 1 个叶子节点。
  2. 相同三元组绝不重复建:若当前要计算的 (运算符, 左操作数指针, 右操作数指针) 已经存在,直接复用该节点,顶点数 +0!
  3. 最少顶点数秒杀公式:
  4. 非交换律左右顺序不可颠倒:加法乘法满足交换律可同构合并;但减法、除法严格区分左右操作数(如 x - y 与 y - x 绝对不能共享同一个节点)!
  5. 考场绝密辨析:选 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

详细实操规则:

  1. Step 1(建叶子表):列出表达式中所有不重复的变量或常数,设其数量为 。
  2. Step 2(定优先级):将中缀表达式按数学运算优先级(先括号内、先乘除后加减)拆解为基础二元运算三元组序列:E1, E2, ...。
  3. Step 3(判重与复用):
    • 逐个检查当前运算三元组 (op, left, right);
    • 若左右输入来源与已有节点的左右完全一致,直接复用已有节点标号;
    • 否则分配一个新的运算符节点标号。
  4. 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 既参与了加法,又参与了除法,同样被多处共享复用。

⚠️ 五、命题人考场陷阱与变式对比

命题人设坑三绝(不可乱合并的情形)

  1. 非交换律运算符操作数颠倒绝对不能合并:
    • 加法 x + y 与 y + x 在数学上等价,但在严格的数据结构求值中,若题目强调操作数顺序,通常只有左、右孩子一致才合并;
    • 减法与除法严格区分左右顺序:(x - y) 与 (y - x)、(x / y) 与 (y / x) 是完全不同的两个运算,绝对不能共享同一个运算符节点!
  2. 千万别数括号:
    • 括号只是用来在文本中规定计算优先级的,在树和图结构中,层级关系本身就表达了优先级,任何括号都不占顶点!
  3. 区分“顶点数(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) 手动画树实操步骤:

  1. 找总根节点:整个式子最外层由两团括号相乘,最后计算的一定是中间的乘号 * 在纸上画出总根节点 *!
  2. 切分左右两翼:
    • * 的左边是 (x + y) 构成 * 的左子树;
    • * 的右边是 ((x + y) / x) 构成 * 的右子树。
  3. 递归画左子树 (x + y):
    • 剥掉括号只剩加法,+ 是左子树的根;
    • + 的左孩子画变量 x,右孩子画变量 y(左翼搞定!)。
  4. 递归画右子树 ((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) 中缀表达式:必须智能添加括号!不加括号会彻底颠覆运算顺序!

到底什么时候必须加括号?(中序遍历加括号黄金法则)

对二叉树做中序递归遍历时:

  1. 叶子节点(操作数):直接输出字符,绝不加括号。
  2. 根节点(最外层):最外层绝不需要加括号(例如不需要写成 (a+b) 的最外层包围)。
  3. 子树(分支运算符节点):
    • 比较 子节点运算符优先级 与 当前父节点运算符优先级;
    • 若子节点优先级 < 父节点优先级(例如子节点是 + 或 -,父节点是 * 或 /):
      • 为了防止先算乘除破坏先算加减的初衷,必须在递归遍历该子树前后输出 ( 和 )!
    • 若子节点优先级 父节点优先级:自然按照左结合性从左到右计算,无需加括号。

3. 考法延伸:括号匹配构建二叉树(广义表表示法 / 括号表示法)

题目常给出如 A(B(D,E),C(,F)) 这种带括号的字符串,要求画出二叉树或求树的深度/叶子节点。

栈与括号匹配解构流程(SOP):

  • 遇到 英文字母:建立新节点;若栈不为空,说明它是栈顶节点的子节点(根据当前是逗号前还是逗号后,挂为左孩子或右孩子)。
  • 遇到 左括号 (:说明前面的字母有子树,将该字母节点 入栈(Push),并标记接下来处理的是它的 左子树!
  • 遇到 逗号 ,:说明左子树已解析完毕,标记接下来处理的是栈顶节点的 右子树!
  • 遇到 右括号 ):说明当前以栈顶为根的子树构建完毕,将栈顶节点 出栈(Pop)!

📋 考场 5 秒防混对比总表

考察对象核心本质是否允许指针汇聚(入度 > 1)重复表达式处理方式同一表达式 (x+y)*((x+y)/x) 节点数
有向无环图(DAG)消除公共子表达式的图结构✅ 允许(多父共享同一个子节点)无论变量还是算式,只要重复全部合并5(2个操作数 + 3个运算符)
表达式二叉树语法分析生成的标准语法树❌ 严格禁止(入度恒 )每个出现的字符独立建点,绝不合并9(5个操作数 + 4个运算符)
括号表达式(广义表)用 ( ) 和 , 序列化表达二叉树分支❌ 严格树形仅用于树的序列化存储与栈解析建树视树的具体节点而定