algorithm - How to solve an arithmetic expression DAG?
algorithm, data-structures, directed-acyclic-graphs, graph, tree
Solution
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.
Problem
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?