algorithm - How to solve an arithmetic expression DAG?

Question

There are two related excises in The Algorithm Design Manual.

Basically, I know how to solve the first excise, but I don't know how to solve the 2nd one using the first one's solution as a hint.

Excise of an arithmetic expression tree

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.

Ok, this is not hard. My solution is like this:

    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);
        }
    }

I just use recursive way to solve the expression tree for the result.

Excise of an arithmetic expression 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.

Ok, there is such a hint in the description: Hint: modify an algorithm for the tree case to achieve the desired efficiency.

I am quite confused by this hint, actually. For a typical tree related thing, we normally can use recursive to solve. However, if this is a graph, my first intuitive is to use BFS or DFS to solve it. Then how can I relate BFS or DFS to the tree, though DFS is actually a recursive?

Answer 1

I believe, to achieve the desired efficiency, the problem wants you to avoid re-evaluating parts of the tree you've already visited. Once you've reached and evaluated some sub-tree in the DAG (every node in the tree represents the sub-tree rooted at that node), you can store the resulting value and associate it with that sub-tree. Then, when you visit it again, you can check whether you've pre-computed that value and just retrieve it rather than evaluating it again.

There are many different ways you can store and retrieve these values a simple one being to modify the structure of a node to allow for a cacheable result.

Answer 2

The problem can be solved using the DFS on given DAG.

• We will save re-calculations on the common portions of the airthmetic expression.

• For example: While doing DFS when * will be re-encountered from the ( / ) node. The edge between ( / ) and * is a cross-edge, which means that the left and right subtrees of (*) are already evaluated. Thus we will take advantage of this and will save on re-calculation.

• However to achieve this we need to save the results of the operation on the nodes.

• The complexity is O(n+m) since it is normal DFS traversal with some extra memory used for storing the intermediate results.

Hope this helps.