Язык программирования C++. Вводный курс. С для начинающих

• Название: С для начинающих
• Дата: 24.08.2022
• Размер: 5.41 Mb.
• Имя файла: Язык программирования C++. Вводный курс.pdf
• Тип: Документы; #652350
• страница: 85 из 93

909
(*static_cast(this)) = rhs;
(Реализация копирующих операторов присваивания в классах AndQuery и OrQuery выглядит так же, поэтому мы оставим ее в качестве упражнения.)
Ниже предложена небольшая программа для тестирования данной реализации. Мы создаем или копируем объект, а затем распечатываем его.
}
После компиляции и запуска программа печатает следующее: notQuery 1: ! alice notQuery 2: ! alice notQuery 3: ! emma notQuery 3 присвоено значение nq2: ! alice
AndQuery : ! alice && emma
AndQuery 2: ! alice && emma
AndQuery 3: alice && emma
AndQuery 2 после присваивания: alice && emma
Упражнение 17.18
Реализуйте копирующие конструкторы в классах AndQuery и OrQuery.
Упражнение 17.19
Реализуйте копирующие операторы присваивания в классах AndQuery и OrQuery.
Упражнение 17.20
#include "Query.h" int main()
{
NameQuery nm( "alice" );
NameQuery nm( "emma" );
NotQuery nq1( &nm ); cout << "notQuery 1: " << nq1 << endl;
NotQuery nq2( nq1 ); cout << "notQuery 2: " << nq2 << endl;
NotQuery nq3( &nm2 ); cout << "notQuery 3: " << nq3 << endl; nq3 = nq2; cout << "notQuery 3 присвоено значение nq2: " << nq3 << endl;
AndQuery aq( &nq1, &nm2 ); cout << "AndQuery : " << aq << endl;
AndQuery aq2( aq ); cout << "AndQuery 2: " << aq2 << endl;
AndQuery aq3( &nm, &nm2 ); cout << "AndQuery 3: " << aq3 << endl; aq2 = aq3; cout << "AndQuery 2 после присваивания: " << aq2 << endl;

С++ для начинающих
910
Что указывает на необходимость реализации явных копирующего конструктора и копирующего оператора присваивания?
17.7.
Управляющий класс UserQuery
Если имеется запрос такого типа: fiery && ( bird || potato ) то в нашу задачу входит построение эквивалентной иерархии классов:
NameQuery( "potato" )
Как лучше всего это сделать? Процедура вычисления ответа на запрос напоминает функционирование конечного автомата. Мы начинаем с пустого состояния и при обработке каждого элемента запроса переходим в новое состояние, пока весь запрос не будет разобран. В основе нашей реализации лежит одна инструкция switch внутри операции, которую мы назвали eval_query(). Слова запроса считываются одно за другим из вектора строк и сравниваются с каждым из возможных значений:
AndQuery
NameQuery( "fiery" )
OrQuery
NameQuery( "bird" )

С++ для начинающих
911
}
Пять операций eval: evalWord(), evalAnd(), evalOr(), evalNot и evalRParen() – как раз и строят иерархию классов Query. Прежде чем обратиться к деталям их реализации, рассмотрим общую организацию программы.
Нам нужно определить каждую операцию в виде отдельной функции, как это было сделано в главе 6 при построении процедур обработки запроса. Пользовательский запрос и производные от Query классы представляют независимые данные, которыми оперируют эти функции. От такой модели программирования (она называется процедурной) мы предпочли отказаться.
В разделе 6.14 мы ввели класс TextQuery, где инкапсулировали операции и данные, изучавшиеся в главе 6. Здесь нам потребуется класс UserQuery, решающий аналогичные задачи.
Одним из членов этого класса должен быть вектор строк, содержащий сам запрос пользователя. Другой член – это указатель типа Query* на иерархическое представление запроса, построенное в eval_query(). Еще три члена служат для обработки скобок:
•
_paren помогает изменить подразумеваемый порядок вычисления операторов (чуть позже мы продемонстрируем это на примере);
•
_lparenOn и _rparenOn содержат счетчики левых и правых скобок, ассоциированные с текущим узлом дерева разбора запроса (мы показывали, как они используются, при обсуждении виртуальной функции print() в разделе 17.5.1). vector::iterator it = _query->begin(), end_it = _query->end(); for ( ; it != end_it; ++it ) switch( evalQueryString( *it ))
{ case WORD: evalWord( *it ); break; case AND: evalAnd(); break; case OR: evalOr(); break; case NOT: evalNot(); break; case LPAREN:
++_paren;
++_lparenOn; break; case RPAREN:
--_paren;
++_rparenOn; evalRParen(); break;

С++ для начинающих
912
Помимо этих пяти членов, нам понадобятся еще два. Рассмотрим следующий запрос: fiery || untamed
Наша цель – представить его в виде следующего объекта OrQuery:
NameQuery( "untamed" )
Однако порядок обработки такого запроса вызывает некоторые проблемы. Когда мы определяем объект NameQuery, объект OrQuery , к которому его надо добавить, еще не определен. Поэтому необходимо место, где можно временно сохранить объект
NameQuery
Чтобы сохранить что-либо для последующего использования, традиционно применяется стек. Поместим туда наш объект NameQuery. А когда позже встретим оператор ИЛИ
(объект OrQuery), то достанем NameQuery из стека и присоединим его к OrQuery в качестве левого операнда.
Объект OrQuery неполон: в нем не хватает правого операнда. До тех пор пока этот операнд не будет построен, работу с данным объектом придется прекратить.
Его можно поместить в тот же самый стек, что и NameQuery. Однако OrQuery представляет другое состояние обработки запроса: это неполный оператор. Поэтому мы определим два стека: _query_stack для хранения объектов, представляющих сконструированные операнды составного запроса (туда мы помещаем объект NameQuery), а второй для хранения неполных операторов с отсутствующим правым операндом.
Второй стек можно трактовать как место для хранения текущей операции, подлежащей завершению, поэтому назовем его _current_op. Сюда мы и поместим объект OrQuery.
После того как второй объект NameQuery будет определен, мы достанем объект OrQuery из стека _current_op и добавим к нему NameQuery в качестве правого операнда. Теперь объект OrQuery завершен и мы можем поместить его в стек _query_stack.
Если обработка запроса завершилась нормально, то стек _current_op пуст, а в стеке
_query_stack содержится единственный объект, который и представляет весь пользовательский запрос. В нашем случае это объект класса OrQuery.
Рассмотрим несколько примеров. Первый из них – простой запрос типа NotQuery:
! daddy
Ниже показана трассировка его обработки. Финальным объектом в стеке _query_stack является объект класса NotQuery:
OrQuery
NameQuery( "fiery" )

С++ для начинающих
913
push NotQuery on _query_stack
Текст, расположенный с отступом под функциями eval, показывает, как выполняется операция.
Во втором примере – составном запросе типа OrQuery – встречаются оба случая. Здесь же иллюстрируется помещение полного оператора в стек _query_stack:
==> fiery || untamed || shyly evalWord() : fiery push word on _query_stack evalOr() : incomplete! pop _query_stack : fiery add operand : WordQuery : OrQuery incomplete! push OrQuery on _current_op ( size == 1 ) evalWord() : untamed pop _current_op : OrQuery add operand : WordQuery : OrQuery complete! push OrQuery on _query_stack evalOr() : incomplete! pop _query_stack : OrQuery add operand : OrQuery : OrQuery incomplete! push OrQuery on _current_op ( size == 1 ) evalWord() : shyly pop _current_op : OrQuery add operand : WordQuery : OrQuery complete! push OrQuery on _query_stack
В последнем примере рассматривается составной запрос и применение скобок для изменения порядка вычислений:
==> fiery && ( bird || untamed ) evalWord() : fiery push word on _query_stack evalAnd() : incomplete! pop _query_stack : fiery add operand : WordQuery : AndQuery incomplete! push AndQuery on _current_op ( size == 1 ) evalWord() : bird
_paren is set to 1 push word on _query_stack evalOr() : incomplete! pop _query_stack : bird add operand : WordQuery : OrQuery incomplete! push OrQuery on _current_op ( size == 2 ) evalWord() : untamed pop _current_op : OrQuery add operand : WordQuery : OrQuery complete! push OrQuery on _query_stack evalRParen() :
_paren: 0 _current_op.size(): 1 pop _query_stack : OrQuery pop _current_op : AndQuery add operand : OrQuery : AndQuery complete! push AndQuery on _query_stack
Реализация системы текстового поиска состоит из трех компонентов: evalNot() : incomplete! push on _current_op ( size == 1 ) evalWord() : daddy pop _current_op : NotQuery add operand: WordQuery : NotQuery complete!

С++ для начинающих
914
•
класс TextQuery, где производится обработка текста (подробно он рассматривался в разделе 16.4). Для него нет производных классов;
•
объектно-ориентированная иерархия Query для представления и обработки различных типов запросов;
•
класс UserQuery, с помощью которого представлен конечный автомат для построения иерархии Query.
До настоящего момента мы реализовали эти три компонента практически независимо друг от друга и без каких бы то ни было конфликтов. Но, к сожалению, иерархия классов Query не поддерживает требований к конструированию объектов, предъявляемых реализацией UserQuery:
•
классы AndQuery, OrQuery и NotQuery требуют, чтобы каждый операнд присутствовал в момент определения объекта. Однако принятая нами схема обработки подразумевает наличие неполных объектов;
•
наша схема предполагает отложенное добавление операнда к объектам AndQuery,
OrQuery и NotQuery. Более того, такая операция должна быть виртуальной. Операнд приходится добавлять через указатель типа Query*, находящийся в стеке
_current_op
. Однако способ добавления операнда зависит от типа: для унарных
(NotQuery) и бинарных (AndQuery и OrQuery) операций он различен. Наша иерархия классов Query подобные операции не поддерживает.
Оказалось, что анализ предметной области был неполон, в результате чего разработанный интерфейс не согласуется с конкретной реализацией проекта. Нельзя сказать, что анализ был неправильным, он просто неполон. Эта проблема связана с тем, что этапы анализа, проектирования и реализации отделены друг от друга и не допускают обратной связи и пересмотра. Но хотя мы не можем все продумать и все предвидеть, необходимо отличать неизбежные неправильные шаги от ошибок, обусловленных собственной невнимательностью или нехваткой времени.
В таком случае мы должны либо сами модифицировать иерархию классов Query, либо договориться, чтобы это сделали за нас. В данной ситуации мы, как авторы всей системы, сами изменим код, модифицировав конструкторы подтипов и включив виртуальную функцию-член add_op() для добавления операндов после определения оператора (мы покажем, как она применяется, чуть ниже, при рассмотрении функций evalRParen() и evalWord()
).
17.7.1.
Определение класса UserQuery
Объект класса UserQuery можно инициализировать указателем на вектор строк, представляющий запрос пользователя, или передать ему адрес этого вектора позже, с помощью функции-члена query(). Это позволяет использовать один объект для нескольких запросов. Фактическое построение иерархии классов Query выполняется функцией eval_query():

С++ для начинающих
915
while ( /* пользователь продолжает формулировать запросы */ );
Вот определение нашего класса UserQuery:
// определить объект, не имея запроса пользователя
UserQuery user_query; string text; vector query_text;
// обработать запросы пользователя do { while( cin >> text ) query_text.push_back( text );
// передать запрос объекту UserQuery user_query.query( &query_text );
// вычислить результат запроса и вернуть
// корень иерархии Query*
Query *query = user_query.eval_query();
}

