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.