Язык программирования C++. Вводный курс. С для начинающих
 Скачать 5.41 Mb.
|
|
266 6.7. Читаем текстовый файл Первая наша задача – прочитать текстовый файл, в котором будет производиться поиск. Нам нужно сохранить следующую информацию: само слово, номер строки и позицию в строке, где слово встречается. Как получить одну строку текста? Стандартная библиотека предоставляет для этого функцию getline(): getline( istream &is, string str, char delimiter ); getline() берет из входного потока все символы, включая пробелы, и помещает их в объект типа string, до тех пор пока не встретится символ delimiter, не будет достигнут конец файла или количество полученных символов не станет равным величине, возвращаемой функцией-членом max_size()класса string. Мы будем помещать каждую такую строку в вектор. Мы вынесли код, читающий файл, в функцию, названную retrieve_text(). В объекте типа pair дополнительно сохраняется размер и номер самой длинной строки. (Полный текст программы приводится в разделе 6.14.) Вот реализация функции ввода файла: 15 15 Программа компилировалась компилятором, не поддерживающим значений параметров по умолчанию шаблонов. Поэтому нам пришлось явно указать аллокатор: vector Для компилятора, полностью соответствующего стандарту С++, достаточно отметить тип элементов: vector istream& С++ для начинающих 267 } Вот как выглядит вывод программы (размер страницы книги недостаточен, чтобы расположить напечатанные строки во всю длину, поэтому мы сделали в тексте отступы, показывающие, где реально заканчивалась строка): please enter file name: a1ice_emma line read: Alice Emma has long flowing red hair. Her Daddy says line read: when the wind blows through her hair, it looks almost alive, line read: like a fiery bird in flight. A beautiful fiery bird, he tells her, line read: magical but untamed. "Daddy, shush, there is no such thing, " line read: she tells him, at the same time wanting him to tell her more. line read: Shyly, she asks, "I mean. Daddy, is there?" number of lines: 6 maximum length: 66 longest line: like a fiery bird in flight. A beautiful fiery bird, he tells her, // возвращаемое значение - указатель на строковый вектор vector { string file_name; cout << "please enter file name: "; cin >> file_name; // откроем файл для ввода ... ifstream 1nfile( file_name.c_str(), ios::in ); if ( ! infile ) { cerr << "oops! unable to open file " << file_name << " -- bailing out!\n"; exit( -1 ); } else cout << '\n'; vector } 1ines_of_text->push_back( textline ); linenum++; } return lines_of_text; С++ для начинающих 268 После того как все строки текста сохранены, нужно разбить их на слова. Сначала мы отбросим знаки препинания. Например, возьмем строку из части “Anna Livia Plurrabelle” романа “Finnegans Wake”. "For every tale there's a telling, and that's the he and she of it." В приведенном фрагменте есть следующие знаки препинания: "For there's telling, that's it." А хотелось бы получить: For there telling that it Можно возразить, что there's должно превратиться в there is но мы-то движемся в другом направлении: следующий шаг – это отбрасывание семантически нейтральных слов, таких, как is, that, and, it и т.д. Так что для данной строчки из “Finnegans Wake” только два слова являются значимыми: tale и telling, и только по этим словам будет выполняться поиск. (Мы реализуем набор стоп-слов с помощью контейнерного типа set, который подробно рассматривается в следующем разделе.) После удаления знаков препинания нам необходимо превратить все прописные буквы в строчные, чтобы избежать проблем с поиском в таких, например, строках: Home is where the heart is. A home is where they have to let you in. Несомненно, запрос слова home должен найти обе строки. Мы должны также обеспечить минимальную поддержку учета словоформ: отбрасывать окончания слов, чтобы слова dog и dogs, love, loving и loved рассматривались системой как одинаковые. С++ для начинающих 269 В следующем разделе мы вернемся к описанию стандартного класса string и рассмотрим многочисленные операции над строками, которые он поддерживает, в контексте дальнейшей разработки нашей поисковой системы. 6.8. Выделяем слова в строке Нашей первой задачей является разбиение строки на слова. Мы будем вычленять слова, находя разделяющие их пробелы с помощью функции find(). Например, в строке Alice Emma has long flowing red hair. насчитывается шесть пробелов, следовательно, эта строка содержит семь слов. Класс string имеет несколько функций поиска. find() – наиболее простая из них. Она ищет образец, заданный как параметр, и возвращает позицию его первого символа в строке, если он найден, или специальное значение string::npos в противном случае. Например: } Хотя позиция подстроки почти всегда имеет тип int, более правильное и переносимое объявление типа результата, возвращаемого find(), таково: string::size_type Например: string::size_type pos = name.find( "Anna" ); Функция find() делает не совсем то, что нам надо. Требуемая функциональность обеспечивается функцией find_first_of(), которая возвращает позицию первого символа, соответствующего одному из заданных в строке-параметре. Вот как найти первый символ, являющийся цифрой: #include #include С++ для начинающих 270 } В этом примере pos получает значение 1 (напоминаем, что символы строки нумеруются с 0 ). Но нам нужно найти все вхождения символа, а не только первое. Такая возможность реализуется передачей функции find_first_of() второго параметра, указывающего позицию, с которой начать поиск. Изменим предыдущий пример. Можете ли вы сказать, что в нем все еще не вполне удовлетворительно? } В начале цикла pos равно 0, поэтому поиск идет с начала строки. Первое вхождение обнаружено в позиции 1. Поскольку найденное значение не совпадает с string::npos, выполнение цикла продолжается. Для второго вызова find_first_of()значение pos равно 1. Поиск начнется с 1-й позиции. Вот ошибка! Функция find_first_of() снова найдет цифру в первой позиции, и снова, и снова... Получился бесконечный цикл. Нам необходимо увеличивать pos на 1 в конце каждой итерации: #include #include найдена цифра в позиции: " << pos << "\t элемент равен " << name[pos] << endl; #include #include // где-то здесь ошибка! while (( pos = name.find_first_of( numerics, pos )) != string::npos ) cout << " найдена цифра в позиции: " << pos << "\t элемент равен " << name[pos] << endl; С++ для начинающих 271 } Чтобы найти все пустые символы (к которым, помимо пробела, относятся символы табуляции и перевода строки), нужно заменить строку numerics в этом примере строкой, содержащей все эти символы. Если же мы уверены, что используется только символ пробела и никаких других, то можем явно задать его в качестве параметра функции: // ... Чтобы узнать длину слова, введем еще одну переменную: } На каждой итерации prev_pos указывает позицию начала слова, а pos – позицию следующего символа после его конца. Соответственно, длина слова равна: pos - prev_pos; // длина слова После того как мы выделили слово, необходимо поместить его в строковый вектор. Это можно сделать, копируя в цикле символы из textline с позиции prev_pos до pos -1. Функция substr() сделает это за нас: // исправленная версия цикла while (( pos = name.find_first_of( numerics, pos )) != string::npos ) { cout << " найдена цифра в позиции: " << pos << "\t элемент равен " << name[pos] << endl; // сдвинуться на 1 символ ++pos; // фрагмент программы 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; С++ для начинающих 272 } Функция substr() возвращает копию подстроки. Первый ее аргумент обозначает первую позицию, второй – длину подстроки. (Второй аргумент можно опустить, тогда подстрока включит в себя остаток исходной строки, начиная с указанной позиции.) В нашей реализации допущена ошибка: последнее слово не будет помещено в контейнер. Почему? Возьмем строку: seaspawn and seawrack После каждого из первых двух слов поставлен пробел. Два вызова функции find_first_of() вернут позиции этих пробелов. Третий же вызов вернет string::npos , и цикл закончится. Таким образом, последнее слово останется необработанным. Вот полный текст функции, названной нами separate_words(). Помимо сохранения слов в векторе строк, она вычисляет координаты каждого слова – номер строки и колонки (нам эта информация потребуется впоследствии). // фрагмент программы vector != string::npos ) { words.push_back( textline.substr( prev_pos, pos-prev_pos)); prev_pos = ++pos; С++ для начинающих 273 } Теперь функция main()выглядит следующим образом: } typedef pair { // words: содержит набор слов // locations: содержит информацию о строке и позиции // каждого слова vector // 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 ); int main() { vector // ... С++ для начинающих 274 Вот часть распечатки, выданной тестовой версией 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::size_type 1ast_pos = river.rfind( "is" ); find() вернет 1, указывая позицию первого вхождения подстроки "is", а rfind() – 4 (позиция последнего вхождения "is"). find_first_not_of() ищет первый символ, не содержащийся в строке, переданной как параметр. Например, чтобы найти первый символ, не являющийся цифрой, можно написать: string river( "Mississippi" ); string::size_type first_pos = river.find( "is" ); С++ для начинающих 275 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 sentence = linel + line2 + line3; Если несколько слов имеют длину, равную максимальной или минимальной, учтите их все. 6.9. Обрабатываем знаки препинания После того как мы разбили каждую строку на слова, необходимо избавиться от знаков препинания. Пока из строки magical but untamed. "Daddy, shush, there is no such thing," у нас получился такой набор слов: magical but untamed. "Daddy, shush, there is no string elems( "0123456789" ); string dept_code( "03714p3" ); // возвращается позиция символа 'p' string linel = "We were her pride of 10 she named us --"; string line2 = "Benjamin, Phoenix, the Prodigal" string line3 = "and perspicacious pacific Suzanne"; С++ для начинающих 276 such thing," Как нам теперь удалить ненужные знаки препинания? Для начала определим строку, содержащую все символы, которые мы хотим удалить: string filt_elems( "\",.;:!?)(\\/" ); (Обратная косая черта указывает на то, что следующий за ней символ должен в данном контексте восприниматься буквально, а не как специальная величина. Так, \" обозначает символ двойной кавычки, а не конец строки, а \\ – символ обратной косой черты.) Теперь можно применить функцию-член find_first_of() для поиска всех вхождений нежелательных символов: != string::npos ) Найденный символ удаляется с помощью функции-члена erase(): word.erase(pos,1); Первый аргумент этой функции означает позицию подстроки, а второй – ее длину. Мы удаляем один символ, находящийся в позиции pos. Второй аргумент является необязательным; если его опустить, будут удалены все символы от pos до конца строки. Вот полный текст функции filter_text(). Она имеет два параметра: указатель на вектор строк, содержащий текст, и строку с символами, которые нужно убрать. } Почему мы не увеличиваем значение pos на каждой итерации? Что было бы, если бы мы написали: while (( pos = word.find_first_of( filt_elems, pos )) void filter_text( vector { vector // Если filter не задан, зададим его сами if ( ! filter.size() ) filter.insert( 0, "\".," ); while ( iter != iter_end ) { string::size_type pos = 0; // удалим каждый найденный элемент while (( pos = (*iter).find_first_of( filter, pos )) != string::npos ) (*iter).erase(pos,1); iter++; } С++ для начинающих 277 } Возьмем строку thing," На первой итерации pos получит значение 5 , т.е. позиции, в которой находится запятая. После удаления запятой строка примет вид thing" Теперь в 5-й позиции стоит двойная кавычка. Если мы увеличим значение pos, то пропустим этот символ. Так мы будем вызывать функцию filter_text(): filter_text( text_locations->first, filt_elems ); А вот часть распечатки, сделанной тестовой версией filter_text(): filter_text: untamed. found! : pos: 7. after: untamed filter_text: "Daddy, found! : pos: 0. after: Daddy, found! : pos: 5. after: Daddy filter_text: thing," found! : pos: 5. after: thing" found! : pos: 5. after: thing filter_text: "I found! : pos: 0. after: I filter_text: Daddy, found! : pos: 5. after: Daddy filter_text: there?" found! : pos: 5. after: there" found! : pos: 5. after: there while (( pos = (*iter).find_first_of( filter, pos )) != string::npos ) { (*iter).erase(pos,1); ++ pos; // неправильно... string filt_elems( "\",.;:!?)(\\/" ); |