袁永福--南京都昌信息科技有限公司創始人

2500行代碼實現高性能數值表達式引擎

南京都昌信息科技有限公司 袁永福 2018-9-23

Http://www.dcwriter.cn

◆◆前言

在一些高自由度的軟件中，特別是報表之類的軟件。需要讓用戶自定義數值表達式，比如定義"A+B*C-D/E",然后再實際運行中把具體的A,B,C,D,E的值代入表達式運算。這能顯著增加軟件的運行時的可配置性，是一個值得廣泛應用的軟件功能。本文就說明了如何使用2500行C#代碼實現一種高性能的數值運算表達式引擎。

完整源代碼下載頁面https://github.com/dcsoft-yyf/DCSoft.Expression。

◆◆ANTLR引擎

提到數值表達式引擎，不得不提起Antlr，一個很著名的開源軟件，能自動生成源代碼來生成語法解析引擎，然后可以在這個語法解析引擎的基礎上來實現運算表達式。

筆者此前也在使用ANTLR相關的代碼來實現了運算表達式引擎，包含了10000行C#源代碼。不過代碼晦澀難懂，改進更加麻煩。近期在處理一個包含大量表達式的場景時出現了性能問題，需要改進。

◆◆新表達式運算引擎

現在作者拋棄了舊的基于ANTLR的引擎，構造了全新的表達式運算引擎，核心模塊只有2500行C#代碼，生成的程序集文件只有27KB，但運行速度提升了10倍。而且程序簡單易懂，擴展性強。當然不再具備ANTLR的廣泛的通用性，但足夠應付作者遇到的應用場景了。

新源代碼中定義的主要類型有：

新引擎工作過程如下：

◆第一步，表達式字符串符號解析

其代碼定義在DCToken.cs中。在此處，將字符分為以下幾種：

所有相鄰的同類型的字符合并在一起成為一組符號，此外還識別單引號或雙引號作為邊界的字符串常量。

以下是符號解析的例子：

◆第二步，解析表達式單元元素

其代碼定義在DCExpression.cs中的 Parse()/ParseItem()函數中。將一個個標識符轉換為表達式單元元素。目前支持以下元素類型：

解析過程是一種遞歸操作,用于構造出一個表達式元素樹狀結構。

首先定義一個DCGroupExpressionItem作為根元素?？梢钥醋靼驯磉_式的最外頭放了一組圓括號。比如把"A+B"當作"(A+B)"。

在這個過程中，遇到標識符并且緊跟著的是"("則認為是函數元素；遇到標識符"true"或"false"則認為是布爾類型的常量元素；遇到可以轉換為數字的標識符則認為是數字常量元素；遇到其他標識符則認為是變量元素；遇到操作標識符則認為是操作符元素類型；遇到"("則為分組元素類型并遞歸解析子元素；遇到")"則認為結束分組元素類型，結束當前遞歸。此外還解析出字符串常量元素。

經過解析操作，構造了只有一個根節點的表達式元素樹狀結構。以下是幾個例子：

◆第三步，優先級調整

數值運算有優先級。規則是數學運算高于邏輯運算，乘除運算高于加減運算，圓括號可以改變運算優先級。

此時需要將一長串的表達式元素按照優先級在此次整理。主要代碼在DCExpression.cs中的CollpaseItems()中，作者稱之為表達式元素列表的收縮。其過程如下：

首先是特別處理減號元素的處理。當減號處于當前組的第一的位置，或者其前面是邏輯運算符時，則將減號元素轉換為取負元素。

然后對元素列表進行一個不定次數的循環。在循環體中，找到優先級最高的而且未經收縮的操作符元素，然后吞并左邊和右邊的元素。如此循環直到沒法產生吞并操作為止。

舉個例子，對于表達式"A+B*C-D"，則生成的表達式元素有

在第一次循環中，*號是優先級最高的，則進行收縮處理，處理后的結構如下：

上圖中黃色元素表示該元素收縮處理過了，不再參與處理。

在第二次循環中，"+"號優先級最高（后面的"-"和它是同等級的），則對它進行收縮，結果如下：

在第三次循環中，"-"號優先級最高，則進行收縮，結果如下：

之后根節點下再無可以處理的運算符元素，則退出循環。

經過上述步驟，最為關鍵的表達式元素樹狀列表產生出來了。

◆第四步，運行表達式

本功能的入口點在DCExpression.cs中的Eval()中，內部調用了根元素的Eval()，然后遞歸調用個子元素的Eval()，獲得最終的運算結果。

運算過程需要一個運行環境上下文對象，上下午對象只有2個功能：執行外界函數和取變量值。

為此定義了IDCExpressionContext接口，其代碼如下：

