C++-Funktion zum Zählen aller Wörter in einer Zeichenfolge

Ich wurde das während eines Interviews gefragt und anscheinend ist es eine einfache Frage, aber es war und ist für mich nicht offensichtlich.

Zählen Sie in einer gegebenen Zeichenfolge alle Wörter darin. Es spielt keine Rolle, ob sie wiederholt werden. Nur die Gesamtzahl wie in einer Textdatei Wortzahl. Wörter sind alles, was durch ein Leerzeichen getrennt ist, und Satzzeichen spielen keine Rolle, solange sie Teil eines Wortes sind.

Zum Beispiel:
A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Mein “Algorithmus” sucht einfach nach Leerzeichen und erhöht einen Zähler, bis ich eine Null erreiche. Da ich den Job nicht bekommen habe und danach gebeten wurde zu gehen, schätze ich, dass meine Lösung nicht gut war? Hat jemand eine cleverere Lösung? Übersehe ich etwas?

Angenommen, Wörter sind durch Leerzeichen getrennt:

unsigned int countWordsInString(std::string const& str)
{
    std::stringstream stream(str);
    return std::distance(std::istream_iterator<std::string>(stream), std::istream_iterator<std::string>());
}

Hinweis: Zwischen Wörtern kann mehr als ein Leerzeichen stehen. Auch andere Leerzeichen wie Tabulator für neue Zeile oder Wagenrücklauf werden nicht erfasst. Das Zählen von Leerzeichen reicht also nicht aus.

Der Stream-Eingabeoperator >>, wenn er zum Lesen einer Zeichenfolge aus einem Stream verwendet wird. Liest ein durch Leerzeichen getrenntes Wort. Also haben sie wahrscheinlich nach Ihnen gesucht, um dies zu verwenden, um Wörter zu identifizieren.

std::stringstream  stream(str);
std::string        oneWord;

stream >> oneWord; // Reads one space separated word.

When kann dies verwenden, um Wörter in einer Zeichenfolge zu zählen.

std::stringstream  stream(str);
std::string        oneWord;
unsigned int       count = 0;

while(stream >> oneWord) { ++count;}
// count now has the number of words in the string.

Kompliziert werden:
Streams können wie jeder andere Container behandelt werden und es gibt Iteratoren, die sie durchlaufen std::istream_iterator. Wenn Sie den ++-Operator für einen istream_iterator verwenden, liest er einfach den nächsten Wert aus dem Stream mit dem Operator >>. In diesem Fall lesen wir std::string, also liest es ein durch Leerzeichen getrenntes Wort.

std::stringstream  stream(str);
std::string        oneWord;
unsigned int       count = 0;

std::istream_iterator loop = std::istream_iterator<std::string>(stream);
std::istream_iterator end  = std::istream_iterator<std::string>();

for(;loop != end; ++count, ++loop) { *loop; }

Die Verwendung von std::distance packt einfach alle oben genannten Punkte in ein ordentliches Paket, da es den Abstand zwischen zwei Iteratoren ermittelt, indem es ++ für den ersten ausführt, bis wir den zweiten erreichen.

Um das Kopieren der Zeichenfolge zu vermeiden, können wir hinterhältig sein:

unsigned int countWordsInString(std::string const& str)
{
    std::stringstream stream;

    // sneaky way to use the string as the buffer to avoid copy.
    stream.rdbuf()->pubsetbuf (str.c_str(), str.length() );
    return std::distance(std::istream_iterator<std::string>(stream), std::istream_iterator<std::string>());
}

Hinweis: Wir kopieren immer noch jedes Wort aus dem Original in ein temporäres. Aber die Kosten dafür sind minimal.

Eine weniger clevere, für alle Programmierer in Ihrem Team offensichtlichere Methode, dies zu tun.

#include <cctype>

int CountWords(const char* str)
{
   if (str == NULL)
      return error_condition;  // let the requirements define this...

   bool inSpaces = true;
   int numWords = 0;

   while (*str != '\0')
   {
      if (std::isspace(*str))
      {
         inSpaces = true;
      }
      else if (inSpaces)
      {
         numWords++;
         inSpaces = false;
      }

      ++str;
   }

   return numWords;
}

Dazu können Sie std::count oder std::count_if verwenden. Unten ein einfaches Beispiel mit std::count:

//Count the number of words on string
#include <iostream>
#include <string>
#include <algorithm> //count and count_if is declared here

int main () {
    std::string sTEST("Text to verify how many words it has.");

    std::cout << std::count(sTEST.cbegin(), sTEST.cend(), ' ')+1;

    return 0;
}

UPDATE: Aufgrund der Beobachtung von Aydin Özcan (November 16) habe ich eine Änderung an dieser Lösung vorgenommen. Jetzt können die Wörter mehr als ein Leerzeichen zwischen sich haben. 🙂

//Count the number of words on string
#include <string>
#include <iostream>

