扩展表达式树评估算法

Question

这是我想出的一种递归算法。我在书中看到了与此类似的算法示例。

f(n)
  if n is an integer
    return n
  else
    l = left child of n
    r = right child of n
    return f(l) n f(r)

它可用于评估表达树，如Θ（n）时间中上图左侧所示。只要这一切都是正确的，我想将其扩展为评估表达式树，如右侧的树，其中重复删除了常见的子表达式。我认为该算法可以正确评估这些类型的树，但是我不确定它会花费多少时间。也许应该使用某种存储子树的方法？如：

f(n, A)
  if n is an integer
    return node
  else
    if n has more than 1 parent AND n is in A (A is a list of stored subtrees)
       return n from A
    else
      l = left child of n
      r = right child of n
      s = f(l, A) n f(r, A)
      add s to list A
      return s

此扩展名正确吗？好像真的很乱我也有一种感觉，它将在O（n ²）时间内运行，因为该函数将在n个节点上调用，并且在每次调用期间，它都必须遍历上限为n的存储节点列表。能比二次时间更好吗？

Answer 1

如果在第一次访问时将子图评估的结果存储在运算符节点上，则处理DAG应该可以正常工作。对该节点的任何后续访问都不会触发递归调用来评估该子表达式，而只是返回存储的值。该技术称为“记忆化”。假设所有操作员评估为O(1)，则运行时间基本上是图形中的边数。

伪代码：

f(n)
  if n is an integer
    return n
  else
    if property evalResult of n is defined
       return property evalResult of n
    else
      l = left successor of n
      r = right successor of n
      s = f(l) n f(r)
      set property evalResult of n to s
      return s