6.4.3 DAG 描述表达式

表达式树会重复存储公共子表达式；DAG允许多个父结点共享同一计算结点，从而避免重复。边方向通常从运算结点指向操作数，或按依赖方向相反表示，必须统一。

手工状态

表达式 (a+b)*(a+b) 中，只建一个加法结点 P，P的孩子a,b；乘法根的两个输入都指向P。树需两个加法子树，DAG共享后只计算一次。

结构与代码

可用哈希键 (op,leftId,rightId) 做结构化去重；对交换运算还可规范化孩子顺序。拓扑序保证依赖先计算，再计算使用者。

正确性依据

相同结构且输入相同的纯表达式可共享；若结点含副作用或可变状态，盲目共享可能改变语义。

错解反馈

只因运算符相同就合并；忽略左右操作数；在有副作用表达式中做公共子表达式消除。

迁移训练

为 (a*b)+(a*b)+c 画DAG，答案只保留一个乘法结点，并被两个位置引用。