适用于 .NET 的计算引擎

• 下载源代码 - 90.0 KB

引言

我最近需要构建一个 Silverlight 应用程序，该应用程序显示一个尽可能像 Excel 的网格。我需要的一个东西是小型、快速、灵活的计算引擎，它允许用户在网格单元格中输入公式并查看结果。

我快速搜索了一下，找到了几个不错的计算引擎，但不幸的是没有一个符合我的需求。有些太大，有些无法在 Silverlight 下构建，有些是 C++ 的，有些需要第三方解析器 DLL 等。

于是我决定调整我之前为报告库编写的脚本引擎的解析器和逻辑。这段代码是稳定而可靠的。我所要做的就是提取我需要的部分，清理它们，并尽可能优化它们以减小尺寸和提高速度。

结果就是 **CalcEngine**，一个小型、快速且可扩展的计算引擎。我对它很满意；我的 Silverlight 项目现在已经完成，而且我还在几个 WinForms 项目中使用了它。

接下来的章节将描述 CalcEngine 类提供的功能，以及如何在扩展 DataGridView 控件以提供公式的项目中使用它。

最后一节包含一些基准测试和 CalcEngine 与其他流行计算引擎之间的比较，以便您可以决定何时何地使用它们。

在深入探讨实际内容之前，请允许我做一个快速声明：在我最初的研究过程中，我注意到一些读者认为这个主题已经过时了。在他们看来，关于表达式解析器和求值器的文章已经太多了。我不同意。关于这个主题的文章确实很多，但这是因为这个主题很深奥、有趣且有用。**NCalc** 的作者 Sebastien Ros 在他最初的 CodeProject 文章中说得很好：

"创建一个数学表达式求值器是计算机科学中最有趣的练习之一，无论使用哪种语言。这是真正理解编译器和解释器背后隐藏的魔力第一步……"。

我完全同意，并希望您也同意。

使用 CalcEngine 类

CalcEngine 类执行两项主要任务：

1. 将包含公式的字符串解析为可以计算的 Expression 对象。
2. 计算 Expression 对象并返回它们代表的值。

要计算代表公式的字符串，您需要调用 CalcEngine.Parse 方法获取一个 Expression，然后调用 Expression.Evaluate 方法获取值。例如：

var ce = new CalcEngine();
var x = ce.Parse("1+1");
var value = (double)x.Evaluate();

或者，您可以直接调用 CalcEngine.Evaluate 方法。这会将字符串解析为表达式，计算表达式，然后返回结果。例如：

var ce = new CalcEngine();
var value = (double)ce.Evaluate("1+1");

第一种方法的优点是它允许您存储解析后的表达式并重新计算它们，而无需多次重新解析相同的字符串。然而，第二种方法更方便，而且因为 CalcEngine 具有内置的表达式缓存，所以解析开销非常小。

函数

CalcEngine 类实现了 69 个函数，从 Excel 的 300 多个函数中选取。可以使用 RegisterFunction 方法轻松添加更多函数。

RegisterFunction 接受一个函数名称、参数数量（最小和最大）以及负责计算函数的委托。例如，“atan”函数实现如下：

var ce = new CalcEngine();
ce.RegisterFunction("ATAN2", 2, Atan2);

static object Atan2(List<Expression> p)
{
    return Math.Atan2((double)p[0], (double)p[1]);
}

函数名不区分大小写（如 Excel 中），参数本身就是表达式。这允许引擎计算诸如“=ATAN(2+2, 4+4*SIN(4))”之类的表达式。

CalcEngine 类还提供了一个 Functions 属性，该属性返回一个包含当前定义的​​所有函数的字典。如果您需要枚举移除引擎中的函数，这会很有用。

请注意，上面列出的方法实现如何将表达式参数强制转换为预期的类型（double）。这是因为 Expression 类实现了到多种类型的隐式转换器（string、double、bool 和 DateTime）。我认为隐式转换器允许我编写简洁明了的代码。

如果您不喜欢隐式转换器，另一种方法是覆盖 Expression 类中的 ToString 并添加 ToDouble、ToDateTime、ToBoolean 等。

变量：绑定到简单值

大多数计算引擎都提供了一种方法来定义可以在表达式中使用的变量。CalcEngine 类实现了一个 Variables 字典，该字典将键（变量名）与值（变量内容）关联起来。

例如，以下代码定义了一个名为 angle 的变量并计算了一个简短的正弦表：

// create the CalcEngine
var ce = new CalcEngine.CalcEngine();

