C++ función para contar todas las palabras en una cadena

Question

Me lo preguntaron durante una entrevista y, aparentemente, es una pregunta fácil, pero no fue y todavía no es obvio para mí.

Dada una cuerda, cuente todas las palabras en ella. No importa si se repiten. Solo el conteo total como en un recuento de palabras de archivos de texto. Las palabras son cualquier cosa separada por un espacio y la puntuación no importa, siempre que sea parte de una palabra.

Por ejemplo: A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Mi "algoritmo" simplemente pasa por buscar espacios y aumentar un contador hasta que llegué a un valor nulo. Como no conseguí el trabajo y me pidieron que me fuera después de eso, ¿supongo que mi solución no fue buena? Alguien tiene una solución más inteligente? ¿Me estoy perdiendo de algo?

Answer 1

Un método menos inteligente, más obvio para todos los programadores en su equipo para hacerlo.

#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 != NULL) 
    { 
     if (std::isspace(*str)) 
     { 
     inSpaces = true; 
     } 
     else if (inSpaces) 
     { 
     numWords++; 
     inSpaces = false; 
     } 

     ++str; 
    } 

    return numWords; 
} 

Answer 2

palabras Suponiendo son espacios en blanco separado:

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

Nota: Puede haber más de un espacio entre las palabras. Además, esto no capta otros caracteres de espacio en blanco, como tabulación nueva línea o retorno de carro. Entonces contar espacios no es suficiente.

El operador de entrada de secuencia >> cuando se utiliza para leer una cadena de una secuencia. Lee una palabra separada en blanco. Probablemente buscaban que lo usara para identificar palabras.

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

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

Cuando puede usar esto para contar palabras en una cadena.

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. 

está complicando:
corrientes pueden ser tratados como cualquier otro recipiente y hay iteradores a bucle a través de ellos std :: istream_iterator. Cuando usas el operador ++ en un istream_iterator, solo lees el siguiente valor de la secuencia usando el operador >>. En este caso, estamos leyendo std :: string para que lea una palabra separada del espacio.

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

El uso de std :: distancia simplemente envuelve todo lo anterior en un paquete ordenado, ya que encontrar la distancia entre dos iteradores haciendo ++ en la primera hasta llegar a la segunda.

Para evitar copiar la cadena que puede ser astuto:

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

Nota: todavía copiar cada palabra del original en un temporal. Pero el costo de eso es mínimo.

Answer 3

Esto se puede hacer sin mirar manualmente cada carácter ni copiar la cadena.

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

he tomado la libertad de utilizar isalnum en lugar de isspace.

Esto no es algo que haría en una entrevista de trabajo. (No es como compilado la primera vez).)

O, para todos los enemigos Boost; 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; 

Answer 4

Otra solución basada impulso que puede funcionar (no probado):

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

Más información se puede encontrar en el Boost String Algorithms Library

Answer 5

Una solución O (N) que también es muy fácil de comprender e implementar:

(No he verificado una entrada de cadena vacía. Pero estoy seguro de que puede hacerlo fácilmente)

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

Answer 6

A O muy concisa N) enfoque (:.

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 enfoque de divide y vencerás, la complejidad es también 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); 
} 

Answer 7

puede utilizar el std :: contar o std :: count_if en hacer eso. Debajo de un ejemplo simple con std :: count:

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

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

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

    return 0; 
}