摘  要： 在編寫優化算法軟件時，用戶輸入的表達式通常是字符串類型,如何實現用戶與計算機的交互，即怎樣讓計算機讀懂用戶輸入的字符串類型的數學表達式,是計算機優化計算所要面臨的首要問題。在VS中調用DEELX正則語言庫,采用匹配、替換的方法實現對用戶輸入函數表達式的判別、計算，并在實現計算表達式的基礎上計算表達式導數和求解極值。
關鍵詞： 正則表達式； 優化算法軟件； DEELX

    傳統的優化程序一般都是針對某個具體的待優化問題進行編寫的，缺乏通用性，用戶還需要花費一段時間來學習如何使用軟件。優化軟件若具有良好的交互性，用戶只需要輸入目標函數、約束條件、自變量、初始點就可以求得最優解和此時的函數值。要實現對用戶輸入問題的求解，首先面對的問題就是如何讓計算機讀懂用戶所輸入的待求解問題。由于用戶所輸入的目標函數、約束條件、自變量都是字符串類型的，所以要通過對字符串進行處理來實現計算機對函數表達式的理解。而正則表達式通常用檢索和替換那些符合某個模式的文本內容，本文采用正則表達式進行字符串的匹配、替換來實現計算機對用戶輸入表達式的讀入[1-2]。
1 優化程序結構
    用戶通過一個問題輸入對話框與計算機進行交互，在對話框中用戶需要輸入待優化問題的目標函數，約束條件，計算精度等參數，點擊求解按鈕進行運算。若用戶有非法輸入則提示用戶重新輸入，如果求解失敗則彈出求解失敗對話框。例如用戶需要求解問題min f (t,s)=0.5t2+s2/4，s.t ts=1，則需要在目標函數欄輸入0.5*t^2+s^2/4,在約束條件欄輸入t*s-1=0。
     程序主要由COptimize、CFunctionCaluclate、CNumericalCaluclate三個類構成。CFunctionCaluclate用于實現對用戶輸入表達式的校驗，將表達式中的變量替換為數值并計算結果，獲取表達式在指定點的一、二階導數等功能。CNumericalCalculation用于實現對替換后只包含數字項的表達式進行基礎運算，包括基本的四則運算以及冪函數運算。COptimize通過實例化CFunctionCaluclate，在實現表達式求值、求導的基礎上完成對用戶輸入函數的求解極值。在交互界面上，用戶需要輸入函數表達式，以及表達式中所包含的變量和變量的初始值大小。程序的對象模型如圖1所示。

2 正則表達式運用于函數表達式的計算
　正則表達式在很多文本編輯器或其他工具里，用來檢索和替換符合某個模式的文本內容，目前許多程序設計語言都支持利用正則表達式進行字符串操作[3]。由于用戶輸入的目標函數和約束條件都是字符串類型的，所以正則表達式可以應用于函數表達式的計算。
     DEELX 是一個在C++環境下的正則表達式引擎[4]，全部采用模板 template 編寫,可將 DEELX 用于char、 wchar_t 以及其他基類型，比如unsigned char、int等。但只能是簡單數據類型，不可以是 struct 或者 union 等復合類型。DEELX全部代碼位于一個頭文件（deelx.h）中，使用時只需要簡單地添加一個 #include"deelx.h"就可以了。
    在本文中，采用匹配、替換的方法實現對用戶輸入函數表達式的判別、計算。首先，用給定初始點的值對自變量進行替換，將函數表達式變為只含有數字項的數學表達式，再通過正則語言的匹配將數學表達式劃分為各個子運算塊,然后將計算結果代替原表達式中的子運算塊,如此循環,直到最后只剩下一個數字，即為計算結果。
2.1 自變量的替換
     在CFunctionCaluclate中添加兩個公有函數Capture_Variables( ):void和Capture_GivenPoints( ):void，分別用來獲取自變量和給定值，并將捕獲到的自變量和給定值分別放入兩個vector<const char*>類型的成員變量m_vecVariables和m_vecValues中。
    首先將儲存自變量的m_vecVariables中的元素作為正則表達式，將其進行匹配并替換為相應的給定值，這時函數表達式已變成只含有數字項的數學表達式。變量替換的流程圖如圖2所示。
2.2 只含數字項表達式的計算
　  CNumericalCalculation用來對替換后只包含數字項的函數表達式進行運算，包括基本的四則運算以及冪函數運算。在CFunctionCaluclate中通過實例化一個CNumericalCalculation的對象m_Calcution來調用它的計算函數。按照運算的優先級，調用的順序依次為冪函數運算、乘除函數運算、加減函數運算。
    CNumericalCalculation類中有私有函數CString Genral_Calculation( CString expression, MODEL calculation_model )，Genral_Calculation( ) 的程序流圖如圖3所示。

    在CNumericalCalculation中已經定義了針對不同函數計算的正則表達式，Power、Multi_Divid、Plus、Minus是在Genral_Calculation( )中枚舉的類型為 MODEL的變量，通過不同的MODEL類型來確定采用哪種計算類型，并選取其對應的正則表達式來匹配子運算塊。
    通過公共函數CString My_pow(CString fun_expression)、
