I Need a Fast Runtime Expression Parser

I need a fast runtime expression parser

Have you seen https://ncalc.codeplex.com/ and https://github.com/sheetsync/NCalc ?

It's extensible, fast (e.g. has its own cache) enables you to provide custom functions and varaibles at run time by handling EvaluateFunction/EvaluateParameter events. Example expressions it can parse:

Expression e = new Expression("Round(Pow(Pi, 2) + Pow([Pi2], 2) + X, 2)");

  e.Parameters["Pi2"] = new Expression("Pi * Pi");
  e.Parameters["X"] = 10;

  e.EvaluateParameter += delegate(string name, ParameterArgs args)
    {
      if (name == "Pi")
      args.Result = 3.14;
    };

  Debug.Assert(117.07 == e.Evaluate());

It also handles unicode & many data type natively. It comes with an antler file if you want to change the grammer. There is also a fork which supports MEF to load new functions.

It also supports logical operators, date/time's strings and if statements.

Parsing a mathematical expression

Check out veparser as well. Here is a sample code that shows how you can build an expression evaluator( the code parses the expression and directly calculates the output ). This sample can be modified to store the evaluation tree instead of running it.

using System;
using VeParser;

public class MathEvaluator : CharParser
{
    protected override Parser GetRootParser()
    {
        Func<double, double, double> productFunc = (value1, value2) => value1 * value2;
        Func<double, double, double> divideFunc = (value1, value2) => value1 / value2;
        Func<double, double, double> sumFunc = (value1, value2) => value1 + value2;
        Func<double, double, double> subtractFunc = (value1, value2) => value1 - value2;
        Func<double, double> negativeFunc = value => -value;
        Func<double, double> posititveFunc = value => value;

        var dot = token('.');
        var op = token('(');
        var cp = token(')');
        var sumOp = create(sumFunc, token('+'));
        var subtractOp = create(subtractFunc, token('-'));
        var positiveOp = create(posititveFunc, token('+'));
        var negativeOp = create(negativeFunc, token('-'));
        var productOp = create(productFunc, token('*'));
        var divideOp = create(divideFunc, token('/'));

        // Numbers
        var deciamlPlaceValue = 1M;
        var decimalDot = run(() => { deciamlPlaceValue = 1; }, dot);
        var digit = consume((n, d) => n * 10 + char.GetNumericValue(d), keep(Digit));
        var decimalDigit = consume((n, d) => { deciamlPlaceValue = deciamlPlaceValue * 10; return (double)((decimal)n + ((decimal)char.GetNumericValue(d)) / deciamlPlaceValue); }, keep(Digit));
        var number = any(
            /* float */  create(0, seq(zeroOrMore(digit), decimalDot, oneOrMore(decimalDigit))),
            /* int   */  create(0, oneOrMore(digit))
        );

        var expression = createReference();
        var simpleExpression = createReference();
        // Unary
        var unaryOp = any(positiveOp, negativeOp);
        var unaryExpression = update(d => d.action(d.value),
                    createNew(seq(set("action", unaryOp), set("value", expression))));
        // Binary
        var binaryOp = any(sumOp, subtractOp, productOp, divideOp);

        var binaryExpressinoTree = update(x => x.value1, createNew(
            seq(
                set("value1", simpleExpression),
                zeroOrMore(
                    update(d => { var r = base.CreateDynamicObject(); r.value1 = d.action(d.value1, d.value2); return r; },
                        seq(
                            set("action", binaryOp),
                            set("value2", simpleExpression))))
            )));

        var privilegedExpressoin = seq(op, expression, cp);

        setReference(simpleExpression, any(privilegedExpressoin, unaryExpression, number));

        setReference(expression, any(binaryExpressinoTree, simpleExpression));

        return seq(expression, endOfFile());
    }

    public static object Eval(string expression)
    {
        MathEvaluator me = new MathEvaluator();
        var result = me.Parse(expression.ToCharArray());
        return result;
    }
}

Equation parser efficiency

It's hard to tell from your description if the slowness includes parsing, or it is just the interpretation time.

The parser, if you write it as recursive-descent (LL1) should be I/O bound. In other words, the reading of characters by the parser, and construction of your parse tree, should take a lot less time than it takes to simply read the file into a buffer.

The interpretation is another matter.
The speed differential between interpreted and compiled code is usually 10-100 times slower, unless the basic operations themselves are lengthy.
That said, you can still optimize it.

You could profile, but in such a simple case, you could also just single-step the program, in the debugger, at the level of individual instructions.
That way, you are "walking in the computer's shoes" and it will be obvious what can be improved.

Whenever I'm doing what you're doing, that is, providing a language to the user, but I want the language to have fast execution, what I do is this:
I translate the source language into a language I have a compiler for, and then compile it on-the-fly into a .dll (or .exe) and run that.
It's very quick, and I don't need to write an interpreter or worry about how fast it is.

Best and shortest way to evaluate mathematical expressions

Further to Thomas's answer, it's actually possible to access the (deprecated) JScript libraries directly from C#, which means you can use the equivalent of JScript's eval function.

using Microsoft.JScript;        // needs a reference to Microsoft.JScript.dll
using Microsoft.JScript.Vsa;    // needs a reference to Microsoft.Vsa.dll

// ...

string expr = "7 + (5 * 4)";
Console.WriteLine(JScriptEval(expr));    // displays 27

// ...

public static double JScriptEval(string expr)
{
    // error checking etc removed for brevity
    return double.Parse(Eval.JScriptEvaluate(expr, _engine).ToString());
}

private static readonly VsaEngine _engine = VsaEngine.CreateEngine();

Parsing a string C# (Possibly with Regex)

As per my comment if you intend to use this to evaluate a math expression you should not use Regex as you cannot have any syntactic or semantic understanding of a string you're parsing.

If you're not intending to do that, this should work fine

([\d\.]+|[()e^/%x*+-])

Regexr example

Dotnetfiddle example

---

Related Topics