C ++ функция для подсчета всех слов в строке - PullRequest
13 голосов
/ 09 сентября 2010

Меня спросили об этом во время интервью, и, очевидно, это простой вопрос, но он не был и все еще не очевиден для меня.Не имеет значения, если они повторяются.Просто общее количество, как в слове текстовых файлов.Слова - это что-то, разделенное пробелом, и пунктуация не имеет значения, если она является частью слова.

Например: A very, very, very, very, very big dog ate my homework!!!! ==> 11 words

Мой «алгоритм» просто просматривает пробелы и увеличивает счетчик, пока я не достигну нуля.Так как я не получил работу и меня попросили уйти после этого, я думаю, что мое решение не было хорошим?У кого-нибудь есть более умное решение?Я что-то упустил?

Ответы [ 8 ]

34 голосов
/ 09 сентября 2010

При условии, что слова разделены пробелами:

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

Примечание. Между словами может быть несколько пробелов.Также это не улавливает другие пробельные символы, такие как новая строка табуляции или возврат каретки.Поэтому подсчета пробелов недостаточно.

Оператор ввода потока >> при использовании для чтения строки из потока.Читает одно слово, разделенное пробелами.Поэтому они, вероятно, искали, чтобы вы использовали это для идентификации слов.

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

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

Когда можно использовать это для подсчета слов в строке.

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.

Сложность:
Потокиможет обрабатываться так же, как и любой другой контейнер, и есть итераторы для их обхода std :: istream_iterator.Когда вы используете оператор ++ в istream_iterator, он просто читает следующее значение из потока, используя оператор >>.В этом случае мы читаем std :: string, поэтому он читает разделенное пробелами слово.

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

Использование std :: distance просто оборачивает все вышеперечисленное в аккуратный пакет, так как находит расстояние между двумя итераторами с помощьюделая ++ на первом, пока не достигнем второго.

Чтобы не копировать строку, мы можем быть хитрыми:

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

Примечание: мы все равно копируем каждое слово из оригинала ввременный характер.Но стоимость этого минимальна.

7 голосов
/ 09 сентября 2010

Менее умный, более очевидный для всех программистов способ сделать это.

#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;
}
5 голосов
/ 09 сентября 2010

Еще одно решение на основе повышения, которое может работать (не проверено):

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

Дополнительную информацию можно найти в библиотеке Boost String Algorithms

3 голосов
/ 28 июня 2017

Вы можете использовать std :: count или std :: count_if для этого.Ниже приведен простой пример с 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;
}
3 голосов
/ 09 сентября 2010

Это можно сделать без ручного просмотра каждого символа или копирования строки.

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

Я позволил себе использовать isalnum вместо isspace.

Этоне то, что я бы сделал на собеседовании.(Это не похоже на то, как это было скомпилировано в первый раз.)

Или, для всех ненавистников 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;
1 голос
/ 27 июня 2018

Вот один проходной, почти безветвительный, почти локализованный алгоритм, который обрабатывает дела с несколькими пробелами между словами:

  1. Если строка пуста, вернуть 0
  2. let transitions = количество соседних пар символов (c1, c2), где c1 == ' ' и c2 != ' '
  3. , если предложение начинается с пробела, возвращает transitions, иначе возвращает transitions + 1

Вот пример со строкой = "Очень, очень, очень, очень, очень большая собака съела мою домашнюю работу !!!!"

 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

Пояснение

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

Вот 2 решения, которые я придумала

Наивное решение

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

Если вы внимательно подумаете, высможет сократить этот набор операций до внутреннего продукта (просто для удовольствия, я не рекомендую этого, поскольку это, возможно, гораздо менее читабельно).

Внутреннее решение продукта

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;
}
1 голос
/ 01 марта 2013

O (N) решение, которое также очень просто понять и реализовать:

(Я не проверял ввод пустой строки. Но я уверен, что это легко сделать.)

#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;
}
0 голосов
/ 30 апреля 2014

Очень краткий O (N) подход:

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

Подход "разделяй и властвуй", сложность также 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);
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...