CString My_multi_divid(CString fun_expression)、CString My_
plus_minus( CString fun_expression)來實現基本的冪函數、乘除、加減計算，并為CNumericalCalculation提供外部接口。
    例如，My_pow( ) 實現對冪函數的計算，它的實現代碼為：
    CString CNumericalCalculate::My_pow(CString fun_expression)
　　    {
        fun_expression = \
        Genral_Calculation(fun_expression,Power);
        return fun_expression;
　　}
    My_pow( )被傳進來的參數 fun_expression為只含數字項的表達式，在Genral_Calculation( )中通過參數Power來確定為冪函數計算。
   My_multi_divid ( ) 實現對乘除函數的計算，它的實現代碼與冪函數一樣，只是在調用Genral_Calculation( )時確定計算類型的參數為Multi_Divid。
    My_plus_minus( ) 實現對加減函數的計算，在調用Genral_Calculation( )前要對此時的表達式進行符號的合并，原因是由于加減運算的優先級別最低，在進行加減運算時表達式只包含“+”、“-”兩種符號，所以需要進行符號的合并。Sign_Combination( )用來對表達式中的符號進行合并，將“++”、“--”合并為“+”，“+-”、“-+”合并為“-”。
2.3 運算優先級問題
    為了實現乘除運算從左至右的順序，必須先進行除法運算，否則會產生錯誤，例如：
    4/2*2，從左至右的運算順序會得到4，若先進行乘運算，則變成4/(2*2)，此時得到的結果為1。這是因為在運算過程中，被“/”所連接的兩個數字應該被看作是一個分數整體，先做除法只是求出了分數的有理型式，所以先進行除法運算不會改變運算結果。
    這里將乘除法合并在一起，在從左至右的匹配過程中，匹配到乘函數就用乘法運算，遇到除函數就用除法運算，這樣就實現了從左至右的運算順序。
    若將乘除法運算分開，先做所有的除法運算，再做所有的乘法運算也會得到正確的結果，但這為程序調試添加了潛在的危險，若不小心顛倒乘除運算順序，這個錯誤將會很難發現。
2.4 匹配子算式的正則表達式
    上文說明了程序計算函數表達式的原理及大致的實現方法，但如何實現對不同的運算法則進行匹配，是使用正則表達式最復雜的地方。
    由于在用初始點替換變量之后會出現“+-”、“++”、“- -”等符號，所以簡單的正則表達式不能實現完全正確的匹配。例如：
    -X1^2 +X2-X3-X4，若此時X1=2，X2=-3，X3=4，X4=-5，那么此時的表達式為：
    -2^2+-3-4--5，用簡單的匹配表達式“[+-]\d+\.?\d*”來匹配，用括號表示被匹配項，那么被捕獲到的數字項為(-2)^(2)+(-3)(-4)-(-5)，很明顯，捕獲結果有錯，首先第一項是-(2)^(2)，前面的符號也進行了冪運算；還有第三項(-4)，運算符號被捕獲為負號。顯然，這種簡單的匹配表達式還會帶來更多的錯誤匹配。
    在本文中，先對用戶輸入的初始點進行判斷，若是負數則直接替換變量，若是正數，則在數字前添加“+” ，這樣就能解決表達式首變量前面為負號的情況，例如此時給2添加“+”號，就能獲得正確的捕獲結果-(+2)^(2)。
　    先使用如下正則表達式來匹配數字項：
    (?<=[\^\-+*/])[+\-]\d+\.?\d*|^[+-]\d+\.?\d*|\d+\.?\d*
　    這是由三個匹配規則用分枝條件組成的正則表達式。
    (?<=[\^\-+*/])[+\-]\d+\.?\d*來捕獲運算符號后面帶正負號的數字,如“-2^2+-3-4--5”中的“-3”“-5”；
    ^[+-]\d+\.?\d*來捕獲表達式開頭帶正負號的數字,
如“ –2^2 + -3-4--5”中的“-2”；
　    \d+\.?\d*來捕獲表達式中不帶正號的正數,如“-2^2 + -3-4--5”中的“2”。
    通過正則表達式的簡化，前兩種匹配規則合并后得到：
