Posted on 2009-04-04 22:58
lzmagic 阅读(3832)
评论(3) 编辑 收藏 引用 所属分类:
Algorithm
/**//**
* IS_MATCHED
* 输入：(1)一个正则表达式：带有正则符号'*'、'+'、'?'、'.'(正则符号不相邻)；
* '*'：任意多个任意字符；
* '+'：至少1个任意字符；
* '?'：0个或1个任意字符；
* '.'：恰好1个任意字符。
* (2)一个字符串。
* 输出：该正则表达式是否匹配该字符。
*/
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool Is_Matched(string ®, string &str)
{
bool is_asterisk, is_plus, is_question, is_dot, is_ok(true);
string substr;
string::iterator reg_it(reg.begin()), str_it(str.begin()), str_it2;
while (is_ok && reg_it != reg.end())
{
// 分离正则符号给is_asterisk、is_plus、is_question、is_dot。
is_asterisk = *reg_it == '*';
is_plus = *reg_it == '+';
is_question = *reg_it == '?';
is_dot = *reg_it == '.';
if ( is_asterisk || is_plus || is_question || is_dot) ++reg_it;
// 分离子字符串给substr。
substr.clear();
for (reg_it = reg_it; reg_it != reg.end()
&& *reg_it != '*'
&& *reg_it != '+'
&& *reg_it != '?'
&& *reg_it != '.'; ++reg_it)// 调整reg_it。
substr.push_back(*reg_it);
// 匹配子字符串：substr空，str_it2=>end()，否则str_it2=>匹配点或end()。
if (substr.empty()) str_it2 = str.end();
else str_it2 = search(str_it, str.end(), substr.begin(), substr.end());
// 是否匹配正则符号：is_asterisk不做判断。
if (is_plus && str_it == str_it2
|| is_question && str_it != str_it2 && str_it != str_it2 - 1
|| is_dot && str_it != str_it2 - 1) is_ok = false;
// 是否匹配子字符串。
if (!substr.empty() && str_it2 == str.end()) is_ok = false;
else str_it = str_it2 + substr.size(); // 调整str_it。
}
// 匹配成功：is_ok为true，reg_it到达reg.end()，str_it到达str.end()。
return is_ok && reg_it == reg.end() && str_it == str.end();
}
int main ()
{
string reg, str; // input : *l?m.g+ lzmagic ?zm lzmagic
while (cin >> reg >> str)
{
if (Is_Matched(reg, str)) cout << "match" << endl;
else cout << "dismatch" << endl;
}
system("pause");
return 0;
}