НА ГЛАВНУЮ
Меню сайта
Категория
Ghost++ [1]
С++ [55]
Развлечение
ON - LINE
Опрос
Что лепим морфу первым артом?
Всего ответов: 363
Оbserver Ward

Онлайн всего: 1
Гостей: 1
Пользователей: 0


Друзья сайта
Заведи себе Бота
Hаша кнопка
Для обмена банерами , наша кнопка для размещения у вас на сайте

Клансайт USSR


Главная » Статьи » Программирование » С++

17. Наследование и подтипизация классов (4)
17.7.1. Определение класса UserQuery

Объект класса UserQuery можно инициализировать указателем на вектор строк, представляющий запрос пользователя, или передать ему адрес этого вектора позже, с помощью функции-члена query(). Это позволяет использовать один объект для нескольких запросов. Фактическое построение иерархии классов Query выполняется функцией eval_query():

// определить объект, не имея запроса пользователя
UserQuery user_query;

string text;
vector<string> query_text;

// обработать запросы пользователя
do {
   while( cin > >  text )
       query_text.push_back( text );

   // передать запрос объекту UserQuery
   user_query.query( &query_text );

   // вычислить результат запроса и вернуть
   // корень иерархии Query*
   Query *query = user_query.eval_query();
}

while ( /* пользователь продолжает формулировать запросы */ );

Вот определение нашего класса UserQuery:

#ifndef USER_QUERY_H
#define USER_QUERY_H

#include <string>
#include <vector>
#include <map>
#include <stack>

typedef pair<short,short>            location;
typedef vector<location,allocator> loc;

#include quot;Query.h"t;

class UserQuery {
public:
    UserQuery( vector< string,allocator >  *pquery = 0 )
        :  _query( pquery ), _eval( 0 ), _paren( 0 ) {}

    Query *eval_query();      // строит иерархию
    void   query( vector< string,allocator >  *pq );
    void   displayQuery();    

    static void word_map( map<string,loc*,less<string>,allocator> *pwm ) {
        if ( !_word_map ) _word_map = pwm;
    }

private:
    enum QueryType { WORD = 1, AND, OR, NOT, RPAREN, LPAREN };

    QueryType evalQueryString( const string &query );
    void      evalWord( const string &query );
    void         evalAnd();
    void         evalOr();
    void         evalNot();
    void         evalRParen();
    bool         integrity_check();
    
    int             _paren;
    Query             *_eval;
    vector<string> *_query;

    stack<Query*, vector<Query*> > _query_stack;
    stack<Query*, vector<Query*> > _current_op;
     static short _lparenOn, _rparenOn;
     static map<string,loc*,less<string>,allocator> *_word_map;
};
#endif

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

Ниже показаны реализации различных встроенных операций eval. Операции evalAnd() и evalOr() выполняют следующие шаги. Сначала объект извлекается из стека _query_stack (напомним, что для класса stack, определенного в стандартной библиотеке, это требует двух операций: top() для получения элемента и pop() для удаления его из стека). Затем из хипа выделяется память для объекта класса AndQuery или OrQuery, и указатель на него передается объекту, извлеченному из стека. Каждая операция передает объекту AndQuery или OrQuery счетчики левых или правых скобок, необходимые ему для вывода своего содержимого. И наконец неполный оператор помещается в стек _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 );
}

Операция evalNot() работает следующим образом. В хипе создается новый объект класса NotQuery, которому передаются счетчики левых и правых скобок для правильного отображения содержимого. Затем неполный оператор помещается в стек _current_op:

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

При обнаружении закрывающей скобки вызывается операция evalRParen(). Если число активных левых скобок больше числа элементов в стеке _current_op, то ничего не происходит. В противном случае выполняются следующие действия. Из стека _query_stack извлекается текущий еще не присоединенный к оператору операнд, а из стека _current_op - текущий неполный оператор. Вызывается виртуальная функция add_op() класса Query, которая их объединяет. И наконец полный оператор помещается в стек _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 );
    }
}

Операция evalWord() выполняет следующие действия. Она ищет указанное слово в отображении _word_map взятых из файла слов на векторы позиций. Если слово найдено, берется его вектор позиций и в хипе посредством конструктора с двумя параметрами создается новый объект NameQuery. В противном случае объект порождается с помощью конструктора с одним параметром. Если число элементов в стеке _current_op меньше либо равно числу встреченных ранее скобок, то нет неполного оператора, ожидающего операнда типа NameQuery, поэтому новый объект помещается в стек _query_stack. Иначе из стека _current_op извлекается неполный оператор, к которому с помощью виртуальной функции add_op() присоединяется операнд NameQuery, после чего ставший полным оператор помещается в стек _query_stack:

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

Упражнение 17.21

Напишите деструктор, копирующий конструктор и копирующий оператор присваивания для класса UserQuery.

Упражнение 17.22

