Best algorithm for evaluating a mathematical expre

问题:

What's the best algorithm for evaluating a mathematical expression? I'd like to be able to optimize this a little in the sense that I may have one formula with various variables, which I may need to evaluate hundreds of times using different variables. So basically if I can initially parse the formula so that it is optimized in some way, and I can then pass in the variables to this optimized version as many times as I need, each time it produces a result for me.

I'll be writing this in either Delphi or C#. I have already written something similar by using the shunting yard algorithm, but each time I need to calculate the same formula, I'm having to go through the parsing stage. There must be a better way to do this.

回答1:

If you want to do it with Delphi, you could look into how the JclExprEval unit works, part of the JEDI Code Library. I wrote it several years ago (it's a little over-engineered); it parses functions and variables and can hand you back a method pointer which evaluates the expression quickly. Pass the variables in by reference, and you can change them directly and the re-evaluated expression will be calculated accordingly.

In any case, the basics of how it works may be helpful for you. Recursive-descent parsing of expressions is easy, and by building a tree you can evaluate multiple times without re-parsing. JclExprEval actually generates code for a simple stack machine, so that it can work a little faster than tree interpretation; stack machines largely restrict their memory operations to arrays and use switches for opcodes, while tree interpretation follows links throughout the heap and often uses virtual dispatch (or double-dispatch) for opcodes, so they usually end up slower.

Taking the same approach as JclExprEval in parsing but written in C#, and building up an Expression, like Marc suggests, is another perfectly valid approach. The JIT-compiled expression ought to be quite a bit faster than an interpreted expression program or tree, which themselves are a lot faster than parsing.

回答2:

In C# with .NET 3.5, you can use Expression for this; you can build a parameterised expression and then compile it to a delegate. This is exactly what I did for the maths aspect of Finguistics. I still have the parsing code I used if you want it...

The main trick I used was that to keep the delegate type known, I used an array as the input type - treating different args as arr[0], arr1, arr[2] etc. This means I could compile to (for example) a Func<decimal[], decimal> (takes an array of decimals, returns a decimal).

Once you have called Compile(), this is pertty much as though you had code to do it directly.

(edit)

As a brief example of using Expression in this way (with a hard-coded function), see below. The parser I have already written currently works as a predicate checker - i.e. to check that "? + (2 * ? - ?) = 22 + ?" - but it wouldn't be hard to change it to return the result instead (and introduce more operations, like sin/pow/etc - presumably by mapping them directly to public methods on a helper object (via Expression.Call)).

using System;
using System.Linq.Expressions;
static class Program
{
    static void Main()
    {
        var args = Expression.Parameter(typeof(float[]), "args");
        var x = Expression.ArrayIndex(args, Expression.Constant(0));
        var y = Expression.ArrayIndex(args, Expression.Constant(1));
        var add = Expression.Add(x, y);
        var lambda = Expression.Lambda<Func<float[], float>>(add, args);

        Func<float[], float> func = lambda.Compile();
        Console.WriteLine(func.Call(1, 2));
        Console.WriteLine(func.Call(3, 4));
        Console.WriteLine(func.Call(5, 6));
    }

    static T Call<T>(this Func<T[], T> func, params T[] args)
    { // just allows "params" usage...
        return func(args);
    } 
}