扩展表达式树评估算法

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 应该可以正常工作。对该节点的任何后续访问都不会触发递归调用来评估子表达式，而只是 return 存储的值。该技术称为 'memoization'。运行时间基本上是图中的边数，假设所有运算符评估都是 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

扩展表达式树评估算法

Extending a expression tree evaluation algorithm

algorithm

graph

time-complexity

expression-trees