# [FoRK] Data Structures Question

Albert S. <albert.scherbinsky at rogers.com> on Wed Apr 4 06:38:30 PDT 2007

```I think Nalin might be better at guessing what the
question is when the asker isn't quite sure
themselves.
Although, I'll leave that to the asker to decide.

It's swell that you can come on this list, ask a
question and get code that does it for you. Mighty
neighbourly.

Albert

--- Nalin Savara <nsavara at vsnl.net> wrote:

> >
> >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
> 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
> (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
> 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
>
> (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
> > > 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
> > 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
> >
> > [1] Yet Another Stupid Day
> >
> > --
> > Andy Armstrong, hexten.net
> >
> > _______________________________________________
> > FoRK mailing list
> > http://xent.com/mailman/listinfo/fork
>
> _______________________________________________
> FoRK mailing list
> http://xent.com/mailman/listinfo/fork
>

```