　    ((?<=[\^\-+*/]|^)[+\-]\d+\.?\d*)|(\d+\.?\d*)
　    再次合并兩種規則得到：
　    ((?<=[\^\-+*/]|^)[+\-])?\d+\.?\d*
　    對于以空格開頭的數字，加上\s進行匹配，最終匹配數字的正則表達式為：
　    ((?<=[\^\s\-+*/]|^)[+\-])?\d+\.?\d*
　    在實現了數字項的匹配后，可以很容易地獲取匹配冪函數的正則表達式，即在兩個數字中間插入冪函數計算符號：
    (((?<=[\^\s\-+*/]|^)[+\-])?\d+\.?\d*)\s*\^\s*(?1)
    匹配乘除、加減函數的正則表達式與冪函數相似，都是在數字項之間加入運算符號來匹配子算式。
2.5 對含有括號項的處理
    匹配括號項的正則表達式為：\([^()]*\)。
　    其含義為以“(”開頭，“)”結尾且不包含“( )”項的字符串。對含有括號的表達式，先匹配括號內的表達式，并調用Calculate( )函數來計算其結果，再用計算結果來代替所匹配到的括號項。如此循環，直到括號項不存在。然后計算無括號的表達式，得到最終的計算結果。
3 正則表達式用于表達式的錯誤檢查
    用戶在輸入表達式時，難免會輸入一些錯誤的數學表達式，比如在數字中出現多個小數點、括號的錯誤使用、變量個數與給定的初始值個數不符、初始值非純數字、所給變量與函數表達式中的不符等，都可以通過建立相關的正則表達式來進行錯誤匹配，當匹配成功后就提示用戶輸入錯誤,幫助用戶輸入正確的表達式與參數。
    CFunctionCaluclate中的Error_Identify( )用來檢測用戶輸入的函數表達式、自變量、給定值是否含有錯誤。
     通常與小數點相關的錯誤是數字項中含有多個小數點，如“2..5”和“2.3.4”都是非法輸入，通過正則表達式來匹配數字項中的多個小數點，若匹配成功，則說明存在小數點非法輸入。
     括號的非法使用通常包含兩種情況，一是函數表達式開頭有右括號或結尾有左括號，例如“a+)6*b-c”和“a-b^2+(c-d”都是第一種錯誤類型；二是左括號與右括號的數量不相等，即含有不完整的括號對，例如“a*(b-c*(2-d)”式中未能構成一個完整的括號對。
    針對以上兩種錯誤類型，采用不同的判別方法。對于第一種錯誤類型，用正則表達式“^[^(]*\)|\([^)]*$”來匹配表達式開頭的“)”或結尾的“(”，若匹配成功，則說明函數表達式有非法的括號使用；對于第二種錯誤類型，先設置一個計數器并初始為零，若匹配到一個左括號則計數器加一，匹配到右括號計數器減一，如果最后計數器不為零，則說明左右括號數量不同，肯定含有不完整的括號對，表達式存在非法的括號使用。
    有關用戶輸入自變量的錯誤，第一種是自變量個數與對應的給定值個數不符，例如自變量有“a、b、c” ，而給定值為“1、2”或“1、2、3、4” ，都無法進行正確的替換，這種錯誤較為容易檢測，只要在獲取了自變量和給定值以后，比較兩個容器中的元素個數，若不相等則說明自變量個數與對應的給定值個數不符。第二種是函數表達式中的變量，在自變量輸入欄用戶沒有給出相應的變量，例如函數表達式為“a*(b-c*(2-d))” ，而用戶只給出了“a、b、c”的給定值，“d”是一個未知變量，對于這種錯誤，要先對函數表達式進行自變量的捕獲，并將其放入一個vector中，再與用戶所給的自變量進行匹配，若有自變量沒能匹配成功，則說明含有未知的自變量，這時需要提示用戶輸入錯誤。
    通過在VS中使用正則表達式,成功地實現了對字符串類型的函數表達式的讀入，為用戶提供了良好的交互接口，用戶只需輸入目標函數、約束條件、自變量、初始點就可以求得最優解和此時的函數值。并能對用戶的輸入進行檢查，在用戶輸入錯誤時給出提醒。
    同時，正則表達式的使用不僅僅針對優化程序，其他程序在面對表達式的數值計算時，同樣會遇到如何理解用戶輸入字符串類型表達式的困難，本文中的方法可以用來解決此類問題。
    本文中所用方法的缺點是，使用正則表達式理解用戶輸入表達式，會隨著表達式的復雜度增加，運算時間也會隨之增長，在使用某些優化算法時，需要計算比較復雜的算式，會使問題的規劃時間變得較長。
參考文獻
[1] 翟自洋，林昌東．利用正則表達式進行查找/替換[J]．中國科技期刊研究，2009，20(1):122-126．
[2] 曹光琦．Boost.Regex_C++正則表達式快速入門[J]． 程序員，2004(04):78-81．
[3] 李旻，陳和平．正則表達式在數據庫查詢中的應用[J]．計算機工程與設計，2006，27(12)：2302-2305．
[4] DEELX正則引擎文檔[CP/OL]．(2006-09-20)[2011-04-25].http://www.regexlab.com/zh/regref.htm，2006，9．[2011,4].