Welcome to Rooeye's blog

有向无环图表示算术表达式

数据结构 rooeye 1314℃ 0评论
今天一个童鞋问了俺一个问题,俺沉思良久,嗯,做个博客记录一下。
题目描述:
用有向无环图描述表达式(A+B)*((A+B)/A),至少需要顶点的数目为几个?
分析:
1.  先画出算术表达式 (A+B)*((A+B)/A)的二叉树表示
 
2. (A+B)*((A+B)/A) 有重复的子表达式 (A+B),二叉树中可实现对子表达式的共享
所以:
相同的叶子节点可以共用:
所以至少需要五个顶点: *,+, /, A,B 各一个。

 

转载请注明: Jinkun 的博客 » 有向无环图表示算术表达式

喜欢 (1)
发表我的评论
取消评论

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址