Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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)

share|improve this question
add comment

4 Answers 4

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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