算法 - 如何解决算术表达式DAG？

Question

在 算法设计手册 中有两个相关的练习。

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

算术表达式 树 练习

上面是一个算术表达式树。假设给出一个算术表达式树，每个叶子节点都是整数，每个内部节点都是标准的算术运算符（+、-、*、/）。例如，表达式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的练习

假设一个算术表达式被给定为一个DAG（有向无环图），其中移除了公共子表达式。每个叶子是一个整数，每个内部节点都是标准算术运算之一（+，-，*，/）。例如，表达式2 + 3 * 4 +（3 * 4）/ 5用上面的图中的DAG表示。给出一个O（n + m）算法来评估这样的DAG，其中DAG中有n个节点和m条边。提示：修改树情况下的算法以实现所需的效率。 好的，在描述中有这样一个提示：提示：修改树情况下的算法以实现所需的效率。 实际上，我对这个提示感到很困惑。对于典型的树相关问题，我们通常可以使用递归来解决。但是，如果这是一个图，我的第一个直觉是使用BFS或DFS来解决它。那么如何将BFS或DFS与树相关联，尽管DFS实际上是递归的？

- Jackson Tale

Answer 1

我认为，为了达到理想的效率，问题要求你避免重新评估已经访问过的树部分。一旦在有向无环图（DAG）中到达并评估了某个子树（树上的每个节点表示以该节点为根的子树），您可以存储结果值并与该子树关联。然后，当您再次访问它时，您可以检查是否预先计算了该值，而只需检索它而不是再次评估。

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

- Felix Fung

---

你认为我对这道树的问题的解决方案是线性的吗？ - Jackson Tale

是的，对于树来说，您的解决方案是线性的，因为没有节点会被访问超过一次。但对于DAG而言，在最坏情况下它只是一个DFS，并且可能变得指数级。想象一棵非常高的表达树。DFS将遍历许多不同的路径才能到达叶子节点。 - Felix Fung

DFS每次只访问每个叶子一次；它不需要指数时间。 - JeffE

@JeffE，我的措辞不太好。我的意思只是说，问题中提出的递归算法在DAG的情况下需要指数时间。 - Felix Fung

我相信这个答案，通过树的后序评估，将会导致深度优先搜索（DFS）。 - Josiah Yoder

Answer 2

问题可以通过在给定DAG上使用DFS来解决。

我们将节省在算术表达式的公共部分上重新计算的时间。

例如：在进行DFS时，当从（/）节点重新遇到*时。 （/）和*之间的边是交叉边，这意味着*的左右子树已经被评估过了。因此，我们将利用这一点并节省重新计算的时间。

但是，为了实现这一点，我们需要保存节点上操作的结果。

复杂度为O（n+m），因为它是正常的DFS遍历，只是使用一些额外的内存来存储中间结果。

希望这可以帮助您。

- Sumit Trehan