|Boolean expressions represented as directed graph email@example.com (Steve Jones) (2002-05-27)|
|Re: Boolean expressions represented as directed graph firstname.lastname@example.org (VBDis) (2002-05-31)|
|Re: Boolean expressions represented as directed graph email@example.com (Kenn Heinrich) (2002-05-31)|
|Date:||31 May 2002 23:07:19 -0400|
|Organization:||AOL Bertelsmann Online GmbH & Co. KG http://www.germany.aol.com|
|Posted-Date:||31 May 2002 23:07:19 EDT|
"Steve Jones" <firstname.lastname@example.org> schreibt:
>A -+-> B -> C -+-> J
> +-> X -> Y -+
First I had some problems with the meaning of this text, without an fixed size
>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.
Return to the
Search the comp.compilers archives again.