Posted on 2009-04-04 22:58
lzmagic 閱讀(3946)
評論(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;
}