6

つまり、基本的には、次のような文字列があるかもしれません。

ただし、この文字列は巨大になる可能性があります。アスタリスクが乗算を表しているように見えない限り、文字列からすべてのアスタリスクを削除しようとしています。ここでは効率がいくぶん重要であり、ここから乗算以外のすべてのアスタリスクを削除するための優れたアルゴリズムを考え出すのに苦労しています。

アスタリスクが乗算用かどうかを判断するには、アスタリスクが 2 つの数値の間に挟まれているかどうかを確認するだけです。

したがって、（疑似コード）のようなことができると思っていました：

wasNumber = false
Loop through string
   if number 
      set wasNumber = true
   else
      set wasNumber = false
   if asterisk
      if wasNumber
         if the next word is a number
            do nothing
         else
            remove asterisk
      else
         remove asterisk

ただし、それは巨大な文字列では見苦しく非効率的です。C++ でこれを達成するためのより良い方法を考えられますか?

また、単語が数字であるかどうかを実際に確認するにはどうすればよいですか? 10 進数を指定できます。文字が数字かどうかをチェックする関数があることを知っています...

4

4 に答える 4

4

完全に機能するコード:

#include <iostream>
#include <string>
using namespace std;

string RemoveAllAstericks(string);
void RemoveSingleAsterick(string&, int);
bool IsDigit(char);

int main()
{
    string myString = "hey this is a string * this string is awesome 97 * 3 = 27 * this string is cool";
    string newString = RemoveAllAstericks(myString);

    cout << "Original: " << myString << "\n";
    cout << "Modified: " << newString << endl;

    system("pause");
    return 0;
}

string RemoveAllAstericks(string s)
{
    int len = s.size();
    int pos;

    for(int i = 0; i < len; i++)
    {
       if(s[i] != '*') 
          continue;

       pos = i - 1;
       char cBefore = s[pos];
       while(cBefore == ' ')
       {
          pos--;
          cBefore = s[pos];
       }

       pos = i + 1;
       char cAfter  = s[pos];
       while(cAfter == ' ')
       {
          pos++;
          cAfter = s[pos];
       }

       if( IsDigit(cBefore) && IsDigit(cAfter) )
          RemoveSingleAsterick(s, i);
    }

    return s;
}

void RemoveSingleAsterick(string& s, int i)
{
    s[i] = ' '; // Replaces * with a space, but you can do whatever you want
}

bool IsDigit(char c)
{
   return (c <= 57 && c >= 48);
}

トップレベルの概要:

コードは、*. 次に、 の前後の AND の前にある最初の非空白文字を調べます*。両方の文字が数値の場合、コードはこれが乗算演算であると判断し、アスタリックを削除します。それ以外の場合は無視されます。

他の詳細が必要な場合は、この投稿の改訂履歴を参照してください。

重要事項:

  • 文字列に境界チェックを追加することを真剣に検討する必要があります (つまり、より小さい0または大きいインデックスにアクセスしようとしないでください)。len
  • 括弧が気になる場合は、空白をチェックする条件を括弧もチェックするように変更します。
  • すべての文字が数字であるかどうかを確認するのは悪い考えです。少なくとも、2 つの論理チェックが必要です (IsDigit()関数を参照してください)。(私のコードは '*' をチェックしますが、これは論理演算の 1 つです。) しかし、投稿された提案のいくつかはよく考えられていませんでした。文字が数値かどうかを確認するために正規表現を使用しないでください。

質問で効率について言及したため、他の回答についてコメントするのに十分な担当者がいません。

'0' '1' '2' ... をチェックする switch ステートメントは、数字ではないすべての文字が 10 回の論理演算を実行する必要があることを意味します。sはs にマップされるため、境界を確認してください。charint(char <= '9' && char >= '0')

于 2011-07-28T18:45:40.027 に答える
3

遅いバージョンを実装することから始めることができます。それはあなたが思っているよりもずっと速いかもしれません。しかし、遅すぎるとしましょう。次に、最適化問題です。非効率性はどこにあるのでしょうか。

  • 「数字の場合」は簡単です。正規表現または数字ではないものを見つけたときに停止するものを使用できます
  • 「次の単語が数字の場合」は、効率的に実装するのと同じくらい簡単です。

さて、あなたにとって問題なのは「アスタリスクを削除する」部分です。ここで注目すべき重要な点は、文字列を複製する必要がないことです。要素を削除するだけなので、実際にはその場で変更できます。

実装を試みる前に、これを視覚的に実行してみてください。

2 つの整数または反復子を保持します。1 つ目は現在文字列を読み取っている場所を示し、2 つ目は現在文字列を書き込んでいる場所を示します。内容を消去するだけなので、読み取りは常に書き込みよりも先になります。

現在の文字列を保持する場合は、整数/イテレータを 1 つずつ進め、それに応じてコピーするだけです。残しておきたくない場合は、読みの文字列を進めるだけです！次に、削除したアスタリスクの分だけ文字列をカットするだけです。複雑さは単純に O(n) であり、追加のバッファーは使用されません。

また、次のように記述した場合、アルゴリズムはより単純になります (ただし同等) ことに注意してください。

wasNumber = false
Loop through string
   if number 
      set wasNumber = true
   else
      set wasNumber = false
      if asterisk and wasNumber and next word is a number
          do nothing // using my algorithm, "do nothing" actually copies what you intend to keep
      else
          remove asterisk
于 2011-07-28T16:59:12.043 に答える
3

私はあなたの小さな問題が興味深いと思い、std::string. ここに行きます：

// TestStringsCpp.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <string>
#include <iostream>

using namespace std;

string& ClearAsterisk(string& iString)
{
    bool bLastCharNumeric = false;
    string lString = "0123456789";

    for (string::iterator it = iString.begin(); it != iString.end() ; ++it) {
        switch (*it) {
        case ' ':   break;//ignore whitespace characters
        case '*':
            if (bLastCharNumeric) {
                //asterisk is preceded by numeric character. we have to check if
                //the following non space character is numeric also
                for (string::iterator it2 = it + 1; it2 != iString.end() ; ++it2) {
                    if (*it2 != ' ') {
                        if (*it2 <= '9' && *it2 >= '0') break;
                        else iString.erase(it);
                        break;  //exit current for
                    }
                }
            }
            else iString.erase(it);;
            break;

        default:
            if (*it <= '9' && *it >= '0') bLastCharNumeric= true;
            else bLastCharNumeric = false;  //reset flag
        }
    }
    return iString;
}

int _tmain(int argc, _TCHAR* argv[])
{
    string testString = "hey this is a string * this string is awesome 97 * 3 = 27 * this string is cool";

    cout<<ClearAsterisk(testString).c_str();
    cin >> testString;  //this is just for the app to pause a bit :)

    return 0;
}

サンプル文字列では完全に機能しますが、次のようなテキストがある場合は失敗します"this is a happy 5 * 3day menu"。「*」の後の最初の非スペース文字のみをチェックするためです。しかし、率直に言って、文の中にこの種の構文が含まれる多くのケースを想像することはできません.

HTH、
JP。

于 2011-07-28T18:45:58.060 に答える
0

正規表現は必ずしも効率的であるとは限りませんが、文字列の解析と操作を他の誰かに任せることができます。

個人的には、効率が気になる場合は、不必要なメモリ割り当てを制限しながら、疑似コード バージョンを実装します。mmap入力ファイルでも構いません。私はあなたがそれよりもずっと速くなることを非常に疑っています。

于 2011-07-28T17:22:07.850 に答える