[FoRK] Data Structures Question
Nalin Savara
<nsavara at vsnl.net> on
Wed Apr 4 01:48:57 PDT 2007
>
>No, that doesn't do the job. I'm not looking to rewrite a boolean
>calculator. I'm looking for a structure, such as a tree, that has inherent
>properties that provide loading of an expression with and's and or's, but
>enables to you go to a specific node, or use an algorithmic method of
>navigation through the nodes, so that getting the subexpressions costs, at
>the worst case, n * log(n)
>
Reza; Andy; Joe ;
To add to Joe Barrera's very commendable and applicable answer:--
(and I say this as someone who was once co-author of a algorithm design book
that had a whole chapter on this):-- (Joe, Andy et al, feel free to comment)
you can do the following:-- (the below are the exact steps--- hopefully
this'll help you get it to code and skip the complicated proofs in Dragon
book):--
(1) First input the boolean expression in infix notation
(2) Convert above boolean expression to postfix notation-- use the
stack-based infix to postfix conversion algo found in any elementary
data-structures book.
Note: this algo is very efficient; because it involves peeking at the
stack-top-- which is the equivalent of LALR(1) parsing-- because peeking at
stack top is peeking ahead one symbol ahead.
(3) Take the postfix expression and generate a tree out of it--> involves
walking through the expression pushing nodes with each node having a single
operand from the expression onto the stack until you 'see' a operator--> and
at that point, you pop two nodes with operands, and replace those with a
parent node with one operator and two terminal nodes which contain the
operands (or a single child node with a single operand incase of a unary
operator).
(4) When there are no more operators or operands left in the expression; at
that point the stack will automatically contain just one pushed node--> and
that will be the root node of the expression tree representing the
expression.
The order of the above expression tree generation will be O(n Log(n) ) -->
and assuming that nodes have pointers to parent nodes; and also references
to symbols in original expression, you can go from any node to any other
node as desired by you.
If you want I can dig around for my old code-- see if i can find
somethingthat does almost exactly what you want.
Hope that helps...
Nalin
----- Original Message -----
From: "Andy Armstrong" <andy at hexten.net>
To: <reza at voicegenesis.com>; "Friends of Rohit Khare" <fork at xent.com>
Sent: Tuesday, April 03, 2007 4:20 PM
Subject: Re: [FoRK] Data Structures Question
> On 3 Apr 2007, at 05:33, Reza B'Far wrote:
> > However, I purposefully am trying not to treat it as a "logic"
> > question. I
> > want to load n expressions into a structure, such as a tree, that
> > has the
> > properties that support the decomposition that I want.
> > Essentially, what I
> > want is to explode the boolean (Andy refers to this) but with some
> > added
> > constraints... Get all the "anded" terms together in one single
> > expression.
> > So, the subexpressions should only have AND's.
>
> That /is/ a sum of products then... If you rewrite your original
> expression in SoP form you get
>
> (e1 && e2 && e5) || (e3 && e5) || (e4 && e5)
>
> which is just your three AND terms ORed together.
>
> > So, to summarize, I'm trying to find a structure that has this
> > inherently
> > built in... which by several degrees of indirection means
> > significantly
> > improved performance if you have n expressions and need to find the
> > subexpressions and the path that was necessary to navigate to each
> > randomly... basically, looking for the canonical solution... don't
> > know if
> > one exists or not.
>
> I'm obviously having YASD[1] but I'm still not really clear what you
> mean. For your example does the tree look like this?
>
> ( or )
> / | \
> / | \
> / (and) \
> / / \ \
> (and) e3 e5 (and)
> / | \ / \
> e1 e2 e5 e4 e5
>
> It might be worth looking at this:
>
> http://www.dei.isep.ipp.pt/~acc/bfunc/
>
> Unfortunately it's binary-only but, if nothing else, some of the
> links might be useful. I recently used it in conjunction with a
> little Perl wrapper to semi-automatically refactor a bunch of complex
> business rules.
>
> [1] Yet Another Stupid Day
>
> --
> Andy Armstrong, hexten.net
>
> _______________________________________________
> FoRK mailing list
> http://xent.com/mailman/listinfo/fork
More information about the FoRK
mailing list