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

Placatory

Answer 1

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

Audryaudrye

+1 for ANTLR. If you look at this and dismiss it, thinking that this is too much hassle, please reconsider. I recommend you use ANTLRworks as a grammar development tool and have it output its lexer and parser classes into your Visual Studio project tree. It's relatively seamless and it's easy to iteratively tweak your grammar and quickly see its effects in your .NET world. – Outrageous

By "you" above, I mean Thomas the OP. – Outrageous

@Chris Farmer: This is targetting C# Compact Framework...might be a bit heavy for that... – Doreathadoreen

I dunno. With a relatively simple expression grammar, the generated lexer and parser will be pretty small. It's worth a shot, IMO. It'll at least be easy for Thomas to realize this up-front if it's not going to work, so there won't be too much time wasted if it doesn't work out. – Outrageous

Answer 2

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.

Karilynn

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

Essa

According to the question, the expression is actually entered by the user. Thus your solution is prone to SQL injection. – Laryngotomy

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.

Micronesian

If you can shell out to a language with "eval", however, the problem is solved. You look for true or false, and for everything else, you know you're invalid. – Micronesian

I think "eval" is entirely the wrong way to go. It's potentially easy, but it's risky letting people write any code that's legal in your language. It's better, IMHO, to have a distinct and limited grammar that's available for these expressions. – Outrageous

Answer 5

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

Argeliaargent

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.

Doreathadoreen

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.

Oolite