0

我在 C++ 中编写了一个函数来从字符串中删除括号，但由于某种原因，它并不总是能全部捕获它们，我确信这真的很简单。

string sanitize(string word)
{
int i = 0;

while(i < word.size())
{
    if(word[i] == '(' || word[i] == ')')
    {
        word.erase(i,1);
    }
    i++;
}
return word;
}

样本结果：

输入：((3)8)8)8)8))7

输出：（38888）7

为什么是这样？我可以通过在输出上调用函数来解决这个问题（因此将字符串运行两次），但这显然不是“好的”编程。谢谢！

4

4 回答 4

11 
if(word[i] == '(' || word[i] == ')')
{
    word.erase(i,1);
}
i++;

如果你删除一个括号，下一个字符会移动到先前被括号占用的索引，所以它不会被检查。使用else.

if(word[i] == '(' || word[i] == ')')
{
    word.erase(i,1);
} else {
    i++;
}
于 2012-10-05T00:03:16.433 回答
4 
while(i < word.size())
{
    if(word[i] == '(' || word[i] == ')')
    {
        word.erase(i,1);
    }
    i++;
}

当您删除一个元素时，下一个元素将移动到该位置。如果你想测试它，你将不得不避免增加计数器：

while (i < word.size()) {
   if (word[i] == '(' || word[i] == ')' ) {
      word.erase(i,1);
   } else {
      ++i;
   }
}

这也可以使用迭代器来完成，但任何一个选项都不好。对于字符串中的每个括号，它后面的所有元素都将被复制，这意味着您的函数具有二次复杂度：O(N^2). 一个更好的解决方案是使用擦除删除成语：

s.erase( std::remove_if(s.begin(), s.end(), 
                        [](char ch){ return ch==`(` || ch ==`)`; })
         s.end() );

如果您的编译器不支持 lambda，您可以将检查实现为函数对象（函子）。该算法具有线性复杂性O(N)，因为未删除的元素仅复制一次到最终位置。

于 2012-10-05T01:25:41.420 回答
0

它失败了，因为您在所有情况下都增加了索引。仅当您不删除字符时才应该这样做，因为删除会将超出该点的所有字符向后移动一个。

换句话说，只要有两个或多个连续字符要删除，就会出现这个问题。它不是将它们都删除，而是将它们“折叠”成一个。

通过你的函数运行它两次将在那个特定的输入字符串上工作，但你仍然会遇到像“(((((pax))))”这样的问题，因为第一次调用会将它折叠为“((pax))”第二个会给你“（pax）”。

一种解决方案是在删除字符时不推进索引：

std::string sanitize (std::string word) {
    int i = 0;

    while (i < word.size()) {
        if(word[i] == '(' || word[i] == ')') {
            word.erase(i,1);
            continue;
        }
        i++;
    }
    return word;
}

但是，我会更智能地使用该语言的功能。C++ 字符串已经具有搜索字符选择的能力，这可能比用户循环优化得多。因此，您可以使用更简单的方法：

std::string sanitize (std::string word) {
    int spos = 0;

    while ((spos = word.find_first_of ("()", spos)) != std::string::npos)
            word.erase (spos, 1);
    return word;
}

您可以在以下完整程序中看到这一点：

#include <iostream>
#include <string>

std::string sanitize (std::string word) {
    int i = 0;

    while ((i = word.find_first_of ("()", i)) != std::string::npos)
            word.erase (i, 1);
    return word;
}

int main (void) {
    std::string s = "((3)8)8)8)8))7 ((((pax))))";
    s = sanitize (s);
    std::cout << s << '\n';
    return 0;
}

输出：

388887 pax
于 2012-10-05T00:28:25.153 回答
-2

为什么不只使用 strtok 和一个临时字符串？

string sanitize(string word)
{
int i = 0;
 string rVal;
 char * temp;
strtok(word.c_str(), "()"); //I make the assumption that your values should always start with a (
do
{
   temp = strtok(0, "()");
   if(temp == 0)
   {
       break;
   }
   else { rVal += temp;}
}while(1);

return rVal;
}
于 2012-10-05T00:01:46.930 回答