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

どうしてこれなの？出力で関数を呼び出すことで問題を回避できます (つまり、文字列を 2 回実行します) が、それは明らかに「適切な」プログラミングではありません。ありがとう！

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). はるかに優れた解決策は、erase-removeイディオムを使用することです。

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

コンパイラがラムダをサポートしていない場合は、関数オブジェクト (ファンクタ) としてチェックを実装できます。このアルゴリズムはO(N)、削除されない要素が最終的な場所に 1 回だけコピーされるため、線形の複雑さを持ちます。

于 2012-10-05T01:25:41.420 に答える
0

すべての場合でインデックスをインクリメントしているため、失敗しています。削除すると、そのポイントを超えるすべての文字が1つ戻るため、文字を削除しない場合にのみこれを行う必要があります。

つまり、削除する連続する文字が 2 つ以上ある場合、この問題が発生します。両方を削除するのではなく、2 つを 1 つに「折りたたみ」ます。

関数を2回実行すると、その特定の入力文字列で機能しますが、最初の呼び出しで「((pax))」に折りたたまれるため、「((((pax))))」のような問題が発生します。 2番目は「（pax）」を提供します。

解決策の 1 つは、文字を削除するときにインデックスを進めないことです。

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 に答える