algorithm - 评估表达式树

Question

Skiena 关于算法的书包含以下问题：

1) 在给定 n 个节点的情况下，在 O(n) 时间内评估作为二叉树给出的表达式。

2) 在 O(n+m) 时间内评估作为 DAG 给出的表达式，给定 DAG 中的 n 个节点和 m 个边。

对于第一个问题，我可以想办法：

evaluate(node) {
     if(node has children){
          left_val = evaluate(node->left);
          right_val = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          return val;
     }
     else {
          return node_value;
     }
}

由于我们访问每个节点一次，因此需要 O(n) 时间。

由于这本书没有解决方案，任何人都可以告诉这是否正确？

也有人可以为第二个问题提出解决方案。

谢谢。

Answer 1

第一种方式对我来说看起来不错。

对于 DAG，如果您可以修改树以将缓存值添加到每个节点，则可以使用相同的算法并稍作调整，以便在操作员节点具有缓存值时不递归。这应该是 O(n+m) 时间（每个节点最多一次算术运算，每个边最多一次指针查找）。明确地：

evaluate(node) {
     if (node has value) {
          return node->value;
     } else {
          left = evaluate(node->left);
          right = evaluate(node->right);

          // find operation symbol for node and use it as
          // val = left_val operation right_val

          node->value = val;
          return val;
     }
}