Parsing Conditions using Interpreter and Visitor Pattern

• Download source and executable - 53.7 Kb

Introduction

This article gives a flexible and simple (maybe not that simple) method to do condition parsing. It also shows the usage of the visitor pattern and the interpreter pattern.

In the example of this article, we define the properties of a desired person as: (NAME='test' AND GENDER='M' AND HEIGHT>100 AND WEIGHT<1000). For a given person whose properties are (NAME='test' AND GENDER='M' AND HEIGHT=101 AND WEIGHT=888), when evaluated by the criteria defined above, the result will be 'is a desired person' because 101>100 and 888<1000; if we change the person's NAME to 'test1' or GENDER to 'F' or HEIGHT to '99', the result will be 'not a desired person'.

The classes

CMetaCondition defines a tstring value (m_tsValue) as a data member and some operations to compare a given value with m_tsValue, those operations are EQUAL, NOT_EQUAL, GREATER_THAN, LESS_THAN, CONTAINS, NOT_CONTAINS. You may expand these operations as you wish.

class CMetaCondition 
{
public:
       enum KeyValueOp {KEYVALUE_OP_EQUAL, KEYVALUE_OP_NOT_EQUAL,
                       KEYVALUE_OP_GREATER_THAN, KEYVALUE_OP_LESS_THAN,
                       KEYVALUE_OP_CONTAINS, KEYVALUE_OP_NOT_CONTAINS};
public:
       int m_iKey;
       KeyValueOp m_op;
       tstring m_tsValue;...
};

CCondition has a data member m_conditions, which is a vector of sub conditions. When evaluated, if the condition operation(m_op) of a CCondition object is META, the m_metaCondition field will take effect, otherwise, AND or OR will be applied on m_conditions. For an AND operation, if all the sub conditions are true, the result will be true; For an OR operation, if one of the subconditions is true, the result will be true. The code shows this:

class CCondition
{
public:
 enum ConditionOp{CONDITION_OP_AND,CONDITION_OP_OR,CONDITION_OP_META};
public:
 /*if m_op is CONDITION_AND, or CONDITION_OR,
 the m_conditions field will take effect.
 Otherwise, the m_metaCondition field will take effect.
 */
 ConditionOp m_op;
 vector<CCONDITION> m_conditions;
 CMetaCondition m_metaCondition;

public:
 BOOL IsTrue(CConditionInterpreter* pInterpreter);
...
};

CConditionInterpreter has only one method: IsTrue(...). You'll see later in this article that when applied with the visitor pattern, this method is just visit(...­) method of the visitor pattern; when applied with the interpreter pattern, this method is better named as interpret(...). Since the two patterns are bound together, the method is named as IsTrue(...­).

class CConditionInterpreter
{
public:
 virtual BOOL IsTrue(CMetaCondition& metaCond) = 0;
}

CPersonChooser is derived from CConditionInterpreter, it overrides the virtual method: IsTrue(...), that is where the actual visit and interpreting happens.

class CPersonChooser : public CConditionInterpreter
{
public:
 CPersonChooser(const CPerson& person);
 virtual ~CPersonChooser();

 virtual BOOL IsTrue(CMetaCondition& metaCondition);
private:
 CPerson m_person;
}

The following code shows how to use them together:

//define the desired condition
m_conditions= predefined_condition;
...
CPerson person;
person.name="test";
person.gender="M";
person.height="101";
person.weight="888";

//construct a CPersonChooser using
//the given person's properties
CPersonChooser* pChooser=new CPersonChooser(person);

//m_condition Accepts a CPersonChooser, then the CPersonChooser
//visits and interprets the (meta) condition
BOOL isDesiredPerson=m_condition.IsTrue(pChooser);

CString strInfo=isDesiredPerson?"IS":"NOT";
strInfo+=" a desired person";
AfxMessageBox(strInfo);

delete pChooser;

In the next section, I'll explain how the visitor pattern and the interpreter pattern are applied to these classes.

The visitor pattern

The motivation of the visitor pattern is: Represent an operation to be performed on the elements of an object structure.

In our example, CConditionInterpreter is the Visitor class in the diagram, CPersonChooser is a concrete visitor derived from it, CCondition is an Element class (and also a concrete element class itself).

The IsTrue(...­) method of CCondition acts as the Accept member function of a normal element class according to the standard visitor pattern. It calls the visit method (CPersonChooser::IsTrue(...­)) of the visitor (pInterpreter) inside its Accept method.

return pInterpreter->IsTrue(m_metaCondition);

The interpreter pattern

