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

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 2

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 3

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.

Answer 4

You can use https://github.com/mrazekv/logicalparser

Its simply library to write logical expression (evaulated with precenednce table, allows to OR, NOT, AND operator and >, >=, <=, < on integer variables and = on string variables)

Answer 5

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

Answer 6

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 7

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 8

This will not be the best answer, but I myself had this problem some time ago.

Here is my old code: VB.Net - no warranty at all!

https://cloud.downfight.de/index.php/s/w92i9Qq1Ia216XB

Dim BoolTermParseObjekt As New BoolTermParse
MsgBox(BoolTermParseObjekt.parseTerm("1 und (((0 oder 1 und (0 oder 4))) oder 2)").ToString)

This code eats a String with multiple '(', ')', 'and', 'or' plus 'other things' and breaks down the logic to a boolean by replacing the things with boolean values. therefore:

Whatever 'other things' I wanted to evaluate I had to put in Function resolveTerm() at the comment "'funktionen ausführen und zurückgeben, einzelwert!" in page 2. There the only evaluation rightnow is "If number is > 1"

Greetings

Answer 9

Take a look at my library, Proviant. It's a .NET Standard library using the Shunting Yard algorithm to evaluate boolean expressions.

It could also generate a truth-table for your expressions.

You could also implement your own grammar.