前言

本文介绍了有向无环图（DAG）在描述算术表达式中的应用。DAG通过消除表达式树中的重复子表达式来优化存储空间，相比树结构更节省空间。文章详细讲解了如何将树结构转换为DAG，包括识别公共子表达式、合并相同操作数节点等步骤。通过2019年统考真题示例，展示了构建DAG的具体方法和规律：操作数不重复排列、按运算符生效顺序分层添加节点、合并同一层可合并运算符等。最后指出DAG描述表达式的结果不唯一，取决于运算符生效顺序。DAG在优化表达式存储空间方面具有重要应用价值。

一.有向无环图

1.定义

• 有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph）
  

二.DAG描述表达式

1.用树描述表达式转化为用DAG描述表达式

• 我们的算术表达式其实可以用树来表示
  
• 细心观察会发现上面用树描述表达式当中存在一些重复的部分,就是绿色和红色的部分,它们这两个子树的计算结果其实是一样的,所以其实我们可以干掉其中的一个子树值
  
• 那对于根节点的乘号来说,他以前的右操作数是c加d乘以e得到的结果,而对于其左子树的加号来说,他以前的右操作数也是c加d乘以e得到的结果
• 所以我们可以把这两个运算符的指针都同时指向其右子树
  
• 那这么做的好处显而易见,我们可以丢弃根节点的右子树,减少了空间开销
• 而现在产生的这个结构,它其实就是一个有向无环图
• 接下来,再观察图结构,发现还可以进行缩减
  

2.真题举例

• 29. 【2019 统考真题】用有向无环图描述表达式$(x+y)((x+y)/x)$，需要的顶点个数至少是（ ).
      A. 5 B. 6 C. 8 D. 9

1.解题过程

1. 画出树结构
   
2. 看一下这个表达式当中x+y是一个公共部分,所以我们可以把它俩合并
   
3. 同为x的这两个节点其实也可以把它只保留一份
   

2.规律

1.观察得出一般规律

• 最终的有向无环图里,顶点中不可能出现重复的操作数

2.总结解题规律

• 例子:$((a+b)\ast (b\ast (c+d))+(c+d)\ast e)\ast ((c+d)\ast e)$

1. 把各个操作数不重复地排成一排
   
2. 标出各个运算符的生效顺序（先后顺序有点出入无所谓）,当然这些运算符的生效顺序就是前后有点出入是无所谓的,为的是构建有向无环图不遗漏任何一个运算符
   
3. 根据标出的这些运算符的生效顺序来依次地把这些运算符对应的节点加到这个图里,注意"分层"
   1. 那第一个需要生效的运算符是这个加号,它的左边是a,右边是b,所以这个运算符对应的节点应该是这样子
      
   2. 第二个生效的是加号,左边是c,右边是d
      
   3. 第三个生效的是这个乘号,左边是b,右边是(c+d),也就是上一步加号的运算结果,那这个地方需要注意要把这个运算符放到上一层,也就是所谓的"分层"¹
      
   4. 第四个生效的运算符应该是乘号,那这个乘号是利用了,第一步的加号的结果,然后它的右操作数又利用了第三步的乘号,需要把这两个部分的结果进行相乘,这里需要分层
      
   5. 第五个生效的是加法,左边是c,右边是d
      
   6. 第六个生效的是乘法,左边是第五步的加号得到的结果,右边是e这个操作数,由于它需要利用到这个加法的运算结果,因此要对它分层
      
   7. 后面的不再赘述,结果如图
      
4. 那现在我们就初步构建完了一个有向无环图,接下来我们来观察哪些东西需要合并,具体的做法是我们需要自底向上的来合并处于同一层的这些运算符
   1. 那由于我们刚开始对于各个操作数,我们都只保留了一个顶点,所以这些操作数顶点一定是不需要合并的,所以我们只需要检查这些操作符
   2. 最下面这一层全部是加法,最左边这个加法左右是ab,后面这三个加法的左右操作数都是cd,所以其实我们可以把左右操作数相同的三个加法运算符进行一个合体的操作
      
   3. 那现在第一层剩下的这两个运算符肯定是没办法合并的,那我们再看第二层,第二层的第一个乘号,左边是b,右边是(c+d),而第二个乘号左边是(c+d),右边是e,第三个乘号左边是(c+d),右边是e,所以第二个和第三个乘号显然是可以合二为一的
      
   4. 那第二层的合并就结束了,那再往上的三层,由于每一层只有一个运算符,所以肯定不需要进行合体的操作
5. 所以最终结果为
   

3.原理

• 为什么只需要检查处于同一层的这些运算符?
  答:最底层的运算符,它的左右操作数是直接对某一个具体的数来进行的,而上面这一层的运算,它的左边或者右边的某一个操作数肯定是一个复合的操作数,所以上面这一层出现的这个运算符和底下这一层的运算符,肯定是不可能合并的,所以我们只需要一层一层的往上检查就可以了

三.运算符生效次序不同的区别

• $(a\ast b)\ast (a\ast b)\ast (a\ast b)\ast c$
  • 运算符生效次序
    
  • 结果
    
  • 运算符生效次序
    
  • 结果
    
• 结论:用DAG描述表达式的有向无环图不唯一

四.知识点回顾与重要考点

结语

一更😉,昨天有事耽搁了,写出来了没发,今天发也一样的😉

如果想查看更多章节,请点击:一、数据结构专栏导航页

---

1. 当前乘法得利用下一层的加法的运算结果才可以进行运算 ↩︎