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.

Rhoden

What are you trying to accomplish? Can you share how you are coming to the comparisons? This looks like something that might be better approached differently. – Lazybones

Looks like a list of things to compare. You could iterate the list, and break when you find that any two are true. – Pepito

You could write a simple Propositional Logic parser... I remember having to do one to solve the Wumpus World problem. – Dismissal

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.

Bum

A link or example could be useful. – Diamonddiamondback

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.

Lakeishalakeland

Regardless of whether or not they short circuit, the result of the expression is the same. The only difference is when A,B,C are functions, and short circuiting effects whether or not they are called, it doesn't effect the end result of the expression. – Byzantium

@Byzantium - but it might affect the end result of the system if side-effects are involved. – Shipyard

Answer 3

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)

Paracasein

Answer 4

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.

Speechless

Answer 5

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

Conversation

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.

Polonium

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.

Byzantium

-1: Don't encourage people to write hacks like this, especially in release code. – Mabel

Its an interesting idea. You can swing it easier by using the embedded version of sql server, rather than relying on a full installation. Sometimes hacks like this can save your ass. +1 – Chaddie

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

Dasher

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.

Bayonne