6. Что мы скажем о будущем позавчера. Новое противоречие

2010-01-22 15:03:11

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

6.0 ЧТО МЫ СКАЖЕМ О БУДУЩЕМ ПОЗАВЧЕРА. НОВОЕ ПРОТИВОРЕЧИЕ

Нетрудно заметить, что, описывая образ идеального решения, мы не учли приоритеты операций.

Последнее решение верно только для операций одинакового приоритета: только для плюсов, только для минусов, только для умножений или только для делений, но не для смешанных ситуаций, в которых, как известно, операция вычитание имеет приоритет над операцией сложение, а операция деление имеет приоритет над операциями умножение, вычитание и сложение.

Например, для инфиксного выражения:

5 * 3 + 7 (должно получиться 22)

алгоритм сформирует такую запись ПОЛИЗ:

5 3 7 + *

А это означает, что сначала будет выполнена операция: 3 + 7 и только затем результат её выполнения будет умножен на 5. И получится 50, а не 22.

Так что, получается: некоторые выражения будут вычисляться правильно, а другие - нет.

Или рассмотрим два выражения:

5 * 3 + 7

5 + 3 * 7

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

5 3 * 7 +

5 3 7 * +

В первом случае, первая операция (’*’) в польской записи следует раньше второй (’+’), а во втором случае - наоборот, операция (’+’) хоть и первая, но в записи следует после второй (’*’). Т.е. в одном случае, при переводе в ПОЛИЗ, порядок операций должен меняться на противоположный, а в другом случае - нет.

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

"При переводе арифметического выражения из инфиксной нотации в нотацию ПОЛИЗ, операция, которая следует раньше, должна следовать позже, и в то же самое время операция, которая следует раньше, должна следовать раньше (т.е. оставаться на своём месте)".

Конкретизируем:

"Порядок операций при преобразовании в ПОЛИЗ должен меняться на противоположный, чтобы можно было правильно вычислять выражение 5 + 3 * 7, и не должен меняться на противоположный, чтобы можно было правильно вычислять выражение 5 * 3 + 5".

Противоречия типа "Раньше - Позже" устраняются, если учитывать приоритеты операций. Т.к. в нотации ПОЛИЗ у операций нет приоритетов, а порядок их выполнения задаётся лишь порядком следования в выражении, то операция, имеющая больший приоритет, должна записываться раньше.

Внесем поправки в описание идеального решения:

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

Методическое отступление: "Здесь опытный Читатель разглядит алгоритм Дейкстры "Сортировочная станция". Но преподавателям программирования мы бы вновь порекомендовали поменять местами "раньше и позже" и предоставить студентам возможность "переизобрести" алгоритм Дейкстры, например, предложив им описать идеальное решение: сначала Противоречия 1, затем Противоречия 2.

На языке программирования C++ этот алгоритм (в несколько усечённом виде) будет выглядеть так (изменения выделены):

TParser Input;
std::vector<TToken> Output;
std::vector<TToken> Operations;
TToken token;

int Priority(const TToken & rToken);

while (Input.GetToken(&token))
{
       switch (token.GetType())
       {
              case Operand:
                    Output.push_back(token);
                    break;
              case Operation:
                     {
                            while (!Operations.empty())
                            {
                                   if (Priority(Operations.Top()) <= Priority(token))
                                       break;

                                  Output.push_back(Operations.back());
                                  Operations.pop_back();
                            }

                            Operations.push_back(token);
                     }
                     break;
              case EndOfSequence:
                     {
                           while (!Operations.empty())
                           {
                                 Output.push_back(Operations.back());
                                 Operations.pop_back();
                           }
                     }
                     break;
       }
}

int Priority(const TToken & rToken)
{
     switch (rToken.GetOperationCode())
     {
            case ’+’:
                   return 1;
            case ’-’:
                   return 2;
            case ’*’:
                   return 3;
            case ’/’:
                   return 4;
     }

return 0;

}

Проведём анализ решения. Удовлетворяет ли оно условиям задачи? Строго говоря, да. Несмотря на то, что разработанный алгоритм не поддерживает выражения со скобками, он не ограничивается обработкой лишь простых выражений. Допустимы выражения любой сложности с произвольным количеством операций.

Но перейдем к скобкам.

Далее...

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

TRIZ-RI Group

Бизнес-образование по-европейски в Праге

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

Авторы

TRIZ-RI Group

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