# Data Structures to represent logical expressions

Here is a logical statement:

``````term1 AND (term2 OR term3) OR term4
``````

What is an effective way of storing this information in a data structure?

For example, should I use a graph, with a property on each edge defining the operator to the next term? (This suggestion doesn't make sense IMO, but it's a data structure that might be useful for this)

-

I used an object graph to code something similar before. Each object in the graph has its own structure.

For example:

``````BinaryLogicalExpression : BooleanExpression
{
Left : BooleanExpression
Right : BooleanExpression
Operator : BinaryLogicalOperator
}
ArithmeticExpression : Expression
{
Left : Expression
Right : Expression
Operator : ArithmeticOperator
}
// for modelling brackets...
LogicalGroupExpression : BooleanExpression
{
GroupedExpression : BooleanExpression
}
// to hold constant values...
IntegerConstant : Expression
{
Value : int
}
StringConstant : Expression
{
Value : string
}
``````

I'd then use a series of `Visitor` implementations to traverse the object graph for evaluation and processing of the expression.

``````Expression
{
Accept(ExpressionVisitor visitor);
}

ExpressionVisitor
{
Visit(BinaryLogicalExpression e);
Visit(ArithmeticExpression e);
Visit(StringConstant e);
Visit(IntegerConstant e);
etc...
}
``````

Using an object graph and `Visitor` makes it easy to serialize such expressions to XML or similar hierarchical data structure.

-

I'd try trees, nest them so that each level has the operator on a left branch and all the data on a right branch ala Lisp.

-

In C you might do something like this:

``````enum NodeType {OPERATOR, VARIABLE};
enum Operator {AND, OR, NOT, IFF, PLY};
struct Node {
enum NodeType typ;
enum Operator op;
struct node *left;
struct node *right;
};
``````

Parentheses don't appear explictly in the structure. Any `struct Node` instance with `typ == OPERATOR` effectively parenthesizes the two terms that `left` and `right` elements point to. You would also have to decide on a convention for the NOT operator: only one of `left`, `right` point to the negated term.

-

an array could be used, so:

``````term1 AND ( (term2 OR term3) OR term4 )
``````

would be:

``````[ {term1},
{ 'OR' : [ { 'OR' : [ {term2} , {term3} ] },
{term4}
]
}

]
``````

in PHP:

``````array('term1',array('OR'=>array(array('OR'=>array('term2','term3')),'term4')));
``````

this notation is used in the CakePhp framework =).

Good Luck

-