评估数学表达式的最佳算法是什么？

Question

什么是评估数学表达式的最佳算法？我想在某种程度上通过优化来实现这一点，因为我可能有一个包含各种变量的公式，我可能需要使用不同的变量来评估数百次。所以基本上，如果我可以最初解析公式，使其以某种方式进行了优化，然后我可以将变量传递给这个优化版本，每次我需要时都会为我产生结果。

我将在Delphi或C#中编写此代码。我已经通过使用Shunting Yard算法编写了类似的内容，但是每次需要计算相同的公式时，我都必须经过解析阶段。一定有更好的方法来解决这个问题。

- Steve

---

表达式有多复杂？仅限于四则运算还是非常通用的？ - Richard

可能会变得相当复杂，包括具有多个参数的函数。 - Steve

Answer 1

如果您想使用Delphi进行操作，可以研究一下JEDI Code Library中的JclExprEval单元是如何工作的。它由我几年前编写（有点过于工程化）；它解析函数和变量，并可以返回一个方法指针，快速地计算表达式。通过引用传递变量，您可以直接更改它们，重新计算表达式将相应地进行计算。

无论如何，它的基本工作原理对您可能会有所帮助。递归下降解析表达式很容易，通过构建树形结构，您可以多次评估而不必重新解析。JclExprEval实际上为简单的堆栈机器生成代码，因此它比树形解释要快一些；堆栈机器主要将其内存操作限制在数组上，并使用开关进行操作码，而树状解释会遍历整个堆并经常使用虚拟分派（或双重分派）进行操作码，因此它们通常会变慢。

采用与JclExprEval相同的解析方式但使用C#编写，并建立一个Expression，像Marc建议的那样，也是完全有效的方法。JIT编译的表达式应该比解释的表达式程序或树形结构快得多，它们本身比解析快得多。

- Barry Kelly

---

看起来正是我所需要的。谢谢。我喜欢“过度设计”！ - Steve

Answer 2

在C#和.NET 3.5中，您可以使用Expression来实现此目的。您可以构建参数化表达式，然后将其编译为委托。这正是我在Finguistics中用于数学方面的方法。如果您需要，我仍然可以提供我使用的解析代码...

我使用的主要技巧是为了保持委托类型已知，我使用数组作为输入类型 - 将不同的args视为arr[0]、arr1、arr[2]等。这意味着我可以编译成（例如）一个Func<decimal[], decimal>（接受一个decimal数组，返回一个decimal）。

一旦调用了Compile()，就几乎相当于直接编写代码。

（编辑）

以下是使用Expression以这种方式（使用硬编码函数）的简短示例。我已经编写的解析器目前作为一个断言检查器工作 - 即检查“? +（2 *？-？）= 22 +？” - 但很容易将其改为返回结果（并引入更多操作，如sin/pow/等 - 可以通过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);
    } 
}

- Marc Gravell

---

我现在在考虑是否将解析代码作为一个个人项目来做一个“正式”的工作...这不会对现有的代码做出太多改变。 - Marc Gravell

@boj - 好吧，那已经是一年多以前的事了 ;-p 如果我没记错的话，那是一个相当标准的解析器。 - Marc Gravell