5

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)

9

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.

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

1

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.

0

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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.