// calculate sin from 0 to 90 degrees
for (int angle = 0; angle <= 90; angle += 30)
{
    // update value of "angle" variable
    ce.Variables["angle"] = angle;

    // calculate sine
    var sin = ce.Evaluate("sin(angle * pi() / 180)");

    // write it out
    Console.WriteLine("sin({0}) = {1}", angle, sin);
}

// output:
sin(0) = 0
sin(30) = 0.5
sin(60) = 0.866025403784439
sin(90) = 1

变量：绑定到 CLR 对象

除了简单值之外，CalcEngine 类还实现了一个 DataContext 属性，该属性允许调用者将常规的 .NET 对象连接到引擎的计算上下文中。引擎使用反射来访问对象的属性，以便它们可以在表达式中使用。

这种方法类似于 WPF 和 Silverlight 中使用的绑定机制，并且比上一节中描述的简单值方法更强大。但是，它也比使用简单值作为变量慢。

例如，如果您想对 Customer 类型的对象执行计算，可以这样做：

// Customer class used as a DataContext
public class Customer
{
    public string Name { get; set; }
    public double Salary { get; set; }
    public List

CalcEngine 支持绑定到子属性和集合。分配给 DataContext 属性的对象可以代表复杂的业务对象和整个数据模型。

这种方法可以更轻松地将计算引擎集成到应用程序中，因为它们使用的变量只是普通的 CLR 对象。您无需学习任何新知识即可应用验证、通知、序列化等。

变量：绑定到动态对象

计算引擎的原始使用场景是类似 Excel 的应用程序，因此它必须能够支持单元格范围对象，例如“A1”或“A1:B10”。这需要一种不同的方法，因为单元格范围必须动态解析（为 DataContext 对象定义具有 A1、A2、A3 等属性是不切实际的）。

为了支持这种情况，CalcEngine 实现了一个名为 GetExternalObject 的虚拟方法。派生类可以通过覆盖此方法来解析标识符并动态构建可计算的对象。

如果返回的对象实现了 CalcEngine.IValueObject 接口，引擎会通过调用 IValueObject.GetValue 方法来计算它。否则，对象本身用作值。

如果返回的对象实现了 IEnumerable 接口，则接受多个值的函数（如 Sum、Count 或 Average）将使用 IEnumerable 实现来获取对象表示的所有值。

例如，本文随附的示例应用程序定义了一个 DataGridCalcEngine 类，该类派生自 CalcEngine 并覆盖了 GetExternalObject 以支持 Excel 风格的范围。这将在后面的章节（“为 DataGridView 控件添加公式支持”）中详细介绍。

优化

我之前提到 CalcEngine 类执行两项主要功能：解析和计算。

如果您查看 CalcEngine 代码，您会注意到解析方法是为速度而编写的，有时甚至会牺牲清晰度。GetToken 方法尤为关键，并且经过了多轮性能分析和调整。

例如，GetToken 使用逻辑语句而不是方便的 char.IsAlpha 或 char.IsDigit 方法来检测字符和数字。这确实产生了在基准测试中明显显示出来的差异。

除此之外，CalcEngine 还实现了另外两种优化技术：

表达式缓存

解析过程通常比实际计算花费更多时间，因此跟踪解析后的表达式并避免再次解析它们是有意义的，特别是如果相同的表达式很可能被一遍又一遍地使用（例如，在电子表格单元格或报表字段中）。

CalcEngine 类实现了一个表达式缓存，可以自动处理此问题。CalcEngine.Evaluate 方法在尝试解析表达式之前会在缓存中查找该表达式。缓存基于 WeakReference 对象，因此未使用的表达式最终会被 .NET 垃圾回收器从缓存中移除。（此技术也用于 **NCalc** 库。）

可以通过将 CalcEngine.CacheExpressions 属性设置为 false 来关闭表达式缓存。

表达式优化

字符串被解析后，可以使用将只引用常量值的表达式部分替换来优化生成的表达式。例如，考虑表达式：

{ 4 * (4 * ATAN(1/5.0) - ATAN(1/239.0)) + A + B }

该表达式包含多个常量和常量的函数。它可以简化为：

{ 3.141592654 + A + B }

第二个表达式等同于第一个表达式，但计算速度快得多。

表达式简化出乎意料地容易实现。它包括一个虚拟的 Expression.Optimize 方法，该方法在表达式被解析后立即调用。

基类 Expression 提供了一个不执行任何操作的 Optimize 方法：

class BinaryExpression : Expression
{
    public virtual Expression Optimize()
    {
        return this;
    }
    ...

这仅仅允许所有派生自 Expression 的类实现自己的优化策略。

例如，BinaryExpression 类实现 Optimize 方法如下：

class BinaryExpression : Expression
{
    public override Expression Optimize()
    {
        _lft = _lft.Optimize();
        _rgt = _rgt.Optimize();
        return _lft._token.Type == TKTYPE.LITERAL &&
               _rgt._token.Type == TKTYPE.LITERAL
            ? new Expression(this.Evaluate())
            : this;
    }
    ...

该方法分别调用两个操作数表达式的 Optimize 方法。如果生成的优化表达式都是字面值，则该方法计算结果（即一个常量）并返回一个表示该结果的字面量表达式。

进一步说明，函数调用表达式的优化如下：

class FunctionExpression : Expression
{
    public override Expression Optimize()
    {
        bool allLits = true;
        if (_parms != null)
        {
            for (int i = 0; i < _parms.Count; i++)
            {
                var p = _parms[i].Optimize();
                _parms[i] = p;
                if (p._token.Type != TKTYPE.LITERAL)
                {
                    allLits = false;
                }
            }
        }
        return allLits
            ? new Expression(this.Evaluate())
            : this;
    }
    ...

首先，所有参数都经过优化。接下来，如果所有优化后的参数都是字面值，则函数调用本身将被替换为表示结果的字面量表达式。

表达式优化以牺牲少量解析时间为代价来减少计算时间。可以通过将 CalcEngine.OptimizeExpressions 属性设置为 false 来关闭它。

全球化

CalcEngine 类有一个 CultureInfo 属性，允许您定义引擎应如何解析表达式中的数字和日期。

默认情况下，CalcEngine.CultureInfo 属性设置为 CultureInfo.CurrentCulture，这会导致它使用用户为解析数字和日期选择的设置。在英语系统上，数字和日期看起来像“123.456”和“12/31/2011”。在德语或西班牙语系统上，数字和日期看起来像“123,456”和“31/12/2011”。这是 Microsoft Excel 使用的行为。

如果您希望表达式在所有系统上看起来都一样，您可以将 CalcEngine.CultureInfo 属性设置为 CultureInfo.InvariantCulture，或者设置为您喜欢的任何文化。

示例：带公式支持的 DataGridView 控件

本文随附的示例展示了如何使用 CalcEngine 类扩展标准的 Microsoft DataGridView 控件以支持 Excel 风格的公式。文章开头的图片显示了示例的运行情况。

请注意，此处描述的公式支持仅限于在单元格中键入公式并计算它们。该示例未实现 Excel 的更高级功能，如剪贴板操作的自动引用调整、选择式公式编辑、引用着色等。

DataGridCalcEngine 类

该示例定义了一个 DataGridCalcEngine 类，该类扩展了 CalcEngine，并带有一个指向拥有该引擎的网格的引用。网格负责存储用于计算的单元格值。

DataGridCalcEngine 类通过覆盖 CalcEngine.GetExternalObject 方法来添加单元格范围支持，如下所示：

/// <summary>
/// Parses references to cell ranges.
/// </summary>
/// <param name="identifier">String representing a cell range 
/// (e.g. "A1" or "A1:B12".</param>
/// <returns>A <see cref="CellRange"/> object that represents 
/// the given range.</returns>
public override object GetExternalObject(string identifier)
{
    // check that we have a grid
    if (_grid != null)
    {
        var cells = identifier.Split(':');
        if (cells.Length > 0 && cells.Length < 3)
        {
            var rng = GetRange(cells[0]);
            if (cells.Length > 1)
            {
                rng = MergeRanges(rng, GetRange(cells[1]));
            }
            if (rng.IsValid)
            {
                return new CellRangeReference(_grid, rng);
            }
        }
    }

    // this doesn't look like a range
    return null;
}

该方法分析作为参数传递的标识符。如果标识符可以解析为单元格引用（例如，“A1”或“AZ123:XC23”），则该方法会构建并返回一个 CellRangeReference 对象。如果标识符无法解析为表达式，该方法将返回 null。

CellRangeReference 类实现如下：

class CellRangeReference : 
    CalcEngine.IValueObject, // to get the cell value
    IEnumerable // to enumerate cells in the range
{
    // ** fields
    DataGridCalc _grid;
    CellRange _rng;
    bool _evaluating;

    // ** ctor
    public CellRangeReference(DataGridCalc grid, CellRange rng)
    {
        _grid = grid;
        _rng = rng;
    }

    // ** IValueObject
    public object GetValue()
    {
        // get simple value (e.g. "A1")
        return GetValue(_rng);
    }

    // ** IEnumerable
    public IEnumerator GetEnumerator()
    {
        // get multiple values (e.g. "A1:B10")
        for (int r = _rng.TopRow; r <= _rng.BottomRow; r++)
        {
            for (int c = _rng.LeftCol; c <= _rng.RightCol; c++)
            {
                var rng = new CellRange(r, c);
                yield return GetValue(rng);
            }
        }
    }

    // ** implementation
    object GetValue(CellRange rng)
    {
        if (_evaluating)
        {
            throw new Exception("Circular reference");
        }
        try
        {
            _evaluating = true;
            return _grid.Evaluate(rng.r1, rng.c1);
        }
        finally
        {
            _evaluating = false;
        }
    }
}

CellRangeReference 类实现了 IValueObject 接口，以返回范围中第一个单元格的值。它通过调用所有者网格的 Evaluate 方法来实现这一点。

CellRangeReference 还实现了 IEnumerable 接口，以返回范围中所有单元格的值。这允许计算引擎计算诸如“Sum(A1:B10)”之类的表达式。

请注意，上面列出的 GetValue 方法使用了一个 _evaluating 标志来跟踪当前正在计算的范围。这允许该类检测循环引用，其中单元格包含引用单元格本身或其他依赖于原始单元格的单元格的公式。

DataGridCalc 类

该示例还实现了一个 DataGridCalc 类，该类派生自 DataGridView 并添加了一个 DataGridCalcEngine 成员。

为了显示公式结果，DataGridCalc 类覆盖了 OnCellFormatting 方法，如下所示：

// evaluate expressions when showing cells
protected override void OnCellFormatting(DataGridViewCellFormattingEventArgs e)
{
    // get the cell
    var cell = this.Rows[e.RowIndex].Cells[e.ColumnIndex];

    // if not in edit mode, calculate value
    if (cell != null && !cell.IsInEditMode)
    {
        var val = e.Value as string;
        if (!string.IsNullOrEmpty(val) && val[0] == '=')
        {
            try
            {
                e.Value = _ce.Evaluate(val);
            }
            catch (Exception x)
            {
                e.Value = "** ERR: " + x.Message;
            }
        }
    }

    // fire event as usual
    base.OnCellFormatting(e);
}

该方法首先检索存储在单元格中的值。如果单元格不在编辑模式下，并且值是一个以等号开头的字符串，则该方法使用 CalcEngine 来计算公式并将结果分配给单元格。

如果单元格处于编辑模式，则编辑器将显示公式而不是值。这允许用户像在 Excel 中一样通过在单元格中键入来编辑公式。

如果表达式计算导致任何错误，则错误消息将显示在单元格中。

此时，网格将计算表达式并显示其结果。但它不跟踪依赖项，因此如果您在单元格“A1”中键入一个新值，则任何使用“A1”中值的公式都不会更新。

为了解决这个问题，DataGridCalc 类覆盖了 OnCellEditEnded 方法来使控件无效。这会导致所有可见单元格在任何编辑后重新绘制并自动重新计算。

// invalidate cells with formulas after editing
protected override void OnCellEndEdit(DataGridViewCellEventArgs e)
{
    this.Invalidate();
    base.OnCellEndEdit(e);
}

别忘了实现前面列出的 CellRangeReference 类使用的 Evaluate 方法。该方法首先检索单元格内容。如果内容是以等号开头的字符串，则该方法会计算它并返回结果；否则，它会返回内容本身。

// gets the value in a cell
public object Evaluate(int rowIndex, int colIndex)
{
    // get the value
    var val = this.Rows[rowIndex].Cells[colIndex].Value;
    var text = val as string;
    return !string.IsNullOrEmpty(text) && text[0] == '='
        ? _ce.Evaluate(text)
        : val;
}

这就是 DataGridCalc 类的内容。请注意，计算值从未存储在任何地方。所有公式都在需要时进行解析和计算。

示例应用程序创建了一个包含 50 列和 50 行的 DataTable，并将该表绑定到网格。该表存储用户键入的值和公式。

该示例还在窗体顶部实现了一个 Excel 风格的公式栏，该公式栏显示当前单元格地址、内容，并具有一个显示可用函数及其参数的上下文菜单。

最后，示例的底部有一个状态栏，显示当前选定内容的摘要统计信息（如 Excel 2010 中的 Sum、Count 和 Average）。摘要统计信息也是使用网格的 CalcEngine 计算的。

测试

我在 CalcEngine 类中内置了一些测试方法。在调试版本中，它们由类构造函数调用：

public CalcEngine()
{
    _tkTbl = GetSymbolTable();
    _fnTbl = GetFunctionTable();
    _cache = new ExpressionCache(this);
    _optimize = true;
#if DEBUG
    this.Test();
#endif
}

这确保了每次使用该类时（在调试模式下）都会执行测试，并且派生类在覆盖基类方法时不会破坏任何核心功能。

Test 方法实现了一个Tester.cs 文件，该文件使用部分类扩展了 CalcEngine。所有测试方法都包含在 #if DEBUG/#endif 块中，因此它们不包含在发布版本中。

这个机制在开发过程中运行良好。它帮助检测了许多细微的错误，如果我在处理独立项目时忘记运行单元测试，这些错误可能会被忽略。

基准测试

在实现 CalcEngine 类时，我使用基准测试来比较其大小和性能与替代库，并确保 CalcEngine 表现良好。CalcEngine 类中的许多优化都源于这些基准测试。

我将 CalcEngine 与另外两个类似的库进行了比较，它们似乎是其中最好的。这两个库都始于 CodeProject 文章，后来迁移到 CodePlex：

• **NCalc**：这是一个非常好的库，小巧、高效且功能丰富。我在 Silverlight 项目中无法使用 NCalc，因为它依赖于 ANTLR 运行时 DLL，而 ANTLR 运行时 DLL 不能在 Silverlight 项目中使用（至少我找不到方法）。
• **Flee**：与 CalcEngine 和 NCalc 不同，Flee 会跟踪公式、它们的值和依赖项。当公式更改时，Flee 会重新计算所有依赖于它的单元格。Flee 的一个有趣功能是它实际上将公式编译成 IL。这代表了一个权衡，因为编译速度相当慢，但计算速度非常快。我决定不在 Silverlight 项目中使用 Flee，因为它相对较大，而且对于我设想的应用程序类型来说，解析时间太长了。

基准测试方法与 Gary Beene 在其 2007 年的 Equation Parsers 文章中所述的方法类似。每个引擎都使用三个表达式测试了解析和计算性能。总花费时间用于计算“Meps”（每秒解析或计算数百万个表达式）指数，该指数代表引擎速度。

使用的表达式如下：

4 * (4 * Atan(1 / 5.0) - Atan(1 / 239.0)) + a + b
Abs(Sin(Sqrt(a*a + b*b))*255)
Abs(Sin(Sqrt(a^2 + b^2))*255)

其中“a”和“b”是设置为 2 和 4 的变量。

每个引擎解析并计算了这些表达式 500,000 次。将这些时间相加，然后通过将重复次数除以消耗的时间来计算“Meps”指数。结果如下：

