Dynamic logical expression parsing/evaluation in C# or VB?

Question

What is the best was to evaluate an expression like the following:
(A And B) Or (A And C) Or (Not B And C)
or
(A && B) || (A && C) || (!B && C)

At runtime, I was planning on converting the above expressions to the following:
(True And False) Or (True And False) Or (Not False And True)
or
(True && False) || (True && False) || (! False && True)

Conditions: 1) The logical expression is not known until runtime. 2) The number variable and their values are not known until runtime. 3) Variable values are never null.

I know I could create a simple assemble with a class and a method that I generate at runtime based on the inputs, but is there a better way. I have done this before. Use a string builder to write the code, then call the compiler. After that, you load the assembly and call the method.

Suggestions?

Thanks.

Answer 1

You can write a simple interpreter/parser. Use something like ANTLR and reuse existing grammars.

Answer 2

If you're using .NET3.5 then you can parse the text and create an abstract sytax tree using the Expression classes. Then create a suitable LambdaExpression instance and compile it into a delegate, which you can then execute.

Constructing a parser and syntax tree builder for this kind of fairly simple grammer is quite an interesting exercise, and will execute somewhat faster than invoking the compiler (and it's neater in my view as well).

If you're not using .NET3.5, then it's also not complicated to implement an interpreted abstract syntax tree yourself.

Answer 3

Be warned: the two final conditions you're talking about are not necessarily equivalent. The && operators in C# will use short-circuit evalution, while the logical And operator in VB does not. If you want to be sure the statements are equivalent, translate a user And to AndAlso and a user Or to OrElse.

For simple expresssions you probably won't notice a difference. But if the conditions can have side effects or if the performance difference between the two is a concern, this can be important.

Answer 4

If you are using .NET 3.5, you can create a Lambda Expression. Then you can create a delegate from it and call as standard delegate/method. On the internet is a lot of samples about Lambda Expressions.

Answer 5

One solution would be to assemble the expression as a string, and then send it SQL Server, or whatever your database is for evaluation. Replace the actual variables with 1=1 or 0=1 for True and False respectively, and you would end up with a query like this:

SELECT 1 WHERE (1=1 And 0=1) Or (1=1 And 1=1) Or (Not 0=1 And 1=1)

Then when you run the query, you get a 1 back when the result is true. May not be the most elegant solution, but it will work. A lot of people will probably advise against this, but I'm just going to throw it out there as a possible solution anyway.

Answer 6

You can do this easily with:

1. a parser generator (like ANTLR, mentioned above) that takes boolean expressions as input and produces an infix list and
2. code to evaluate a Reverse Polish Notation stack.

The grammar looks something like this:

program: exprList ;

exprList: expr { Append($1); }
    | expr OR exprList { Append(OR); }
    | expr AND exprList { Append(AND); }
    | NOT exprList { Append(NOT); }
    | ( exprList ) { /* Do nothing */ }
    ;

expr: var { Append($1); }
    | TRUE { Append(True); }
    | FALSE { Append(False); }
    ;

To evaluate, you do this:

for each item in list
    if item is symbol or truth value, push onto RPN stack
    else if item is AND, push (pop() AND pop())
    else if item is OR, push (pop() OR pop())
    else if item is NOT, push (NOT pop())

result = pop()

For symbols, you have to substitute the truth value at runtime.