正则表达式在优化计算中的应用

正则表达式在优化计算中的应用

正则表达式在优化计算中的应用

摘要：在编写优化算法软件时，用户输入的表达式通常是字符串类型,如何实现用户与计算机

的交互，即怎样让计算机读懂用户输入的字符串类型的数学表达式,是计算机优化计算所要面临的首要问题。在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，在实现表达式求值、求导的基础上完成对用户输入函数的求解极值。在交互界面上，用户需要输入函数表达式，以及表达式中所包含的变量和变量的初始值大小。程序的对象模型。

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

只含数字项表达式的计算CNumericalCalculation用来对替换后只包含数字项的函数表达

式进行运算，包括基本的四则运算以及幂函数运算。在CFunctionCaluclate中通过实例化一个CNumericalCalculation的对象m_Calcution来调用它的计算函数。按照运算的优先级，调用的顺序依次为幂函数运算、乘除函数运算、加减函数运算。CNumericalCalculation类中

有私有函数CString Genral_Calculation(CString expression,MODEL calculation_model)，Genral_Calculation()的程序流图。

在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中使用正则表达式,成功地实现了对字符串类型的函数表达式的读入，为用户提供了良好的交互接口，用户只需输入目标函数、

约束条件、自变量、初始点就可以求得最优解和此时的函数值。并能对用户的输入进行检查，在用户输入错误时给出提醒。同时，正则表达式的使用不仅仅针对优化程序，其他程序在面对表达式的数值计算时，同样会遇到如何理解用户输入字符串类型表达式的困难，本文中的方法可以用来解决此类问题。本文中所用方法的缺点是，使用正则表达式理解用户输入表达式，会随着表达式的复杂度增加，运算时间也会随之增长，在使用某些优化算法时，需要计算比较复杂的算式，会使问题的规划时间变得较长。