	时间（秒）		速度（“Meps”）
库	解析	评估	解析	评估
CalcEngine	1.4	1.3	1.04	1.18
NCalc	7.1	5.7	0.21	0.26
Flee	1,283.0	0.5	0.00	2.91
CalcEngine*	10.7	1.5	0.14	0.99
NCalc*	145.2	5.7	0.01	0.27

关于基准测试结果的一些评论

• CalcEngine 的表现不错，是解析器最快，计算器第二快（仅次于 Flee）。
• Flee 在这两种方面都“超乎想象”，解析速度几乎慢了 900 倍，计算速度比 CalcEngine 快 2.5 倍。因为 Flee 将公式编译成 IL，我预计解析速度慢而计算速度快，但这种差异的幅度令人惊讶。
• 用星号标记的条目是在关闭优化的情况下执行的。它们包含在内是为了演示优化选项的影响。

除了速度，大小也很重要，特别是对于需要下载到客户端的 Silverlight 应用程序。以下是库大小的比较：

库	大小（kB）
CalcEngine	26
NCalc	188
Flee	202

CalcEngine 是迄今为止最小的库，比 NCalc 小七倍多。如有必要，可以通过移除一些不太重要的内置函数来进一步减小它的尺寸。

结论

CalcEngine 类紧凑、快速、可扩展且跨平台。我认为它与 NCalc 和 Flee 有足够大的区别，可以为许多类型的项目增加价值，特别是像它诞生的 Silverlight 应用程序。您可以在下面的图片中看到 Silverlight 应用的运行情况，或者通过点击 此处 观看直播。

我希望其他人也能发现 CalcEngine 有用且有趣。

一些读者要求我将代码放在 github 上，以便他们更容易使用，所以我这样做了：

https://github.com/Bernardo-Castilho/CalcEngine

希望您喜欢它！

参考文献

1. Gary Beene 的信息中心软件评论（2007）Equation Parsers
2. NCalc（适用于 .NET 的数学表达式求值器）（C#，2007）CodeProject CodePlex
3. Flee（快速轻量级表达式求值器）（VB，2007）CodeProject CodePlex
4. 快速数学表达式解析器（C++，2004）CodeProject
5. 带插件的可扩展数学表达式解析器（C++，2004）CodeProject