[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

(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

(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

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


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