# [FoRK] Data Structures Question

Stephen D. Williams <sdw at lig.net> on Wed Apr 4 06:59:54 PDT 2007

```The original question was trying to optimize when there were _any_
number of variables.  I took any to be very large (thousands or 10's of
thousands), so O(n Log(n)) isn't very good compared to what can probably
be done.  In many cases, these kinds of problems will have mostly false
variables or rules with limited interdependency which can be optimized for.

sdw

Nalin Savara 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
>> 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 ;
>
> (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
>
> (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 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
>>
>> [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
>

```