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

       

Управляющий класс UserQuery


Если имеется запрос такого типа:

fiery && ( bird || potato )

то в нашу задачу входит построение эквивалентной иерархии классов:

AndQuery

   NameQuery( "fiery" )

   OrQuery

      NameQuery( "bird" )

      NameQuery( "potato" )

Как лучше всего это сделать? Процедура вычисления ответа на запрос напоминает функционирование конечного автомата. Мы начинаем с пустого состояния и при обработке каждого элемента запроса переходим в новое состояние, пока весь запрос не будет разобран. В основе нашей реализации лежит одна инструкция switch внутри операции, которую мы назвали eval_query(). Слова запроса считываются одно за другим из вектора строк и сравниваются с каждым из возможных значений:

vector<string>::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;

            }

Пять операций eval: evalWord(), evalAnd(), evalOr(), evalNot и evalRParen() – как раз и строят иерархию классов Query. Прежде чем обратиться к деталям их реализации, рассмотрим общую организацию программы.

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


В разделе 6. 14 мы ввели класс TextQuery, где инкапсулировали операции и данные, изучавшиеся в главе 6. Здесь нам потребуется класс UserQuery, решающий аналогичные задачи.

Одним из членов этого класса должен быть вектор строк, содержащий сам запрос пользователя. Другой член – это указатель типа Query* на иерархическое представление запроса, построенное в eval_query(). Еще три члена служат для обработки скобок:

  • _paren помогает изменить подразумеваемый порядок вычисления операторов (чуть позже мы продемонстрируем это на примере);


  • _lparenOn и _rparenOn содержат счетчики левых и правых скобок, ассоциированные с текущим узлом дерева разбора запроса (мы показывали, как они используются, при обсуждении виртуальной функции print() в разделе 17.5.1).


  • Помимо этих пяти членов, нам понадобятся еще два. Рассмотрим следующий запрос:

    fiery || untamed

    Наша цель – представить его в виде следующего объекта OrQuery:

    OrQuery

       NameQuery( "fiery" )

       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:

    evalNot() : incomplete!

          push on _current_op ( size == 1 )

    evalWord() : daddy

          pop _current_op : NotQuery

          add operand: WordQuery : NotQuery complete!

          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

    Реализация системы текстового поиска состоит из трех компонентов:

  • класс 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()).


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