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

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

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

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