Напишите функции print() для класса UserQuery. Обоснуйте свой выбор того, что она выводит.
17.8. Соберем все вместе

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

#include "TextQuery.h"
int main()
{
   TextQuery tq;

   tq.build_up_text();
   tq.query_text();
}

Функция-член build_text_map() - это не что иное, как переименованная функция doit() из раздела 6.14:

inline void
TextQuery::
build_text_map()
{
   retrieve_text();
   separate_words();
   filter_text();
   suffix_text();
   strip_caps();
   build_word_map();
}

Функция-член query_text() заменяет одноименную функцию из раздела 6.14. В первоначальной реализации в ее обязанности входили прием запроса от пользователя и вывод ответа. Мы решили сохранить за query_text() эти задачи, но реализовать ее по-другому:

void
TextQuery::query_text()
{
    /* локальные объекты:
     *
     * text: содержит все слова запроса
     * query_text: вектор для хранения пользовательского запроса
     * caps: фильтр для поддержки преобразования
     * прописных букв в строчные
     *
     * user_query: объект UserQuery, в котором инкапсулировано
     *             собственно вычисление ответа на запрос
     */
    string text;
    string caps( "ABCDEFGHIJKLMNOPQRSTUVWXYZ" );
    vector<string, allocator> query_text;
    UserQuery user_query;

     // инициализировать статические члены UserQuery
    NotQuery::all_locs( text_locations->second );
    AndQuery::max_col( &line_cnt );
    UserQuery::word_map( word_map );

    do {
           // удалить предыдущий запрос, если он был
        query_text.clear();

           cout << "Введите запрос. Пожалуйста, разделяйте все его "

              << "элементы пробелами.\n"
                << "Запрос (или весь сеанс) завершается точкой ( . ).\n\n"
            << "==> ";
    
          /*
           * прочитать запрос из стандартного ввода,
           * преобразовать все заглавные буквы, после чего
           * упаковать его в query_text ...
           *
           * примечание: здесь производятся все действия по
           * обработке запроса, связанные собственно с текстом ...
           */
           while( cin >text )
           {
             if ( text == "." )
                  break;

             string::size_type pos = 0;
                while (( pos = text.find_first_of( caps, pos ))
                     != string::npos )
                          text[pos] = tolower( text[pos] );

             query_text.push_back( text );
           }

           // теперь у нас есть внутреннее представление запроса
           // обработаем его ...
           if ( ! query_text.empty() )
        {
                 // передать запрос объекту UserQuery
               user_query.query( &query_text );
                 // вычислить ответ на запрос
                 // вернуть иерархию Query*
                 // подробности см. в разделе 17.7

                 // query - это член класса TextQuery типа Query*
               query = user_query.eval_query();

                 // вычислить иерархию Query,
                 // реализация описана в разделе 17.7
               query->eval();

                 // вывести ответ с помощью
                 // функции-члена класса TextQuery
               display_solution();

                 // вывести на терминал пользователя дополнительную
                 // пустую строку
                cout << endl;
        }
        }
        while ( ! query_text.empty() );
        cout << "До свидания!\n";
}

Тестируя программу, мы применили ее к нескольким текстам. Первым стал короткий рассказ Германа Мелвилла "Bartleby”. Здесь иллюстрируется составной запрос AndQuery, для которого подходящие слова расположены в соседних строках. (Отметим, что слова, заключенные между символами косой черты, предполагаются набранными курсивом.)

Введите запрос. Пожалуйста, разделяйте все его элементы пробелами.

Запрос (или весь сеанс) завершается точкой ( . ).

==> John && Jacob && Astor
         john ( 3 ) lines match
         jacob ( 3 ) lines match
         john && jacob ( 3 ) lines match
         astor ( 3 ) lines match
         john && jacob && astor ( 5 ) lines match

Requested query: john && jacob && astor
( 34 ) All who know me consider me an eminently /safe/ man. The late
John Jacob
( 35 ) Astor, a personage little given to poethic enthusiasm, had no
hesitation in
( 38 ) my profession by the late John Jacob Astor, a name which, I admit
I love to
( 40 ) bullion. I will freely add that I was not insensible to the late
John Jacob
( 41 ) Astor's good opinion.

Следующий запрос, в котором тестируются скобки и составные операторы, обращен к тексту новеллы "Heart of Darkness" Джозефа Конрада:

==>horror || ( absurd && mystery ) || ( North && Pole )

         horror ( 5 ) lines match
         absurd ( 8 ) lines match
         mystery ( 12 ) lines match
         ( absurd && mystery ) ( 1 ) lines match
         horror || ( absurd && mystery ) ( 6 ) lines match
         north ( 2 ) lines match
         pole ( 7 ) lines match
         ( north && pole ) ( 1 ) lines match
         horror || ( absurd && mystery ) || ( north && pole )
                ( 7 ) lines match

