Expression evaluator for C#/Python/Ruby

Question

We have semi-complicated expressions in the format:
"25 + [Variable1] > [Variable2]"

We need an expression evaluator to parse the expression and use a callback to ask for the variable values and work out the overall result of the expression. It has to be a callback as there are thousands of variables.

We need the usual math operators but also things like "if" etc. The richer the language the better.

We can use any language we want. Anyone have any suggestions?

Heddi

Unless you have a exact spec for the language, all we can do is suggest general resources on language implementation. And even given that, we'll just point you to helpful ressources because it's your compiler construction course, not ours ;) – Featherbrain

What you mean by 'semi-complicated'? What is the real-world situation behind of your question? Or it's just homework? If so please tag your question appropriate manner. Thanks – Abmho

Answer 1

Check out NCalc. It's .NET and should support your requirements.

Ozell

Answer 2

Have you considered using Mono.CSharp.Evaluator? It seems like this in conjunction with an appropriatelly set InteractiveBaseClass would do the trick quite nicely, and with minimal effort.

Note that the following uses Mono 2.11.1 alpha.

using System;
using System.Diagnostics;
using Mono.CSharp;
using NUnit.Framework;

public class MonoExpressionEvaluator
{
    [Test]
    public void ProofOfConcept()
    {
        Evaluator evaluator = new Evaluator(new CompilerContext(new CompilerSettings(), new ConsoleReportPrinter()));
        evaluator.InteractiveBaseClass = typeof (Variables);
        Variables.Variable1Callback = () => 5.1;
        Variables.Variable2Callback = () => 30;

        var result = evaluator.Evaluate("25 + Variable1 > Variable2");

        Assert.AreEqual(25 + Variables.Variable1 > Variables.Variable2, result);
        Console.WriteLine(result);
    }

    public class Variables
    {
        internal static Func<double> Variable1Callback;

        public static Double Variable1 { get { return Variable1Callback(); } }

        internal static Func<double> Variable2Callback;

        public static Double Variable2 { get { return Variable2Callback(); } }
    }
}

Real shame it runs a little slow. For instance, on my i7-m620 it takes almost 8 seconds to run this 10,000 times:

[Test]
public void BenchmarkEvaluate()
{
    Evaluator evaluator = new Evaluator(new CompilerContext(new CompilerSettings(), new ConsoleReportPrinter()));
    evaluator.InteractiveBaseClass = typeof(Variables);
    Variables.Variable1Callback = () => 5.1;
    Variables.Variable2Callback = () => 30;

    var sw = Stopwatch.StartNew();
    for (int i = 1; i < 10000; i++)
        evaluator.Evaluate("25 + Variable1 > Variable2");
    sw.Stop();

    Console.WriteLine(sw.Elapsed);
}

00:00:07.6035024

It'd be great if we could parse and compile it to IL so we could execute it at .NET speeds, but that sounds like a bit of a pipe dream...

[Test]
public void BenchmarkCompiledMethod()
{
    Evaluator evaluator = new Evaluator(new CompilerContext(new CompilerSettings(), new ConsoleReportPrinter()));
    evaluator.InteractiveBaseClass = typeof(Variables);
    Variables.Variable1Callback = () => 5.1;
    Variables.Variable2Callback = () => 30;

    var method = evaluator.Compile("25 + Variable1 > Variable2");
    object result = null;
    method(ref result);
    Assert.AreEqual(25 + Variables.Variable1 > Variables.Variable2, result);

    Variables.Variable2Callback = () => 31;
    method(ref result);
    Assert.AreEqual(25 + Variables.Variable1 > Variables.Variable2, result);

    var sw = Stopwatch.StartNew();
    for (int i = 1; i < 10000; i++)
        method(ref result);
    sw.Stop();
    Console.WriteLine(sw.Elapsed);
}

00:00:00.0003799

Oh my.

Need excel-like expression constructs like IF? Build your own!

    [Test]
    public void ProofOfConcept2()
    {
        Evaluator evaluator = new Evaluator(new CompilerContext(new CompilerSettings(), new ConsoleReportPrinter()));
        evaluator.InteractiveBaseClass = typeof(Variables2);
        Variables.Variable1Callback = () => 5.1;
        Variables.Variable2Callback = () => 30;

        var result = evaluator.Evaluate(@"IF(25 + Variable1 > Variable2, ""TRUE"", ""FALSE"")");

        Assert.AreEqual("TRUE", result);
        Console.WriteLine(result);
    }

    public class Variables2 : Variables
    {
        public static T IF<T>(bool expr, T trueValue, T falseValue)
        {
            return expr ? trueValue : falseValue;
        }
    }

Coster

Answer 3

Pure expression evaluators are actually pretty easy to write.

See this SO answer which shows expression evaluators in a dozen langauges. You should be able to adapt one of these:

Code Golf: Mathematical expression evaluator (that respects PEMDAS)

EDIT: Whoever dinged this obviously didn't go and examine the solutions there. Yes, there are a bunch that are crammed tight to meet the golf-rules (typically "smallest") but most of them are explained pretty clearly with a cleartext version of algorithm.

Joerg

Those don't have much extensibility for things like if constructs or callbacks for variables. – Claim

I agree. People aren't even really trying to golf many of the solutions over there in the first place. – Tyranny

They aren't very hard to modify. "if(a,b,c)" is just a piece of syntax that you have to parse; parsing was part of the provide solution. Callbacks for variables just means that when a variable is detected, you need to add a callback to the code. You certainly have to customize these a bit. My point is that they are so simple, that it doesn't make a lot of sense to try and go find a subroutine package that does exactly what you want; you can code exactly what you want. These are typically 100-200 lines! If OP isn't capable of coding one these, a package won't help him much either. – Joerg

@Ken: your comment arrived at an awkward moment and is thus a bit ambiguous: are you agreeing with Gabe or me? – Joerg

Answer 4

Well ... you need a language. You have C#, VB.Net, IronPython, IronRuby, and others.

Simple replace the open variables using regex (maybe you even know them ahead and just need a string.Replace) and then compile the script using CodeDOM (for C# or VB.Net) or use the DLR (IronPython, IronRuby). You can simply add the variables as method parameters in the method wrapper you use to encapsulate your code (for CodeDOM) or just inject the variables in the DLR. Both variants we implemented in our team in business with less effort and reliable effort.

When you urgently regquire the callback, well the add to the solutions above a method which communicate with the host of the programming language with a name like ValueOf(string). So you can write

ValueOf("A") > ValueOf("B") - 10

Have fun.

Guthrey

Answer 5

http://code.google.com/p/bc-expression/

Handles variable lookup via a lambda or block callback.

Understands numeric, string and boolean constants.

Unary operators + - !

Operators || && < <= == != >= > + - * / %

Grouping with ( )

Raises an Expression::SyntaxError if there's a syntax error.

Hirai