10

The Algorithm Design Manual中有两个相关的 excises 。

基本上，我知道如何解决第一个消费税，但我不知道如何使用第一个解决方案作为提示来解决第二个消费税。

算术表达式树的消费税

算术表达式树

上面是一个算术表达式树。假设算术表达式以树的形式给出。每个叶子都是一个整数，每个内部节点都是标准算术运算之一（+，-，*，/）。例如，表达式 2 + 3 * 4 + (3 * 4)/5 由上图中的树表示。给出一个计算这样一个表达式的 O(n) 算法，其中树中有 n 个节点。

好的，这并不难。我的解决方案是这样的：

    public float evaluate() {
        return evaluate(root);
    }

    private float evaluate(Node_EX _node) {
        if (_node.left == null || _node.right == null)
            return Float.parseFloat(_node.key);
        String op = _node.key;
        if (op == "+") {
            return evaluate(_node.left) + evaluate(_node.right);
        } else if (op == "-") {
            return evaluate(_node.left) - evaluate(_node.right);
        } else if (op == "*") {
            return evaluate(_node.left) * evaluate(_node.right);
        } else {
            return evaluate(_node.left) / evaluate(_node.right);
        }
    }

我只是使用递归的方式来解决表达式树的结果。

算术表达式DAG的 Excise

算术表达式 dag

假设一个算术表达式被给出为一个 DAG（有向无环图），其中删除了公共子表达式。每个叶子都是一个整数，每个内部节点都是标准算术运算之一（+，-，*，/）。例如，表达式 2 + 3 * 4 + (3 * 4)/5 由上图中的 DAG 表示。给出一个 O(n + m) 算法来评估这样一个 DAG，其中 DAG 中有 n 个节点和 m 个边。提示：修改树案例的算法以达到所需的效率。

好的，描述中有这样一个提示：提示：针对树的情况修改一个算法，以达到预期的效率。

实际上，我对这个提示感到很困惑。对于一个典型的树相关的事情，我们通常可以使用递归来解决。但是，如果这是一个图，我的第一个直觉是使用 BFS 或 DFS 来解决它。那么我如何将 BFS 或 DFS 与树相关联，尽管 DFS 实际上是递归的？

4

2 回答 2

13

我相信，为了达到预期的效率，问题希望您避免重新评估您已经访问过的树的部分。一旦您到达并评估了 DAG 中的某个子树（树中的每个节点都代表以该节点为根的子树），您可以存储结果值并将其与该子树相关联。然后，当您再次访问它时，您可以检查您是否已经预先计算了该值并只是检索它而不是再次评估它。

有许多不同的方法可以存储和检索这些值，一种简单的方法是修改节点的结构以允许可缓存的结果。

于 2012-04-12T10:24:41.943 回答
2

可以使用给定 DAG 上的 DFS 来解决该问题。

  • 我们将保存对空气动力学表达式的公共部分的重新计算。

  • 例如：在做 DFS 时， * 会从 ( / ) 节点重新遇到。( / ) 和 * 之间的边是交叉边，这意味着 (*) 的左右子树已经被求值。因此，我们将利用这一点并节省重新计算。

  • 然而，要实现这一点，我们需要保存节点上的操作结果。

  • 复杂度为 O(n+m)，因为它是正常的 DFS 遍历，其中一些额外的内存用于存储中间结果。

希望这可以帮助。

于 2014-05-18T04:37:24.693 回答