摘  要： 在編寫優(yōu)化算法軟件時，用戶輸入的表達式通常是字符串類型,如何實現(xiàn)用戶與計算機的交互,，即怎樣讓計算機讀懂用戶輸入的字符串類型的數(shù)學表達式,是計算機優(yōu)化計算所要面臨的首要問題,。在VS中調(diào)用DEELX正則語言庫,采用匹配、替換的方法實現(xiàn)對用戶輸入函數(shù)表達式的判別,、計算,，并在實現(xiàn)計算表達式的基礎(chǔ)上計算表達式導數(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ù)字項的表達式進行基礎(chǔ)運算，包括基本的四則運算以及冪函數(shù)運算。COptimize通過實例化CFunctionCaluclate,，在實現(xiàn)表達式求值,、求導的基礎(chǔ)上完成對用戶輸入函數(shù)的求解極值。在交互界面上,，用戶需要輸入函數(shù)表達式,，以及表達式中所包含的變量和變量的初始值大小。程序的對象模型如圖1所示,。

2 正則表達式運用于函數(shù)表達式的計算
　正則表達式在很多文本編輯器或其他工具里,，用來檢索和替換符合某個模式的文本內(nèi)容，目前許多程序設(shè)計語言都支持利用正則表達式進行字符串操作[3],。由于用戶輸入的目標函數(shù)和約束條件都是字符串類型的,，所以正則表達式可以應(yīng)用于函數(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中的元素作為正則表達式,，將其進行匹配并替換為相應(yīng)的給定值，這時函數(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類型來確定采用哪種計算類型,，并選取其對應(yīng)的正則表達式來匹配子運算塊,。
    通過公共函數(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ù)字應(yīng)該被看作是一個分數(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ù)器不為零,，則說明左右括號數(shù)量不同,，肯定含有不完整的括號對，表達式存在非法的括號使用,。
    有關(guān)用戶輸入自變量的錯誤,，第一種是自變量個數(shù)與對應(yīng)的給定值個數(shù)不符，例如自變量有“a,、b,、c” ,，而給定值為“1、2”或“1,、2、3,、4” ,，都無法進行正確的替換，這種錯誤較為容易檢測,，只要在獲取了自變量和給定值以后,，比較兩個容器中的元素個數(shù)，若不相等則說明自變量個數(shù)與對應(yīng)的給定值個數(shù)不符,。第二種是函數(shù)表達式中的變量,，在自變量輸入欄用戶沒有給出相應(yīng)的變量，例如函數(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ù)庫查詢中的應(yīng)用[J]．計算機工程與設(shè)計,，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].