c string 一个字符串内的多次替换

Question

假设我有一个字符串:

"(aaa and bbb or (aaa or aaa or bbb))"

**为简单起见，这将始终是字符串的格式，始终是 3 个 a 后跟一个空格或“)”或 3 个 b 后跟一个空格或“)”。

在 C 中用“1”替换每次出现的“aaa”以及用“0”替换每次出现的“bbb”的最佳方法是什么？结束字符串应如下所示:

"(1 and 0 or (1 or 1 or 0))"

编辑让我更具体一点:

char* blah = (char *) malloc (8);
sprintf(blah, "%s", "aaa bbb");

blah = replace(blah);

我如何编写replace以便它分配空间并存储一个新字符串

"1 0"

Answer 1

最有效的方法是使用 POSIX 正则表达式系列。某些实现将为模式构建适当的自动机。另一种方法是重复使用 KMP 或 Boyer-Moore 搜索，但你必须多次扫描字符串，效率较低。此外，给定这样的输入您想要什么结果:字符串“aabb”上的 aa=1、ab=2、bb=3？

顺便说一下，当你实现这个函数时，一个更干净的解决方案是分配一个新的动态 C 字符串，而不是在替换时修改原始字符串。您可以实现就地替换，但这会复杂得多。

regex_t r; regmatch_t match[2]; int last = 0;
regcomp(&r, "(aaa|bbb)", REG_EXTENDED);
insert(hashtable, "aaa", "0"); insert(hashtable, "bbb", "1");
while (regexec(&r, oristr, 1, match, 0) != REG_NOMATCH) {
  char *val;
  strncat(newstr, oristr + last, match->rm_so);
  lookup(hashtable, oristr + match->rm_so, match->rm_eo - match->rm_so, &val);
  last = match->rm_eo;
  strncat(newstr, val);
}
strcat(newstr, oristr + last);
oristr = realloc(oristr, strlen(newstr));
strcpy(oristr, newstr); free(newstr); regfree(&r);

在实际实现中，应该动态改变newstr的大小。您应该记录 newstr 的结尾而不是使用 strcat/strlen。源代码可能有问题，因为我还没有真正尝试过。但想法就在那里。这是我能想到的最有效的实现方式。