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

-

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

-

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.

-