RRRRR - 54.197.66.254

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

Скрыть / Показать Сортировать по дате
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;
       }
}



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


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


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


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


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


Далее...

Уважаемые Коллеги!

Если Вам нравится наш Форум, Вы можете поддержать его, отправив любую сумму (тогда выберите опцию "Спасибо за Форум").

Вы также можете поддержать конкретное обсуждение и получить гарантированный ответ от наших специалистов (тогда выберите опцию "Прошу эксперта ответить в этой теме").
Задайте Ваш вопрос здесь.

Большое Спасибо!


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