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;
}
}
Решает ли алгоритм в таком виде поставленную задачу? Решает. Тревожит ли он нас теперь или нет? Тревожит.
Алгоритм, все же, малость усложнился. И если бы эта малость была последней, то и бог бы с ней. Но где гарантия, что впоследствии (при увеличении сложности обрабатываемых выражений) и количество разных видов токенов не увеличится? Не начнет ли он "пухнуть"? (Он уже и так чуток "припух".) И если число разных токенов увеличится, то как быть нам с ними?
И у нас ведь есть требование к идеальной программе: увеличение функциональности не должно приводить к разрастанию кода.
В идеале алгоритм меняться вовсе не должен, должен оставаться "какой он есть" (а еще лучше - сокращаться), притом что его возможности по обработке разных токенов (допустим: корней любой степени, синусов, косинусов, логарифмов и т.д.) расширяются сколько угодно.
Это идеал или противоречие?
Далее...