6.1 节的练习

为下面的表达式构造 DAG

((x+y)-((x+y)*(x-y)))+((x+y)*(x-y))

解答

为下列表达式构造 DAG，且指出他们每个子表达式的值编码。假定 + 是左结合的。

1. a+b+(a+b)
2. a+b+a+b
3. a+a+(a+a+a+(a+a+a+a))

解答

1. a+b+(a+b)

   

   1	id	a
   2	id	b
   3	+	1	2
   4	+	3	3

2. a+b+a+b

   

   1	id	a
   2	id	b
   3	+	1	2
   4	+	3	1
   5	+	4	2

3. a+a+(a+a+a+(a+a+a+a))

   

   1	id	a
   2	+	1	1
   3	+	2	1
   4	+	3	1
   5	+	3	4
   6	+	2	5