The motivation of the interpreter pattern is: Given a language, define a representation for its grammar along with an interpreter that uses the representation to interpret sentences in a language.

In our example, CMetaCondition is a Context while CConditionInterpreter is an AbstractExpression, and CPersonChooser is a TerminalExpression.

The IsTrue(...) method of CConditionInterpreter and CPersonChooser acts as the Interpret(in Context) member function of a normal XXXExpression class according to the standard interpreter pattern, that is where the actual interpreting happens.

public:
       virtual BOOL IsTrue(CMetaCondition& metaCondition);
       // this member function acts as Interpret(in Context) of a normal 
       // Expression class

The code

//The Accept method of the visitor pattern
BOOL CCondition::IsTrue(CConditionInterpreter* pInterpreter)
{       if (m_op == CONDITION_OP_AND) {
              if (m_conditions.size() == 0)
                     return FALSE;
              BOOL bAndCondIsTrue = TRUE;
              for (vector<CCondition>::iterator it = m_conditions.begin(); 
            it != m_conditions.end(); it++) {
                     if (!(*it).IsTrue(pInterpreter)) {
                            bAndCondIsTrue = FALSE;
                            break;
                     }
              }
              return bAndCondIsTrue;
       }
       if (m_op == CONDITION_OP_OR) {
              if (m_conditions.size() == 0)
                     return FALSE;
              BOOL bOrCondIsTrue = FALSE;
              for (vector<CCondition>::iterator it = m_conditions.begin(); 
                   it != m_conditions.end(); it++)  {
                     if ((*it).IsTrue(pInterpreter)) {
                            bOrCondIsTrue = TRUE;
                            break;
                     }
              }
              return bOrCondIsTrue;       
       }
       return pInterpreter->IsTrue(m_metaCondition);
}
//...
//The Visit method of the visitor pattern and Interpret method of
//the interpreter pattern
BOOL CPersonChooser::IsTrue(CMetaCondition& metaCondition)
{
       switch (metaCondition.m_iKey) {
       case KEY_NAME:
              switch(metaCondition.m_op) {
              case metaCondition.KEYVALUE_OP_EQUAL:
                  return (m_person.name == metaCondition.m_tsValue);
              case metaCondition.KEYVALUE_OP_NOT_EQUAL:
                  return (m_person.name != metaCondition.m_tsValue);
              case metaCondition.KEYVALUE_OP_GREATER_THAN:
                  return (m_person.name > metaCondition.m_tsValue);
              case metaCondition.KEYVALUE_OP_LESS_THAN:
                  return (m_person.name < metaCondition.m_tsValue);
              default:
                  break;
              }
              break;
       case KEY_GENDER:
              switch(metaCondition.m_op) {
              case metaCondition.KEYVALUE_OP_EQUAL:
                  return (m_person.gender == metaCondition.m_tsValue);
              case metaCondition.KEYVALUE_OP_NOT_EQUAL:
                  return (m_person.gender != metaCondition.m_tsValue);
              default:
                  break;
              }
              break;
       case KEY_HEIGHT:
              switch(metaCondition.m_op) {
              case metaCondition.KEYVALUE_OP_EQUAL:
                 return (m_person.height == 
                          atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_NOT_EQUAL:
                 return (m_person.height != 
                          atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_GREATER_THAN:
                 return (m_person.height > 
                          atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_LESS_THAN:
                 return (m_person.height < 
                          atoi(metaCondition.m_tsValue.c_str()));
              default:
                 break;
              }
              break;
       case KEY_WEIGHT:
              switch(metaCondition.m_op) {
              case metaCondition.KEYVALUE_OP_EQUAL:
                 return (m_person.weight == 
                     atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_NOT_EQUAL:
                 return (m_person.weight != 
                     atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_GREATER_THAN:
                 return (m_person.weight > 
                     atoi(metaCondition.m_tsValue.c_str()));
              case metaCondition.KEYVALUE_OP_LESS_THAN:
                 return (m_person.weight < 
                     atoi(metaCondition.m_tsValue.c_str()));
              default:
                 break;
              }
              break;
       }      
       return FALSE;
}

Credits

• I learned the usage of this idiom from my co-worker Alvin Robin Shen. He is a real programmer and a very nice guy. I used to get the opportunity to write the condition configuration module for him during our project development and all the classes presented in this article are copied from him. Now he is busy with his open source project: Luntbuild.
• When you look at the downloaded source code, you'll find that I have used a CComboListCtrl as the main UI for condition setting. This class is written by Aravindan Premkumar. You can find the introduction of this control at: Customized Report List Control with In-Place Combo Box & Edit Control.