Requested query: horror || ( absurd && mystery ) || ( north && pole )
( 257 ) up I will go there.' The North Pole was one of these
( 952 ) horros. The heavy pole had skinned his poor nose
( 3055 ) some lightless region of subtle horrors, where pure,
( 3673 ) " 'The horror! The horror!'
( 3913 ) the whispered cry, 'The horror! The horror! '
( 3957 ) absurd mysteries not fit for a human being to behold.
( 4088 ) wind. 'The horror! The horror!'

Последний запрос был обращен к отрывку из романа Генри Джеймса "Portrait of a Lady". В нем иллюстрируется составной запрос в применении к большому текстовому файлу:

==>clever && trick || devious
         clever ( 46 ) lines match
         trick ( 12 ) lines match
         clever && trick ( 2 ) lines match
         devious ( 1 ) lines match
         clever && trick || devious ( 3 ) lines match
Requested query: clever && trick || devious
( 13914 ) clever trick she had guessed. Isabel, as she herself grew older
( 13935 ) lost the desire to know this lady's clever trick. If she had
( 14974 ) desultory, so devious, so much the reverse of processional.
There were

Упражнение 17.23

Реализованная нами обработка запроса пользователя обладает одним недостатком: она не применяет к каждому слову те же предварительные фильтры, что и программа, строящая вектор позиций (см. разделы 6.9 и 6.10). Например, пользователь, который хочет найти слово "maps", обнаружит, что в нашем представлении текста распознается только "map”, поскольку существительные во множественном числе приводятся к форме в единственном числе. Модифицируйте функцию query_text() так, чтобы она применяла эквивалентные фильтры к словам запроса.

Упражнение 17.24

Поисковую систему можно было бы усовершенствовать, добавив еще одну разновидность запроса "И”, которую мы назовем InclusiveAndQuery и будем обозначать символом &. Строка текста удовлетворяет условиям запроса, если в ней находятся оба указанных слова, пусть даже не рядом. Например, строка

We were her pride of ten, she named us

удовлетворяет запросу:

pride & ten

но не:

pride && ten

Поддержите запрос InclusiveAndQuery.

Упражнение 17.25

Представленная ниже реализация функции display_solution() может выводить только в стандартный вывод. Более правильно было бы позволить пользователю самому задавать поток ostream, в который надо направить вывод. Модифицируйте display_solution() так, чтобы ostream можно было задавать. Какие еще изменения необходимо внести в определение класса UserQuery?

void TextQuery::
display_solution()
{
    cout << "\n"
         <<  "Requested query: "
         <<  *query <<  "\n\n";

    const set<short,less<short>,allocator> *solution = query->solution();
    
    if ( ! solution->size() ) {
         cout <<  "\n\t"
          <<  "Sorry, no matching lines were found in text.\n"
          <<  endl;
    }
    set<short>::const_iterator
        it = solution->begin(),
        end_it = solution->end();
    for ( ; it != end_it; ++it ) {
        int line = *it;
        // пронумеруем строки с 1 ...
        cout <<  "( " <<  line+1 << " ) "
             <<  (*lines_of_text)[line] <<  '\n';
    }
    cout <<  endl;
}

Упражнение 17.26

Нашему классу TextQuery не хватает возможности принимать аргументы, заданные пользователем в командной строке.

Предложите синтаксис командной строки для нашей поисковой системы.

Добавьте в класс необходимые данные и функции-члены.

Предложите средства для работы с командной строкой (см. пример в разделе 7.8).

Упражнение 17.27

В качестве темы для рабочего проекта рассмотрите следующие усовершенствования нашей поисковой системы:

Реализуйте поддержку, необходимую для представления запроса AndQuery в виде одной строки, например "Motion Picture Screen Cartoonists".

Реализуйте поддержку для ответа на запрос на основе вхождения слов не в строку, а в предложение.

Реализуйте подсистему хранения истории, с помощью которой пользователь мог бы ссылаться на предыдущий запрос по номеру, возможно, комбинируя его с новым запросом.

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

==> John && Jacob && Astor
(1)    john ( 3 ) lines match
(2)    jacob ( 3 ) lines match
(3)    john && jacob ( 3 ) lines match
(4)    astor ( 3 ) lines match
(5)    john && jacob && astor ( 5 ) lines match
// Новая возможность: пусть пользователь укажет, какой запрос выводить
// пользователь вводит число
==> вывести? 3
// Затем система спрашивает, сколько строк выводить
// при нажатии клавиши Enter выводятся все строки,
// но пользователь может также ввести номер одной строки или диапазон
сколько (Enter выводит все, иначе введите номер строки или диапазон) 1-3
Категория: С++ | Добавил: r2d2 (29.09.2011)
Просмотров: 693 | Рейтинг: 0.0/0
Всего комментариев: 0
Добавлять комментарии могут только зарегистрированные пользователи.
[ Регистрация | Вход ]
Born in Ussr
Залогиниться
Турниры

/j clan ussr /j clan cccp