[FoRK] Data Structures Question

[Nalin Savara]

>
>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