На сайте ведутся работы 8. Освободим "узников оператора IF" | ТРИЗ - РТВ - ТРТЛ | Бизнес-форум TRIZ-RI
9737
СОГЛАСЕН С ОБРАБОТКОЙ ЛИЧНЫХ ДАННЫХ
Все категории » ТРИЗ - РТВ - ТРТЛ » С.В. Сычев, К.А. Лебедев "Не только про калькулятор"

8. Освободим "узников оператора IF"

Ваши данные (просмотреть)
в избранные темы
Политика конфиденциальности

Обсуждения-аналоги

Скрыть / Показать Сортировать по дате
Создать аналогичное обсуждение...

Авторы

Скрыть / Показать
2010-01-22 15:04:25
Сычев С.В., Лебедев К.А. » Всем

8. ОСВОБОДИМ "УЗНИКОВ ОПЕРАТОРА IF"


Итак, предположительное "распухание" алгоритма обусловлено появлением новых токенов и правил их обработки.


Сформулируем Противоречие 3:

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

Получилось противоречие типа "Много - Мало". (Этот тип противоречия был рассмотрен нами в статье "Как вспомнить "и так известное".)

Чтобы разрешить такое противоречие, нужно абстрагироваться от различных видов токенов (операндов, операций, скобок, запятых, функций и т.п.), которые и вызывают эффект "разбегания специфики". И еще радикальнее: надо вообще перестать думать в объектных категориях. Об этом мы писали ранее в статье "Освобождение узников оператора IF".


В самом деле, вольно или невольно, все эти токены мы понимали до этого момента, как разные объекты, которые надо "обработать". А, собственно говоря, почему?


Изменим точку зрения, забудем об объектах и спросим себя: "Какие функции нам нужны?"


Таковых всего три:

1. Функция указателя, которая сообщает, куда пойти токену: в "выходную последовательность", в "стек" или в "никуда". Назовем ее "WhereToPut" ("Женщина, Вам сюда!")


2. Первая функция "демона", которая определяет, нужно ли выталкивать из стека текущую вершину. Назовем ее "NeedPop" ("Мальчик, на выход - мама пришла").


3. Вторая функция "демона", которая определяет, до каких пределов нам нужно извлекать операции из вершины стека и заносить их в выходную последовательность. Назовем ее  "BreakNow" ("Стоп, дети, не все мамы пришли!").


Знания об этих трёх функциях достаточно для того, чтобы написать обобщённый код.

Приводим его на языке программирования C++ без обработки ошибок:


int  WhereToPut(const TToken & rToken);
bool NeedPop(const TToken & rToken1, const TToken & rToken2);
bool BreakNow(const TToken & rToken1, const TToken & rToken2);

do
{
       Token = Input.GetToken();


        while (!Operations.empty())
        {
      
             // Получаем токен из вершины стека
            TToken topToken = Operations.back();

       
             // Выталкиваем токен из вершины стека, если надо
             if (NeedPop(topToken, Token))
                 Operations.pop_back();

             if (BreakNow(topToken, Token))
                 break;

            Output.push_back(topToken);
        }

   
       switch (WhereToPut(Token))
        {
             case eOutputSequence:
                   Output.push_back(Token);
                   break;
             case eOperationStack:
                    Operations.push_back(Token);
                    break;
        }
}
while (Token.GetType() != eTokenEndOfSequence);


Т.о., вся основная логика данного алгоритма инкапсулирована в трёх функциях:

  • WhereToPut
  • NeedPop
  • BreakNow

Какова должна быть их реализация, чтобы алгоритм мог корректно обрабатывать инфиксные выражения со скобками и не только? Рассмотрим каждую функцию.

Далее...
Ответить Сообщение для всех [Нет ответов на это сообщение]


Яндекс.Метрика