3. Как сразу выйти на лучшее?

2010-01-22 15:00:39

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

3. КАК СРАЗУ ВЫЙТИ НА ЛУЧШЕЕ?

Рассмотрим простейшее арифметическое выражение: 3 + 5. В чём состоит основная трудность его интерпретации? Как будет осуществляться его разбор?

- Сначала из входной последовательности токенов будет считан операнд ’3’. Его легко запомнить, поместив в стек.

- За ним будет прочитан знак операции ’+’. Если бы на момент прочтения оператора ’+’ были бы известны оба операнда (3 и 5), мы могли бы посчитать значение выражения. Но поскольку второй операнд (5) ещё не прочитан, то знак операции приходится запоминать в отдельной переменной.

- После операции вновь следует операнд. На этот раз - (5).

Итак, основная трудность при разборе простейшего арифметического выражения заключается в том, что на момент считывания операции ещё неизвестны все её операнды.

Сформулируем требования к идеальному решению:

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

Это означает, что операнды должны стоять раньше операций.

Например, так: 3 5 +

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

Строго говоря, для того чтобы

у тех, кто знает, "и так известное" вспоминалось в момент проектирования, а не постфактум,
те, кто не знает, сами "открывали" (описывали) то, что требуется;
"и те, и другие" создавали новое, когда "и так известного" не хватает,

используются: формулировка задач в виде противоречий и описание идеального решения.

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

Пусть подумают. Те из них, кто "переизобретет" инверсную запись, квалифицированно запомнят ее на уровне деятельности, а не просто вызубрят.

Как известно, алгоритм интерпретации арифметических выражений в нотации ПОЛИЗ сводится к циклу, состоящему из трёх действий:

1. Получить токен из входной последовательности.

2. Если токен является операндом, то поместить его в стек.

3. Если токен является операцией, то извлечь из стека нужное количество операндов, выполнить над ними операцию, а результат - обратно поместить в стек.

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

std::vector<double> Stack;
TToken token;

while (GetToken(&token))
{
        switch (token.GetType())
        {
                case eTokenOperand: //Операнд
                        Stack.push_back(token.GetOperand());
                        break;
                case eTokenPlus: //Плюс
                        {
                                 double fltArg2 = Stack.back();
                                 Stack.pop_back();
                                 double fltArg1 = Stack.back();
                                 Stack.pop_back();
                                 Stack.push_back(fltArg1 + fltArg2);
                        }
                       break;
                case eTokenMinus: //Минус
                        {
                                 double fltArg2 = Stack.back();
                                 Stack.pop_back();
                                 double fltArg1 = Stack.back();
                                 Stack.pop_back();
                                 Stack.push_back(fltArg1 - fltArg2);
                        }
                       break;
                case eTokenMultiply: //Умножить
                        {
                                 double fltArg2 = Stack.back();
                                 Stack.pop_back();
                                 double fltArg1 = Stack.back();
                                 Stack.pop_back();
                                 Stack.push_back(fltArg1 * fltArg2);
                        }
                       break;
                case eTokenDivide: //Разделить
                        {
                                 double fltArg2 = Stack.back();
                                 Stack.pop_back();
                                 double fltArg1 = Stack.back();
                                 Stack.pop_back();
                                 Stack.push_back(fltArg1 / fltArg2);
                        }
                       break;
        }
}

Как видим, на первый взгляд, алгоритм интерпретации арифметических выражений в нотации ПОЛИЗ несложен:

1) он не требует отдельных массивов и переменных для хранения операндов и результатов операций - все операнды и результаты помещаются в стек;

2) вычисления производятся при обработке операции - все необходимые для этого данные уже находятся в стеке;

3) при всей простоте, алгоритм подходит для интерпретации достаточно сложных выражений.

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

Далее...

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

TRIZ-RI Group

Нужна готовая система расчета зарплаты для программистов IT-отдела

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

Авторы

TRIZ-RI Group

Как управлять торговой компанией?