С++ для начинающих
916
#endif
Обратите внимание, что два объявленных нами стека содержат указатели на объекты типа Query, а не сами объекты. Хотя правильное поведение обеспечивается обеими реализациями, хранение объектов значительно менее эффективно, поскольку каждый объект (и его операнды) должен быть почленно скопирован в стек (напомним, что операнды копируются виртуальной функцией clone()) только для того, чтобы вскоре быть уничтоженным. Если мы не собираемся модифицировать объекты, помещаемые в контейнер, то хранение указателей на них намного эффективнее.
Ниже показаны реализации различных встроенных операций eval. Операции evalAnd() и evalOr() выполняют следующие шаги. Сначала объект извлекается из стека
#ifndef USER_QUERY_H
#define USER_QUERY_H
#include
#include
#include

С++ для начинающих
917
_query_stack
(напомним, что для класса stack, определенного в стандартной библиотеке, это требует двух операций: top() для получения элемента и pop() для удаления его из стека). Затем из хипа выделяется память для объекта класса AndQuery или OrQuery, и указатель на него передается объекту, извлеченному из стека. Каждая операция передает объекту AndQuery или OrQuery счетчики левых или правых скобок, необходимые ему для вывода своего содержимого. И наконец неполный оператор помещается в стек _current_op:
}
Операция evalNot() работает следующим образом. В хипе создается новый объект класса NotQuery, которому передаются счетчики левых и правых скобок для правильного отображения содержимого. Затем неполный оператор помещается в стек _current_op:
} inline void
UserQuery:: evalAnd()
{
Query *pop = _query_stack.top(); _query_stack.pop();
AndQuery *pq = new AndQuery( pop ); if ( _lparenOn )
{ pq->lparen( _lparenOn ); _lparenOn = 0; } if ( _rparenOn )
{ pq->rparen( _rparenOn ); _rparenOn = 0; }
_current_op.push( pq );
} inline void
UserQuery:: evalOr()
{
Query *pop = _query_stack.top(); _query_stack.pop();
OrQuery *pq = new OrQuery( pop ); if ( _lparenOn )
{ pq->lparen( _lparenOn ); _lparenOn = 0; } if ( _rparenOn )
{ pq->rparen( _rparenOn ); _rparenOn = 0; }
_current_op.push( pq ); inline void
UserQuery:: evalNot()
{
NotQuery *pq = new NotQuery; if ( _lparenOn )
{ pq->lparen( _lparenOn ); _lparenOn = 0; } if ( _rparenOn )
{ pq->rparen( _rparenOn ); _rparenOn = 0; }
_current_op.push( pq );

С++ для начинающих
918
При обнаружении закрывающей скобки вызывается операция evalRParen(). Если число активных левых скобок больше числа элементов в стеке _current_op, то ничего не происходит. В противном случае выполняются следующие действия. Из стека
_query_stack извлекается текущий еще не присоединенный к оператору операнд, а из стека _current_op – текущий неполный оператор. Вызывается виртуальная функция add_op()
класса Query, которая их объединяет. И наконец полный оператор помещается в стек _query_stack:
}
Операция evalWord() выполняет следующие действия. Она ищет указанное слово в отображении _word_map взятых из файла слов на векторы позиций. Если слово найдено, берется его вектор позиций и в хипе посредством конструктора с двумя параметрами создается новый объект NameQuery. В противном случае объект порождается с помощью конструктора с одним параметром. Если число элементов в стеке _current_op меньше либо равно числу встреченных ранее скобок, то нет неполного оператора, ожидающего операнда типа NameQuery, поэтому новый объект помещается в стек _query_stack.
Иначе из стека _current_op извлекается неполный оператор, к которому с помощью виртуальной функции add_op() присоединяется операнд NameQuery, после чего ставший полным оператор помещается в стек _query_stack: inline void
UserQuery:: evalRParen()
{ if ( _paren < _current_op.size() )
{
Query *poperand = _query_stack.top();
_query_stack.pop();
Query *pop = _current_op.top();
_current_op.pop(); pop->add_op( poperand );
_query_stack.push( pop );
}

С++ для начинающих
919
}
Упражнение 17.21
Напишите деструктор, копирующий конструктор и копирующий оператор присваивания для класса UserQuery.
Упражнение 17.22
Напишите функции print() для класса UserQuery. Обоснуйте свой выбор того, что она выводит.
17.8.
Соберем все вместе
Функция main() для нашего приложения текстового поиска выглядит следующим образом:
}
Функция-член build_text_map() – это не что иное, как переименованная функция doit()
из раздела 6.14: inline void
UserQuery:: evalWord( const string &query )
{
NameQuery *pq; loc *ploc; if ( ! _word_map->count( query )) pq = new NameQuery( query ); else { ploc = ( *_word_map )[ query ]; pq = new NameQuery( query, *ploc );
} if ( _current_op.size() <= _paren )
_query_stack.push( pq ); else {
Query *pop = _current_op.top();
_current_op.pop(); pop->add_op( pq );
_query_stack.push( pop );
}
#include "TextQuery.h" int main()
{
TextQuery tq; tq.build_up_text(); tq.query_text();

С++ для начинающих
920
}
Функция-член query_text() заменяет одноименную функцию из раздела 6.14. В первоначальной реализации в ее обязанности входили прием запроса от пользователя и вывод ответа. Мы решили сохранить за query_text() эти задачи, но реализовать ее по- другому
19
:
19 Полный текст программы можно найти на FTP-сайте издательства Addison-
Wesley по адресу, указанному на задней стороне обложки. inline void
TextQuery:: build_text_map()
{ retrieve_text(); separate_words(); filter_text(); suffix_text(); strip_caps(); build_word_map();

С++ для начинающих