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

2010-01-22 15:04:25

Сычев С.В., Лебедев К.А. [sch@triz-ri.ru; askofen@mail.ru] » Всем

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

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

Далее...

[Нет ответов на это сообщение]

TRIZ-RI Group

Как платить зарплату супервайзеру, мерчандайзеру, торгпреду?

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

Авторы

TRIZ-RI Group

Интересует кейс для активных продаж