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

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

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

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