namespace DCSoft.Expression
{
    /// <summary>
    /// 表達式執行上下文對象
    /// </summary>
    [System.Runtime.InteropServices.ComVisible( false )]
    public interface IDCExpressionContext
    {
        /// <summary>
        /// 執行函數
        /// </summary>
        /// <param name="name">函數名</param>
        /// <param name="parameters">參數列表</param>
        /// <returns>函數返回值</returns>
        object ExecuteFunction(string name, object[] parameters);
        /// <summary>
        /// 獲得變量值
        /// </summary>
        /// <param name="name">變量名</param>
        /// <returns>變量值</returns>
        object GetVariableValue(string name);
    }
}

應用程序只需定義一個實現了該接口的類型即可傳遞給表達式執行引擎即可進行數值表達式運算了。

◆◆應用

這個表達式引擎完成后，開發者就能很方便的使用這個引擎了。首先是定義實現了IDCExpressionContext接口的上下文對象。其代碼如下：

private class MyContext : IDCExpressionContext
{
    public object ExecuteFunction(string name, object[] parameters)
    {
        name = name.ToUpper();
        try
        {
            switch (name)
            {
                case "SIN": return Math.Sin(Convert.ToDouble(parameters[0]));
                case "MAX":
                    return Math.Max(
                            Convert.ToDouble(parameters[0]),
                            Convert.ToDouble(parameters[1]));
                default:
                    MessageBox.Show("不支持的函數" + name);
                    return 0;
            }
        }
        catch (System.Exception ext)
        {
            MessageBox.Show("執行函數" + name + " 錯誤:" + ext.Message);
            return 0;
        }
    }

    public object GetVariableValue(string name)
    {
        name = name.ToUpper();
        switch( name )
        {
            case "A":return 1.5;
            case "B": return 2.3;
            case "C": return -99;
            case "D": return 998;
            case "E": return 123.5;
            case "F": return 3.1415;
            default:
                MessageBox.Show("不支持的參數名:" + name);
                return 0;
        }
    }
}

 在這個上下文中，定義了函數SIN和MAX的執行過程，并定義了變量A,B,C,D,E,F的具體的數值

然后我們可以使用以下代碼來調用表達式引擎了。

private void Form1_Load(object sender, EventArgs e)
{
    cboExpression.Items.Add("SIN(99+123)");
    cboExpression.Items.Add("A*99.1+MAX(-11,-10)");
    cboExpression.Items.Add("FIND('7048dcb034d94ce6bfd750c3f1672096',[zz])>=0");
    cboExpression.Items.Add("SUM(A1:B3)");
    cboExpression.Items.Add("[A1]-[B2]");
    cboExpression.Items.Add("A+B+C+在三+是+213");
    cboExpression.Items.Add("A+B*(C+D*(E-F))-999");
    cboExpression.Items.Add("-A+B+C+D");
    cboExpression.Items.Add("A+B*C-D");
    cboExpression.Items.Add("10+8>-9");
}
private void toolStripButton1_Click(object sender, EventArgs e)
{
    DCExpression exp = new DCExpression(cboExpression.Text);
    MyContext c = new MyContext();
    object vresult = exp.Eval(c);
    txtResult.Text = "運算結果:" + vresult;
}

如此這樣我們用2500行代碼實現了一個功能強大、性能卓越的數值表達式引擎?？蓮V泛用于各類軟件開發。

在筆者主導開發的電子病歷編輯器控件中就使用了這個數值表達式引擎來實現了類似EXCEL的公式運算功能，其界面如下：

在這個文檔中，我們設置右下角的單元格的數值表達式為"SUM([D3:D13])"，則用戶以下拉列表方式設置D3:D13區域的單元格內容時，軟件會調用DCSoft.Expression的功能，自動執行數值運算，并將運算結果顯示在右下角單元格中。

◆◆小結

在本文中使用了2500行C#代碼實現了一個結構清晰、易于理解和掌握、性能卓越的數值表達式運算引擎。支持四則數學運算、布爾邏輯運算、能調用外部函數和外部參數值。很容易實現一個類似EXCEL的公式運算引擎。

使用該引擎，能顯著提高軟件的自由度，讓軟件在運行階段即可自由改變運行模式，實現了軟件的高度的運行時可配置化。

中秋之夜編寫此文，詩性大發：玉宇無塵，朗月虛空三千里；架構有道，代碼奔騰百萬行。獻給紅塵中這百萬代碼人共勉。

◆◆關于作者

袁永福，80后，南京東南大學畢業，中國知名醫療信息技術專家，南京都昌信息科技有限公司（www.dcwriter.cn）的聯合創始人，微軟MVP，從事軟件研發近20年。長期從事電子病歷軟件底層技術的研發和推廣，對醫學病歷文檔技術有著深厚的積累。