字符串替换
字符串替换
C++ string 中有⾃带的replace替换函数，其替换⽅式有以下⼏种：
（）
这⼏种⽅式都是只能针对某⼀个⽬标进⾏替换，不能对字符串中出现多次⽬标的情形进⾏全部替换。下⾯我们给出对字符串中所有⽬标进⾏替换的程序。
⼀、两种基本的全部替换⽅式
⽐如给定⼀⽬标字符串（以下参考⾃）：
12212
我们将其中的“12”替换为“21”，有两种替换⽅式，分别为：
1）进⾏distinct替换，即每次替换后，对替换后⾯的进⾏替换，不考虑替换后的字符序
列；
2）每次替换后，再进⾏下⼀步替换时，考虑之前替换的字符序列；
相应的两种替换⽅式替换后的结果分别为：
21221
22211
两种替换⽅式的程序分别为：
// 字符串的两种替换⽅式
#include <iostream>
#include <string>
using namespace std;
string& replace_all_distinct(string& str, const string& src, const string& des)
{
for (string::size_type i = 0; i != string::npos; i += des.size())
{
i = str.find(src, i);
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
string& replace_all_notdistinct(string& str, const string& src, const string& des)
{
for (string::size_type i = 0; ; )
{
i = str.find(src); // 从头开始查
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
int main()
{
string str("12212");
cout << replace_all_distinct(str, "12", "21") << endl;
str = "12212";
cout << replace_all_notdistinct(str, "12", "21") << endl;
system("PAUSE");
return0;
}
注意，第⼆种⽅式有可能造成死循环，⽐如对于12212，如果将12替换为212，那么将永远不会终⽌，因为对于12替换后的212，还会替换为2212、22212、222212……所以，对于这种替换⽅式，我们的原则是替换后的字符序列不能包含被替换的字符序列。
⼆、⼀点改进
接下来，我们做⼀点改进，就是指定替换的个数，我们设定⼀个参数，⽤来记录替换⽬标字符串的次数（参考⾃），这⾥我们可以按照从前到后的次序，也可以从后到前。具体程序如下：
/
/ 定量替换&逆向替换
#include <iostream>
#include <string>
using namespace std;
string& replace_all_distinct(string& str, const string& src, const string& des, int n)
{
int count = 0;
for (string::size_type i = 0, count = 0; i != string::npos && count < n; i += des.size(), ++count)
{
i = str.find(src, i);
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
string& r_replace_all_distinct(string& str, const string& src, const string& des, int n)
{
int count = 0;
for (string::size_type i = str.size()-1, count = 0; i != string::npos && count < n; --i, ++count)
{
i = str.rfind(src, i);
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
string& replace_all_notdistinct(string& str, const string& src, const string& des, int n)
{
int count = 0;
for (string::size_type i = 0, count = 0; count < n; ++count)
{
i = str.find(src); // 从头开始查
if (i != string::npos)
{
}
else
{
break;
}
字符串截取替换}
return str;
}
string& r_replace_all_notdistinct(string& str, const string& src, const string& des, int n)
{
int count = 0;
for (string::size_type i = str.size()-1, count = 0; count < n; ++count)
{
i = str.rfind(src); // 从尾开始查
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
int main()
{
string str("abababababab");
cout << replace_all_distinct(str, "ab", "xy", 3) << endl;
str = "aababababab";
cout << replace_all_notdistinct(str, "ab", "ba", 2) << endl;
str = "abababababab";
cout << r_replace_all_distinct(str, "ab", "xy", 3) << endl;
str = "ababababaab";
cout << r_replace_all_notdistinct(str, "ab", "ba", 2) << endl;
system("PAUSE");
return0;
}
三、批量替换
前⾯我们做的替换是对字符串中所有出现⽬标序列进⾏的替换，但是我们只是针对单⼀的⽬标序列。这⾥我们将对多个⽬标序列进⾏替换操作。我们默认多个⽬标序列之间不存在包含、被包含、相等等关系。
具体实现有以下两种⽅式：
1）针对每个待替换字符序列，顺序查并替换。假如查并替换依次的时间复杂度为
O(1)，那么这种⽅式的时间复杂度为：O(N*M)，其中N为待替换字符序列的个数，M为单个待替换序列出现的平均次数。
2）另⼀种⽅式是：顺序扫描⼀次字符串，查最早出现那个待替换字符序列的位置，
然后进⾏替换，这样针对每个出现的位置会查N*M*N次，替换N*M次，所以时
间复杂度为O(N*M*N)。
根据以上的分析，我们采⽤第⼀种替换⽅法：
// 逐个替换
#include <iostream>
#include <string>
#include <vector>
using namespace std;
string& replace_all_distinct(string& str, const string& src, const string& des)
{
for (string::size_type i = 0; i != string::npos; i += des.size())
{
i = str.find(src, i);
if (i != string::npos)
{
}
else
{
break;
}
}
return str;
}
string& n_replace(string& str, const vector<string>& src, const vector<string>& des)
{
assert(src.size() > 0 && src.size() == des.size());
for (vector<string>::size_type i = 0; i != src.size(); ++i)
{
replace_all_distinct(str, src[i], des[i]);
}
return str;
}
int main()
{
vector<string> src, des;
src.push_back("+");
src.push_back("-");
src.push_back("*");
src.push_back("/");
src.push_back("(");
src.push_back(")");
des.push_back(" + ");
des.push_back(" - ");
des.push_back(" * ");
des.push_back(" / ");
des.push_back(" ( ");
des.push_back(" ) ");
string str("1+2-3*4/5+(1/3)");
cout << n_replace(str, src, des) << endl;
system("PAUSE");
return0;
}
四、总结
以上我们对字符串两种基本的替换⽅式做了⼀些总结，并对其进⾏了⼀些改进，最后针对字符串做批量替换。
通过批量替换，我们将运⽤到后⾯的针对表达式的空⽩符预处理，以绕开词法分析。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。