Representing Logical Combinations in Analysis Programs

[DEvens]

TL;DR

How to internally represent string of and's and or's

I have an analysis program. (It's MCNP if it makes any difference.) Part of the input is to specify the surfaces of a cell in a string of "this side of surface x" and "that side of surface y" entries. It looks a little something like this.

((a b):(c -d)):(f -g))

So the : means "or" and otherwise it's "and". So this example is

{(outside a and outside b ) or (outside c and inside d) } or (outside f and inside g)

So my question is, is there a standard way of internally representing such strings of combinations of and's and or's? I'm thinking possibly some kind of tree structure? This seems like it should be one of those "standard questions" that gets asked all the time.

 

[pbuk]

For string representation I'd use somethijg like + for or, * for and and ~ for not.

But internally as you suggest some kind of node structure that suits the language you are using would be best - four kinds of node (value, and, or and not) with pointers to child nodes.

 

[DEvens]

Got it!

https://en.wikipedia.org/wiki/And–or_tree

 

[BvU]

So this example is
{(outside a and outside b ) or (outside c and inside d) }

I would read (outside c or inside d)

 

[pbuk]

Got it!

https://en.wikipedia.org/wiki/And–or_tree

Well that's a slightly different arrangement to the one I outlined (and you hinted at); the nodes on the wiki page have an arbitrary number of children whereas 'my' nodes have at most two children. Depending on the particular circumstances (language, data, algorithm), one of these may be more efficient and/or easier to implement than the other. In particular dealing with an arbitrary number of things in a low-level language is more complicated than dealing with at most two.

I would read (outside c or inside d)

Yes, IME it is always better to stick to + * and ~ or some similar characters in the base 7 bit ASCII set where you are dealing with operations that are similar to addition, multiplication and negation.

 

[DEvens]

I would read (outside c or inside d)

Fixed.

 

[DEvens]

Well that's a slightly different arrangement to the one I outlined (and you hinted at); the nodes on the wiki page have an arbitrary number of children whereas 'my' nodes have at most two children.
[snips]

Considering that my example already had three...

 

[pbuk]

Considering that my example already had three...

This has three:

(a b):(c -d):(f -g)

but you wrote

((a b):(c -d)):(f -g)

 

[BvU]

Fixed.

Great. Now my post looks like nonsense

 

[DEvens]

Guys, maybe you noticed the post where I said "Got it!" and posted a link? Mods, please close this thread.

 

[PeterDonis]

Thread closed.