Re: Boolean expressions represented as directed graph

"Steve Jones" <steve@istech.demon.co.uk> schreibt:


>A -+-> B -> C -+-> J
> +-> X -> Y -+


First I had some problems with the meaning of this text, without an fixed size
font ;-)


>I'm looking for some insight on the approach I might take in traversing the
>graph to convert it to the text form.


I'd use an array with the number of not yet seen in-edges for every node. Then
walk the tree and create AND expressions for all sequences, and OR expressions
from all forks. Walking stops on a follow node with yet unseen in-edges, backs
up to the last fork, and processes the next edge. Processing continues only
when all in-edges to the next node already have been seen. Parentheses should
be inserted around every OR subexpression, starting at a fork.


In your example first "A && ( B && C" is created. Then the follow node has
another yet unseen in-edge, which results in a backup to A. Then walking the
next branch results in " || X && Y", and continues with ")", since now all
in-edges of J have been seen, and with the final assignment. I'd remove the
assignment from the graph before, and replace it by an synthetic end node,
because it's a different (non boolean) operation.


DoDi

Return to the comp.compilers page.
Search the comp.compilers archives again.