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

7. Скобки, которых нет

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

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

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

Авторы

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

8. СКОБКИ, КОТОРЫХ НЕТ


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


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


Например, инфиксное выражение со скобками:

2 * (3 - 2 * (1 + 3))

в нотации ПОЛИЗ будет выглядеть так:

2 3 2 1 3 + * - *

Но что значит в контексте рассматриваемого алгоритма "влиять на расстановку"? Это значит выполнять работу "демона" на входе в стек - "выталкивать и препятствовать выталкиванию" операций из стека. Причем открывающая скобка пусть препятствует выталкиванию, а закрывающая скобка выталкивает.

Рассмотрим подробнее.

№ДействиеСтек операций  Выражение в ПОЛИЗ
(Выходная последовательность)
1

Поместить операнд (2) в выходную последовательность.

Пуст

2

2

Занести операцию (*) в стек операций.

 *

2

3

Пропустить открывающую скобку.

 *

2

4

Занести операнд (3) в выходную последовательность.

 *

2 3

5

Поместить операцию (-) в вершину стека.


Примечание: Если бы не было открывающей скобки, то на этом шаге следовало бы вытолкнуть операцию (*) из стека и поместить её в выходную последовательность.

- *

2 3

6

Занести операнд (2) в выходную последовательность.

- *

2 3 2

7

Поместить операцию (*) в вершину стека.

* - *

2 3 2

8

Пропустить открывающую скобку.

* - *

2 3 2

9

Занести операнд (1) в выходную последовательность.

* - *

2 3 2 1

10

Поместить операцию (+) в вершину стека.

+ * - *

2 3 2 1

11

Занести операнд (3) в выходную последовательность.

+ * - *

2 3 2 1 3

12

Вытолкнуть операцию (+) из вершины стека и занести её в выходную последовательность.

* - *

2 3 2 1 3 +

13

Вытолкнуть операции (*) и (-) из стека и занести их в выходную последовательность.

*

2 3 2 1 3 + * -

14

Вытолкнуть операцию (*) из стека и занести её в выходную последовательность.

Пуст

2 3 2 1 3 + * - *  

 


То же на языке программирования 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())
                           {
                                  TToken topToken = Operations.back();

                                   if (topToken.GetType() == OpeningBracket)
                                      break;

                                   if (Priority(topToken) <= Priority(token))
                                      break;


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

                           Operations.push_back(token);
                    }
                    break;
             case OpeningBracket:
                    Operations.push_back(token);
                    break;
             case ClosingBracket:
                    {
                          while (!Operations.empty())
                          {
                                  TToken topToken = Operations.back();

                                  if (topToken.GetType() == OpeningBracket)
                                      break;


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


Решает ли алгоритм в таком виде поставленную задачу? Решает. Тревожит ли он нас теперь или нет? Тревожит.


Алгоритм, все же, малость усложнился. И если бы эта малость была последней, то и бог бы с ней. Но где гарантия, что впоследствии (при увеличении сложности обрабатываемых выражений) и количество разных видов токенов не увеличится? Не начнет ли он "пухнуть"? (Он уже и так чуток "припух".) И если число разных токенов увеличится, то как быть нам с ними?


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


В идеале алгоритм меняться вовсе не должен, должен оставаться "какой он есть" (а еще лучше - сокращаться), притом что его возможности по обработке разных токенов (допустим: корней любой степени, синусов, косинусов, логарифмов и т.д.) расширяются сколько угодно.


Это идеал или противоречие?

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


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