Expression evaluation design questions

Question

Hi,

I a modeling a system to evaluate expressions. Now the operands in these expressions can be of one of several types including some primitive .NET types. When defining my Expression class, I want some degree of type-safety and therefore don't want to use 'object' for the operand object type, so I am considering defining an abstract Operand base class with nothing in it and creating a subclass for each type of Operand. What do you think of this?

Also, only some types of operands make sense with others. And finally, only some operators make sense with particular operands. I can't really think of a way to implement these rules at compile-time so I'm thinking I'll have to do these checks at runtime.

Any ideas on how I might be able to do this better?

Answer 1

I'm not sure if C based languages have this, however Java has several packages that would really make sense for this.

The JavaCC or java compiler compiler allows you to define a language (your expressions for example) and them build the corresponding java classes. A somewhat more user friendly if not more experimental and academic package is DemeterJ - this allows you to very easily specify the expression language and comes with a library for defining visitors and strategies to operate over the generated class structure. If you could afford to switch to Java I might try that. Other wise I'd look for a C# clone of one of these technologies.

Another thing to consider if you go down this route is that once you've generated your class structure within some reasonable approximation of the end result, you can subclass all of the generated classes and build all of your application specific login into the subclasses. That way if you really need to regenerate a new model for the expression language your logic will be relatively independent of your class hierarchy.

Update: Actually it looks as though some of this stuff is ported to .NET technology though I havent used it so I'm not sure what shape it may be in:

http://www.ccs.neu.edu/home/lieber/inside-impl.html

good luck!

Answer 2

I've recently built a dynamic expression evaluator. What I found to be effective was to create, as you suggested, a BaseOperand with meaningful derived classes (NumericOperand, StringOperand, DateOperand, etc) Depending on your implementation, generics may make sense as well (Operand).

Through the implementation of the Visitor pattern, you can perform any kind of validation you like.

I had a very specific need to roll my own solution, but there are many options already available for processing expressions. You may want to take a look at some of these for inspiration or to avoid reinventing the wheel.

Answer 3

How about Expression in 3.5? I recently wrote an expression parser/compiler using this.

Answer 4

I found a good approach to handle the types of objects with EXPRESSIONOASIS framework. They are using custom data structure to carry the types of the objects. So after parsing the operand with regular expressions and given expressions, they decide the type and store this type as property of a generic class which can be used any time for getting the type.

http://code.google.com/p/expressionoasis/