Boolean and Math Expression Parser

Question

I am writing an application that allows a user to enter a boolean expression. I need the ability to evaluate the entered boolean expression at runtime and am looking for both a parser and a expressoin validator.

Parser
The parser needs to take a boolean expression as a string and return true/false.

Example:

string expression = "(1 == 1) && (1 > 0)";
Parser parser = new Parser();
boolean result = parser.parse(expression);  // Result should be True.

In addition to handling boolean expressions I also need it to handle Math.

expression = "((1 + 1 * 2) == 1)";
result = parser.parse(expression);  // Result should be False.

Validate
So that I can tell the user if there is a problem with the expression being entered I also need a way to validate the syntax.

I am working in C# using the .NET Compact Framework, but if you know of something written in another language that may be helpful.

Thanks for any help you can provide. Tom

Answer 1

Our project is using NCalc (with ANTLR underneath for lexing/parsing) and we're very happy with it.

NCalc is a mathematical expressions evaluator in .NET. NCalc can parse any expression and evaluate the result, including static or dynamic parameters and custom functions.

Our application requires that it be cross-compiled for both Full and Compact Frameworks. With relatively simple tweaks we were able to make both NCalc and ANTLR work for both framework flavours.

Answer 2

http://www.antlr.org

Antlr grammars can be designed to allow for both parsing and evaluation.

Here's an example: http://www.antlr.org/wiki/display/ANTLR3/Expression+evaluator

Answer 3

Assuming you can change your syntax slightly, let an embedded database do the work for you with a query like this T-SQL:

select case when <Expression> then 1 else 0 end as Result

Using your example:

select case when ((1 = 1) and (1 > 0)) then 1 else 0 end as Result
select case when ((1 + 1 * 2) = 1) then 1 else 0 end as Result

Answer 4

I don't know of any libraries to make this easier, but you really just have two subproblems here. You need to build an infix to postfix converter, then write a basic calculator for the boolean and math operations.

Once you have your boolean tree/stack built, begin performing operations. If you have anything that's not a number, evaluate it by sending the string/expression to the arithmetic calculator which performs infix->postfix conversion and then returns a value.

If you google "infix to postfix" and "stack rpn calculator", you can probably find more resources.

Answer 5

You may be able to use the dotMath library to do this.

Answer 6

Here's an excellent evaluation parser on Codeproject, that uses the eval method and does not rely on CodeDOM or anything like that. Here's an excellent article on building an expression evaluator using Antlr, also on the same site..

Hope this helps, Best regards, Tom.

Answer 7

This type of thing is F#'s bread and butter. You might give that a try. For parsing, use recursive descent, then you can run over the tree that results. If you have control of the input language, you can get by with a quote operation.