数据结构——有向无环图描述表达式
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph），如下图所示；3.一般会给出一个算术表达式，让我们来求出所需要的最少的顶点个数，下面给出解答步骤；
·
——本节内容为Bilibili王道考研《数据结构》P65视频内容笔记。
目录
一、定义
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph），如下图所示；
二、问题描述
1.之前学习过用树的形式来表示一个表达式，比如下面这棵树：
2.不难发现上面这棵树其中有很多部分可以合并，合并完后变为：
3.一般会给出一个算术表达式，让我们来求出所需要的最少的顶点个数，下面给出解答步骤；
三、解题步骤
1.例如题目给出：
2.第一步：把各个操作数不重复地排成一排，如下图：
3.第二步：标出各个运算符的生效顺序（先后顺序有点出入无所谓），如下图：
4.第三步：按顺序加入运算符，注意“分层”，如下图：
5.第四步：从底向上逐层检查同层的运算符是否可以合体，如下图：
四、特殊例子
魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。
更多推荐
6
0- 0
已为社区贡献6条内容
所有评论(0)