Data Structures to represent logical expressions

Question

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)

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.