int main () {
    std::string T("Text to   verify :  How many words does it   have?");

    size_t NWords = T.empty() || T.back() == ' ' ? 0 : 1;
    for (size_t s = T.size(); s > 0; --s)
        if (T[s] == ' ' && T[s-1] != ' ') ++NWords;

    std::cout << NWords;

    return 0;
}

Eine weitere Boost-basierte Lösung, die funktionieren könnte (ungetestet):

vector<string> result;
split(result, "aaaa bbbb cccc", is_any_of(" \t\n\v\f\r"), token_compress_on);

Weitere Informationen finden Sie in der Bibliothek für Boost-String-Algorithmen

Dies kann erfolgen, ohne jedes Zeichen manuell zu betrachten oder die Zeichenfolge zu kopieren.

#include <boost/iterator/transform_iterator.hpp>
#include <cctype>

boost::transform_iterator
    < int (*)(int), std::string::const_iterator, bool const& >
    pen( str.begin(), std::isalnum ), end( str.end(), std::isalnum );

size_t word_cnt = 0;

while ( pen != end ) {
    word_cnt += * pen;
    pen = std::mismatch( pen+1, end, pen ).first;
}

return word_cnt;

Ich habe mir erlaubt zu verwenden isalnum anstatt isspace.

Das ist nichts, was ich bei einem Vorstellungsgespräch tun würde. (Es ist nicht so, als wäre es beim ersten Mal kompiliert worden.)

Oder für alle Boost-Hasser ;v)

if ( str.empty() ) return 0;

size_t word_cnt = std::isalnum( * str.begin() );

for ( std::string::const_iterator pen = str.begin(); ++ pen != str.end(); ) {
    word_cnt += std::isalnum( pen[ 0 ] ) && ! std::isalnum( pen[ -1 ] );
}

return word_cnt;

Eine O(N)-Lösung, die auch sehr einfach zu verstehen und zu implementieren ist:

(Ich habe nicht nach einer leeren Zeichenfolgeneingabe gesucht. Aber ich bin sicher, dass Sie das leicht tun können.)

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

int countNumberOfWords(string sentence){
    int numberOfWords = 0;
    size_t i;

    if (isalpha(sentence[0])) {
        numberOfWords++;
    }

    for (i = 1; i < sentence.length(); i++) {
        if ((isalpha(sentence[i])) && (!isalpha(sentence[i-1]))) {
            numberOfWords++;
        }
    }

    return numberOfWords;
}

int main()
{
    string sentence;
    cout<<"Enter the sentence : ";
    getline(cin, sentence);

    int numberOfWords = countNumberOfWords(sentence);
    cout<<"The number of words in the sentence is : "<<numberOfWords<<endl;

    return 0;
}

Hier ist ein (fast) verzweigungsloser Single-Pass-Algorithmus, der das Gebietsschema berücksichtigt und Fälle mit mehr als einem Leerzeichen zwischen Wörtern behandelt:

1. Wenn die Zeichenfolge leer ist, geben Sie 0 zurück
2. let Übergänge = Anzahl benachbarter Zeichenpaare (c1, c2) wobei c1 == ' ' und c2 != ' '
3. Wenn der Satz mit einem Leerzeichen beginnt, kehren Sie zurück transitions sonst zurück transitions + 1

Hier ist ein Beispiel mit string = “Ein sehr, sehr, sehr, sehr, sehr großer Hund hat meine Hausaufgaben gefressen!!!!”

 i | 0123456789
c1 | A very, very, very, very, very big dog ate my homework!!!!
c2 |  A very, very, very, very, very big dog ate my homework!!!!
   |  x     x     x     x     x    x   x   x   x  x

Erläuterung

Let `i` be the loop counter.

When i=0: c1='A' and c2=' ', the condition `c1 == ' '` and `c2 != ' '` is not met
When i=1: c1=' ' and c2='A', the condition is met
... and so on for the remaining characters

Hier sind 2 Lösungen, die ich mir ausgedacht habe

Naive Lösung

size_t count_words_naive(const std::string_view& s)
{
    if (s.size() == 0) return 0;
    size_t count = 0;
    bool isspace1, isspace2 = true;
    for (auto c : s) {
        isspace1 = std::exchange(isspace2, isspace(c));
        count += (isspace1 && !isspace2);
    }
    return count;
}

Wenn Sie sorgfältig überlegen, können Sie diese Reihe von Operationen auf ein inneres Produkt reduzieren (nur zum Spaß, ich empfehle dies nicht, da dies wohl viel weniger lesbar ist).

Innere Produktlösung

size_t count_words_using_inner_prod(const std::string_view& s)
{
    if (s.size() == 0) return 0;
    auto starts_with_space = isspace(s.front());
    auto num_transitions = std::inner_product(
            s.begin()+1, s.end(), s.begin(), 0, std::plus<>(),
            [](char c2, char c1) { return isspace(c1) && !isspace(c2); });
    return num_transitions + !starts_with_space;
}