Язык программирования C++. Вводный курс

Выделяем слова в строке


Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова, находя разделяющие их пробелы с помощью функции find(). Например, в строке

Alice Emma has long flowing red hair.

насчитывается шесть пробелов, следовательно, эта строка содержит семь слов.

Класс string

имеет несколько функций поиска. find() – наиболее простая из них. Она ищет образец, заданный как параметр, и возвращает позицию его первого символа в строке, если он найден, или специальное значение string::npos в противном случае. Например:

#include <string>

#include <iostream>

int main() {

    string name( "AnnaBelle" );

    int pos = name.find( "Anna" );



    if ( pos == string::npos )

        cout << "Anna не найдено!\n";

    else cout << "Anna найдено в позиции: " << pos << endl;

}

Хотя позиция подстроки почти всегда имеет тип int, более правильное и переносимое объявление типа результата, возвращаемого find(), таково:

string::size_type

Например:

string::size_type pos = name.find( "Anna" );

Функция find()

делает не совсем то, что нам надо. Требуемая функциональность обеспечивается функцией find_first_of(), которая возвращает позицию первого символа, соответствующего одному из заданных в строке-параметре. Вот как найти первый символ, являющийся цифрой:

#include <string>

#include <iostream>

int main() {

    string numerics( "0123456789" );

    string name( "r2d2" );

    string:: size_type pos = name.find_first_of( numerics );

    cout << "найдена цифра в позиции: "

         << pos       << "\tэлемент равен "

         << name[pos] << endl;

}

В этом примере pos

получает значение 1

(напоминаем, что символы строки нумеруются с 0).

Но нам нужно найти все вхождения символа, а не только первое. Такая возможность реализуется передачей функции find_first_of()


второго параметра, указывающего позицию, с которой начать поиск. Изменим предыдущий пример. Можете ли вы сказать, что в нем все еще не вполне удовлетворительно?



#include <string>

#include <iostream>

int main() {

    string numerics( "0123456789" );

    string name( "r2d2" );

    string::size_type pos = 0;

    // где-то здесь ошибка!

    while (( pos = name.find_first_of( numerics, pos ))

                != string::npos )

        cout << "найдена цифра в позиции: "

             << pos       << "\tэлемент равен "

             << name[pos] << endl;
}

В начале цикла pos

равно 0, поэтому поиск идет с начала строки. Первое вхождение обнаружено в позиции 1. Поскольку найденное значение не совпадает с string::npos, выполнение цикла продолжается. Для второго вызова find_first_of()значение pos

равно 1. Поиск начнется с 1-й позиции. Вот ошибка! Функция find_first_of()

снова найдет цифру в первой позиции, и снова, и снова... Получился бесконечный цикл. Нам необходимо увеличивать pos на 1 в конце каждой итерации:



// исправленная версия цикла

while (( pos = name.find_first_of( numerics, pos ))

            != string::npos )

{

        cout << "найдена цифра в позиции: "

             << pos       << "\tэлемент равен "

             << name[pos] << endl;

    // сдвинуться на 1 символ

    ++pos;
}

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



// фрагмент программы

while (( pos = textline.find_first_of( ' ', pos ))

            != string::npos )
    // ...

Чтобы узнать длину слова, введем еще одну переменную:



// фрагмент программы

// pos: позиция на 1 большая конца слова

// prev_pos: позиция начала слова

string::size_type pos = 0, prev_pos = 0;

while (( pos = textline.find_first_of( ' ', pos ))

            != string::npos )

{

    // ...

    // запомнить позицию начала слова

    prev_pos = ++pos;
<


}

На каждой итерации prev_pos

указывает позицию начала слова, а pos – позицию следующего символа после его конца. Соответственно, длина слова равна:

pos - prev_pos; // длина слова

После того как мы выделили слово, необходимо поместить его в строковый вектор. Это можно сделать, копируя в цикле символы из textline с позиции prev_pos до pos -1. Функция substr() сделает это за нас:



// фрагмент программы

vector<string> words;

while (( pos = textline.find_first_of( ' ', pos ))

            != string::npos )

{

    words.push_back( textline.substr(

                     prev_pos, pos-prev_pos));

    prev_pos = ++pos;
}

Функция substr()

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

В нашей реализации допущена ошибка: последнее слово не будет помещено в контейнер. Почему? Возьмем строку:

seaspawn and seawrack

После каждого из первых двух слов поставлен пробел. Два вызова функции find_first_of()

вернут позиции этих пробелов. Третий же вызов вернет string::npos, и цикл закончится. Таким образом, последнее слово останется необработанным.

Вот полный текст функции, названной нами separate_words(). Помимо сохранения слов в векторе строк, она вычисляет координаты каждого слова – номер строки и колонки (нам эта информация потребуется впоследствии).



typedef pair<short,short> location;

typedef vector<location>  loc;

typedef vector<string>    text;

