用正则表达式(regex)匹配多项式(polynomial)

2018-06-17 21:44:05来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

因为作业的要求,我需要识别用户从命令行输入的多项式,并且要提取出其中的系数、指数以便用于后续计算。

曾经想过用一个数组把用户所有的输入全部存进来,然后在写逻辑判断。但想想那复杂的逻辑,头皮都发麻,这时候因为有个朋友拜托我写个简单的小爬虫,写完后我灵机一动,爬虫用到的正则表达式不就是最好的处理手段么??(感谢同学,大雾)


 

言归正传。

首先先简单的讲一讲关于正则表达式的知识,这里就只关注那些我一会儿会用到的。

[ ] 方括号在这里被叫做原子表,它能够匹配括号中出现的任意一个元素

 

[abcd] //匹配abcd中任意一个字母
[!@#] // 匹配!@#中任意一个符号
[0-9] //匹配0,1,2,3,4,5,6,7,8,9中任意一个数字

三个常用的特殊符号: * + ?

    • * 星号可以匹配前面出现的元素0次,1次或任意多次
    • + 加号可以匹配前面出现的元素1次或任意多次
    • ? 问号可以匹配前面出现的元素0次或1次
ab* //匹配 a,ab,abb,abbb.......
ab+ //匹配 ab,abb,abbb,abbbb.......
ab? //匹配 a,ab

( ) 圆括号在这里被叫做模式单元符,他能够将一些元素组合成一个大的,不可分割的新元素,类似于括号在正常运算中的作用。

(ab*)? //匹配 空串 或 a,ab,abb,abbb.......
(ab+)? //匹配 空串 或 ab,abb,abbb,abbbb.......
(ab?)? //匹配 空串 或 a,ab

匹配任意字符:.(除换行符)

a.c  //匹配aac,abc,acc,adc.......

   转义符 : 如果想要匹配本身拥有特殊意义的符号,可以使用转移符\

\. // 匹配一个小数点

边界限制字符:^ $

  • ^ 匹配字符串的开始
  • $ 匹配字符串的结束
^a.* //匹配以a开头的字符串
.*a$ //匹配以a结尾的字符串

 


 

好了,现在可以回过头来看看我们要处理的问题了。

我们要处理的是类似这样的,由用户输入的字符串,用户很可能会输入一些空格,所以最稳妥的办法是用一个字符串存下一整行的输入信息,然后从中删去所有的空格和制表符。

x^2+x-3x^-1

如何匹配这样复杂的表达式呢??首先还是得拆分,一点点入手。

我们可以把一个完整的多项式拆成若干项

x^2
+x
-3x^-1

先看看如何匹配其中的一项吧

很明显,最先出现的是表示正负的符号,但也可以不出现

[+-]? //匹配加号,减号,或不出现符号

 然后就应该考虑匹配一个浮点数了,当然,如果系数为1,这个浮点数也可以不出现 所以最后可以用一个?表达可以不出现的意思。

[0-9]*\.?[0-9]+ //匹配一个浮点数
([0-9]*\.?[0-9]+)? //这个浮点数也可以不出现

 

然后考虑匹配指数位,当然,在指数为1的时候,也可以不出现,指数为0的时候,x也不用出现

\\^[+-]?[0-9]+ //匹配^1,^2,^3......
x(\\^[+-]?[0-9]+)? //匹配x^1,x^2,x^3...... 或者x (指数为1的情况)
(x(\\^[+-]?[0-9]+)?)? //允许匹配空串,用于指数为0的情况

 

好了,现在可以讲上述三个部分组合在一起了

[-+]?([0-9]*\.?[0-9]+)?(x(\\^[+-]?[0-9]+)?)? // 匹配 x^2,-3x^5,1,-x^-1......

 

还剩最后一点点就能完成了!!下面就是让这整个部分多次出现,用于匹配整个多项式,同时通过^匹配字符串的开头

^([-+]?([0-9]*\.?[0-9]+)?(x(\\^[+-]?[0-9]+)?)?)+$ //匹配整个多项式

 

emmmmm,好!如果你没有强迫症的话,大功告成了!

 

如果你有呢?

emmmmm,那就得再想想了。

在一个多项式中,符号,系数,指数不是必须全部出现的,但也不能全都不出现。反正一共只有23钟可能性,我们一样考虑一下就好了。(下面表格中星号代表这项出现)

符号 系数 指数 示例 是否可行 正则表达式
* * * -2x^2
[-+]([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?)
  * * 2x^2
([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?)
*   * -x^2
[-+](x(\\^[+-]?[0-9]+)?)
* *   -2
[-+]([0-9]*\.?[0-9]+)
*        
  *   3 ([0-9]*\.?[0-9]+)
    * x (x(\\^[+-]?[0-9]+)?)
         

发现有六种可行的情况,那就用笨办法依次匹配这六种情况呗。

然后把这六种打上括号,用 | 连接起来,就构成了修订后的用于匹配某一项的正则表达式。

([-+]([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?))|(([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?))|([-+](x(\\^[+-]?[0-9]+)?))|([-+]([0-9]*\.?[0-9]+))|(([0-9]*\.?[0-9]+))|((x(\\^[+-]?[0-9]+)?))

 

然后再像刚才一样 ,让这整个部分多次出现,用于匹配整个多项式,同时通过^匹配字符串的开头

^(([-+]([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?))|(([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9]+)?))|([-+](x(\\^[+-]?[0-9]+)?))|([-+]([0-9]*\.?[0-9]+))|(([0-9]*\.?[0-9]+))|((x(\\^[+-]?[0-9]+)?)))+$

 

接下来把代码实现方式摆出来,哦对了,要使用正则表达式的话,记得 #include <regex>

std::string poly = "x^2-x+3+x^-5";

std::string p1 = std::string("(") + "[-+]([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9])?)" + ")";

std::string p2 = std::string("(") + "([0-9]*\.?[0-9]+)(x(\\^[+-]?[0-9])?)" + ")";
std::string p3 = std::string("(") + "[-+](x(\\^[+-]?[0-9])?)" + ")";
std::string p4 = std::string("(") + "[-+]([0-9]*\.?[0-9]+)" + ")";
std::string p5 = std::string("(") + "([0-9]*\.?[0-9]+)" + ")";
std::string p6 = std::string("(") + "(x(\\^[+-]?[0-9])?)" + ")";
std::string p = p1 + "|" + p2 + "|" + p3 + "|" + p4 + "|" + p5 + "|" + p6;
std::string p_ = std::string("^(") + p + ")+$";
std::regex polyPattern(
p_);
if(!std::regex_match(poly,polyPattern)){
  std::cout
<<"invalid polynomial!"<<std::endl;
}

下面我要做的,就是把每一项中的系数和指数识别出来,然后分别转换成double和int类型的变量便于计算。

std::regex cofPattern("^[-+]?([0-9]*\.?[0-9]+)"); //匹配系数

 

 因为不能匹配 x, -x 这两种情况,所以在写代码的时候可以在适当判断一下

std::smatch cofResult;
double cof;
std::string term = "3x^5";
if( std::regex_search(term,cofResult,cofPattern) ){ const char* tempCof = cofResult.str().data(); //atof函数的参数是 const char* 类型的,我们需要转换一下 cof = std::atof(tempCof); // 将字符串转换成double类型数字 }else if(term[0] == '-') cof = -1; else cof = 1;

 

 下面是最后一步!提取指数

std::regex expPattern1("x\\^[+-]?[0-9]+$"); // 匹配指数

 但由于这样无法匹配指数为1的情况,所以我又写了个单独的正则表达式

std::regex expPattern2("x$"); // 匹配x在末尾
std::smatch expResult;
int exp;
if( std::regex_search(term,expResult,expPattern1) ){ const char* tempExp = expResult.str().substr(2).data(); exp = std::atoi(tempExp); }else if(std::regex_search(term,expResult,expPattern2)) exp = 1; else exp = 0;

 

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:洛谷P1607 [USACO09FEB]庙会班车Fair Shuttle

下一篇:cin、cin.get()、cin.getline()的区分