Funkcja C++ do zliczania wszystkich słów w ciągu

Question

Zapytano mnie o to podczas wywiadu i najwyraźniej jest to łatwe pytanie, ale nie było i nadal nie jest dla mnie oczywiste.

Podając ciąg, policz wszystkie słowa w nim. Nie ma znaczenia, czy są powtarzane. Tylko całkowita liczba, jak w przypadku liczby słów plików tekstowych. Słowa są cokolwiek oddzielone spacją, a interpunkcja nie ma znaczenia, o ile jest częścią słowa.

Na przykład: A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Mój „algorytm” po prostu przechodzi szukają przestrzeni i inkrementacja licznika, dopóki nie uderzył null. Ponieważ nie dostałem pracy i zostałem poproszony o opuszczenie tego miejsca, myślę, że moje rozwiązanie nie było dobre? Czy ktoś ma bardziej sprytne rozwiązanie? Czy czegoś brakuje?

Answer 1

Mniej sprytna, bardziej oczywista dla wszystkich metod programistów w zespole.

#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

Zakładając słowa są białe znaki rozdzielone: ​​

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

Uwaga: Może być więcej niż jedna przestrzeń między słowami. Nie powoduje to również przechwycenia innych znaków spacji, takich jak tabulacja nowej linii lub powrót karetki. Więc liczenie miejsc nie wystarczy.

Operator wprowadzania strumienia >> w przypadku użycia do odczytu łańcucha ze strumienia. Odczytuje jedno słowo oddzielone spacją. Tak więc prawdopodobnie szukali tego, aby użyć tego do identyfikacji słów.

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

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

Kiedy można użyć tego do policzenia słów w ciągu znaków.

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. 

Pierwsze skomplikowane:
Strumienie mogą być traktowane jak każdy inny pojemnik i są iteratory do pętli przez nich std :: istream_iterator. Kiedy używasz operatora ++ na istream_iterator, po prostu odczytaj następną wartość ze strumienia za pomocą operatora >>. W tym przypadku czytamy std :: string, aby odczytać słowo oddzielone spacją.

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

Używanie std :: odległość tylko zawija wszystko powyższe w pakiecie schludny jak to znaleźć odległość między dwoma iteratorów wykonująC++ na pierwszym dojeżdżamy do drugiego.

Aby uniknąć kopiowania ciąg możemy być podstępne:

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

Uwaga: wciąż skopiować każde słowo z oryginału na tymczasowy. Ale koszt tego jest minimalny.

Answer 3

Można to zrobić bez ręcznego przeglądania każdej postaci lub kopiowania ciągu znaków.

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

Pozwoliłem sobie korzystania isalnum zamiast isspace.

To nie jest coś, co zrobiłbym podczas rozmowy kwalifikacyjnej. (To nie jest tak, jak skompilowane za pierwszym razem.)

Lub dla wszystkich haters Google 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

Innym rozwiązaniem doładowania w oparciu, które mogą pracować (niesprawdzone):

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

Więcej informacji można znaleźć w Boost String Algorithms Library

Answer 5

Rozwiązanie O (N), które jest również bardzo łatwe do zrozumienia i wdrożenia:

(Nie sprawdziłem pod kątem pustego łańcucha wejściowego. Ale jestem pewien, że można to zrobić łatwo)

#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

bardzo zwięzły O N) podejście (:.

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

Podejście dziel i zwyciężaj, złożoność jest 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

Możesz użyć std :: count lub std :: count_if, aby to zrobić. Poniżej prostego przykładu ze 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; 
}