Fonction C++ pour compter tous les mots dans une chaîne de caractères

En supposant que les mots sont séparés par des espaces:

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>());
}

Remarque: Il peut y avoir plus d'un espace entre les mots. Aussi cela ne veut pas attraper d'autres caractères blancs comme de l'onglet nouvelle ligne ou un retour chariot. Si le comptage des espaces n'est pas assez.

Le flux d'entrée de l'opérateur >> lorsqu'il est utilisé pour lire une chaîne de caractères à partir d'un flux. Lit-on dans un espace blanc mot séparé. Ils étaient donc probablement à la recherche pour vous de l'utiliser pour identifier les mots.

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

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

Quand pouvez l'utiliser pour compter le nombre de mots dans une chaîne de caractères.

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.

Se complique:

Cours d'eau peut être traité comme tout autre récipient et y sont des itérateurs pour parcourir en boucle std::istream_iterator. Lorsque vous utilisez l'opérateur ++ sur un istream_iterator il suffit de lire les prochaines valeur du flux à l'aide de l'opérateur >>. Dans ce cas, nous sommes la lecture de std::string afin qu'il lit un espace séparé de parole.

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; }

En utilisant std::distance, tout encapsule tous les ci-dessus dans un paquet bien rangé comme il trouver la distance entre deux itérateurs en faisant ++ sur le premier jusqu'à ce que nous arrivons à la seconde.

Pour éviter la copie de la chaîne, nous pouvons être sournois:

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>());
}

Remarque: nous avons encore copie de chaque mot de l'original dans une mesure temporaire. Mais le coût est minime.

OriginalL'auteur Martin York

Cela peut être fait sans rechercher manuellement à chaque personnage ou de la copie de la chaîne.

#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;

J'ai pris la liberté d'utiliser isalnum au lieu de isspace.

Ce n'est pas quelque chose que je ferais à l'entrevue d'emploi. (Ce n'est pas compilé la première fois.)

Ou, pour tous, le coup de pouce rageux ;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;

OriginalL'auteur Potatoswatter

Un O(N) c'est aussi une solution très simple à comprendre et à mettre en œuvre:

(Je n'ai pas vérifié pour une chaîne vide d'entrée. Mais je suis sûr que vous pouvez le faire facilement.)

#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;
}

OriginalL'auteur totjammykd

Très concis O(N) approche:

bool is_letter(char c) { return c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z'; }

int count_words(const string& s) {
    int i = 0, N = s.size(), count = 0;
    while(i < N) {
        while(i < N && !is_letter(s[i])) i++;
        if(i == N) break;
        while(i < N && is_letter(s[i])) i++;
        count++;
    }
    return count;
}

Un divide-and-conquer approche, la complexité est également en O(N):

int DC(const string& A, int low, int high) {
if(low > high) return 0;
int mid = low + (high - low) / 2;
int count_left = DC(A, low, mid-1);
int count_right = DC(A, mid+1, high);
if(!is_letter(A[mid])) 
return count_left + count_right;
else {
if(mid == low && mid == high) return 1;
if(mid-1 < low) {
if(is_letter(A[mid+1])) return count_right;
else return count_right+1;
} else if(mid+1 > high) {
if(is_letter(A[mid-1])) return count_left;
else return count_left+1;
}
else {
if(!is_letter(A[mid-1]) && !is_letter(A[mid+1])) 
return count_left + count_right + 1;
else if(is_letter(A[mid-1]) && is_letter(A[mid+1]))
return count_left + count_right - 1;
else
return count_left + count_right;
}
}
}
int count_words_divide_n_conquer(const string& s) {
return DC(s, 0, s.size()-1);
}

OriginalL'auteur sunjerry