algorithm - 如何求解算术表达式 DAG？

Question

Algorithm Design Manual中有两个相关的消费税.

基本上，我知道如何解决第一个问题，但我不知道如何解决第二个问题使用第一个问题的解决方案作为提示。

运算表达式树

Above is an arithmetic expression tree. Suppose an arithmetic expression is given as a tree. Each leaf is an integer and each internal node is one of the standard arithmetical operations (+,−,∗,/). For example, the expression 2 + 3 ∗ 4 + (3 ∗ 4)/5 is represented by the tree in above Figure. Give an O(n) algorithm for evaluating such an expression, where there are n nodes in the tree.

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

    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

Suppose an arithmetic expression is given as a DAG (directed acyclic graph) with common subexpressions removed. Each leaf is an integer and each internal node is one of the standard arithmetical operations (+,−,∗,/). For example, the expression 2 + 3 ∗ 4 + (3 ∗ 4)/5 is represented by the DAG in above Figure. Give an O(n + m) algorithm for evaluating such a DAG, where there are n nodes and m edges in the DAG. Hint: modify an algorithm for the tree case to achieve the desired efficiency.

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

实际上，我对这个提示很困惑。对于一个典型的树相关的东西，我们一般可以用递归来解决。但是，如果这是一个图，我的第一个直觉是用BFS或者DFS来求解。那么我如何将 BFS 或 DFS 与树相关联，尽管 DFS 实际上是递归的？

Answer 1

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

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