算法 - 如何求解算术表达式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实际上是递归的？

Answer 1

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

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