typedef pair<text* ,loc*> text_loc;

text_loc*

separate_words( const vector<string> *text_file )

{

    // words: содержит набор слов

    // locations: содержит информацию о строке и позиции

    // каждого слова

    vector<string>   *words = new vector<string>;

    vector<location> * locations = new vector<location>;

    short line_pos = 0; // текущий номер строки

    // iterate through each line of text

    for ( ; line_pos < text_file->size(); ++line_pos )

        // textline: обрабатываемая строка

        // word_pos: позиция в строке

        short word_pos = 0;

        string textline = (*text_file) [ line_pos ];

        string::size_type pos = 0, prev_pos = 0;

        while (( pos = textline.find_first_of( ' ', pos ))

                    != string::npos )

        {

            // сохраним слово

            words->push_back(

                textline.substr( prev_pos, pos - prev_pos ));

            // сохраним информацию о его строке и позиции

            locations->push_back(

                make_pair( line_pos, word_pos ));

            // сместим позицию для следующей итерации

            ++word_pos; prev_pos = ++pos;

        }

        // обработаем последнее слово

        words->push_back(

               textline.substr( prev_pos, pos - prev_pos ));

        locations->push_back(

               make_pair( line_pos, word_pos ));

    }

    return new text_loc( words, locations );
<


}

Теперь функция main()выглядит следующим образом:



int main()

{

    vector<string> *text_file = retrieve_text();

    text_loc *text_locations = separate_words( text_file );

    // ...
}

Вот часть распечатки, выданной тестовой версией separate_words():

textline: Alice Emma has long flowing red hair. Her Daddy

          says

eol: 52 pos: 5 line: 0 word: 0 substring: Alice

eol: 52 pos: 10 line: 0 word: 1 substring: Emma

eol: 52 pos: 14 line: 0 word: 2 substring: has

eol: 52 pos: 19 line: 0 word: 3 substring: long

eol: 52 pos: 27 line: 0 word: 4 substring: flowing

eol: 52 pos: 31 line: 0 word: 5 substring: red

eol: 52 pos: 37 line: 0 word: 6 substring: hair.

eol: 52 pos: 41 line: 0 word: 7 substring: Her

eol: 52 pos: 47 line: 0 word: 8 substring: Daddy

last word on line substring: says

...

textline: magical but untamed. "Daddy, shush, there is no

          such thing,"

eol: 60 pos: 7 line: 3 word: 0 substring: magical

eol: 60 pos: 11 line: 3 word: 1 substring: but

eol: 60 pos: 20 line: 3 word: 2 substring: untamed

eol: 60 pos: 28 line: 3 word: 3 substring: "Daddy,

eol: 60 pos: 35 line: 3 word: 4 substring: shush,

eol: 60 pos: 41 line: 3 word: 5 substring: there

eol: 60 pos: 44 line: 3 word: 6 substring: is

eol: 60 pos: 47 line: 3 word: 7 substring: no

eol: 60 pos: 52 line: 3 word: 8 substring: such

last word on line substring: thing,":

...

textline: Shy1y, she asks, "I mean, Daddy: is there?"

eol: 43 pos: 6 line: 5 word: 0 substring: Shyly,

eol: 43 pos: 10 line: 5 word: 1 substring: she

eol: 43 pos: 16 line: 5 word: 2 substring: asks,

eol: 43 pos: 19 line: 5 word: 3 substring: "I

eol: 43 pos: 25 line: 5 word: 4 substring: mean,

eol: 43 pos: 32 line: 5 word: 5 substring: Daddy,

eol: 43 pos: 35 line: 5 word: 6 substring: is

last word on line substring: there?":

Прежде чем продолжить реализацию поисковой системы, вкратце рассмотрим оставшиеся функции-члены класса string, предназначенные для поиска. Функция rfind() ищет последнее, т.е. самое правое, вхождение указанной подстроки:





string river( "Mississippi" );

string::size_type first_pos = river.find( "is" );
string::size_type 1ast_pos = river.rfind( "is" );

find()

вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4

(позиция последнего вхождения "is").

find_first_not_of()

ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать:



string elems( "0123456789" );

string dept_code( "03714p3" );

// возвращается позиция символа 'p'
string::size_type pos = dept_code.find_first_not_of(elems) ;

find_last_of()

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

Упражнение 6.13

Напишите программу, которая ищет в строке

"ab2c3d7R4E6"

цифры, а затем буквы, используя сначала find_first_of(), а потом find_first_not_of().

Упражнение 6.14

Напишите программу, которая подсчитывает все слова и определяет самое длинное и самое короткое из них в строке sentence:



string linel = "We were her pride of 10 she named us --";

string line2 = "Benjamin, Phoenix, the Prodigal"

string line3 = "and perspicacious pacific Suzanne";
string sentence = linel + line2 + line3;

Если несколько слов имеют длину, равную максимальной или минимальной, учтите их все.


Содержание раздела