10. "ЭТО ВАШ МАЛЬЧИК?... ДА, ОНИ У ВАС ВСЕ РАЗНЫЕ"
Вернемся к программе и попробуем теперь реализовать функцию NeedPop. Задача этой функции - сравнить два токена (текущий и тот, что находится на вершине стека) и решить, следует ли токен из вершины стека удалить.
Если бы речь шла только о сортировке операций, то реализация была бы простой:
Получить приоритет операции, находящей на вершине стека.
Получить приоритет текущей операции.
Сравнить приоритеты.
Если приоритет текущей операции меньше приоритета операции из вершины стека, то следует вытолкнуть токен из вершины стека.
В противном случае - трогать вершину стека не надо.
Но у нас в системе присутствуют очень разные "сущности" (типы токенов) и мы исходим из того, что их количество и разнообразие будет возрастать. Функция NeedPop обрабатывает вместе с операциями и операнды, и круглые скобки, и конец последовательности.
Рассмотрим ситуацию, когда текущий токен является операндом. (Напомним, что противоположной ситуации - когда на вершине стека находится операнд, а текущий токен является операцией - не может получиться, т.к. операнды никогда не помещаются в стек.)
Если текущий токен является операндом, то функция NeedPop должна вернуть false, независимо от того, какая операция находится на вершине стека. Чтобы добиться такого эффекта, любому операнду будем сопоставлять гарантированно самый высокий приоритет. Если приоритеты представлены типом int, то максимальный приоритет будет задан константой INT_MAX.
Если текущий токен является концом последовательности, из стека один за одним нужно вытолкнуть все токены. Это означает, что приоритет конца последовательности должен быть гарантированно самым минимальным. Для типа int минимальное значение представлено константой INT_MIN.
Далее следует рассмотреть ситуации, когда текущий токен является скобкой. Наиболее интересный случай получается, когда текущий токен является открывающей скобкой. Оставим его на потом и начнём с закрывающей скобки.
Если текущий токен является закрывающей скобкой, то из стека нужно последовательно вытолкнуть все токены вплоть до открывающей скобки (и её тоже). Этого можно достичь, если назначить закрывающей скобке самый низкий приоритет (разве что только у конца последовательности приоритет может быть ниже). Например, в качестве значения приоритета выберем (-1).
Зададим приоритеты операциям + - * / : 1,2,3,4 соответственно.
Получим:
Кто | Приоритет |
| Конец последовательности | INT_MIN |
| Закрывающая скобка | - 1 |
| + | 1 |
| - | 2 |
| * | 3 |
| / | 4 |
| Операнд | INT_MAX |
Но куда мы вставим открывающую скобку? Чтобы правильно обрабатывать выражения со скобками, открывающую скобку нужно помещать в стек. Это означает, что приоритет у открывающей скобки должен быть больше, чем у самой приоритетной арифметической операции - деления. Если у операции деления приоритет равен 4, то у открывающей скобки он должен быть равен, например, 5.
То есть, на первый взгляд, получается так:
| Кто | Приоритет |
| Конец последовательности | INT_MIN |
| Закрывающая скобка | - 1 |
| + | 1 |
| - | 2 |
| * | 3 |
| / | 4 |
| Открывающая скобка | 5 |
| Операнд | INT_MAX |
Но, с другой стороны, открывающая скобка, находящаяся на вершине стека, не должна извлекаться из него, если текущий токен является одной из четырёх арифметических операций.
Это означает, что приоритет у открывающей скобки (на вершине стека) должен быть меньше, чем у самой низко приоритетной арифметической операции - сложения. Если приоритет сложения равен 1, то у открывающей скобки (на вершине стека) он должен быть равен 0.
То есть, на второй взгляд, получается так:
| Кто | Приоритет |
| Конец последовательности | INT_MIN |
| Закрывающая скобка | -1 |
| Открывающая скобка | 0 |
| + | 1 |
| - | 2 |
| * | 3 |
| / | 4 |
| Операнд | INT_MAX |
Сформулируем Противоречие 4:
"Открывающая скобка должна быть приоритетнее операции деления (самой высоко приоритетной операции), чтобы её можно было помещать в стек,
И
она же должна быть менее приоритетна операции сложения (самой низко приоритетной операции), чтобы после неё можно было помещать в стек любые арифметические операции".
"От жажды умираю над ручьем, смеюсь от горя и от счастья плачу" (Фр. Вийон)
Разрешим Противоречие 4 объединением противоречивых требований (сделаем И так, И так). Для этого перейдем от системы с одним приоритетом к надсистеме с двумя приоритетами.
Это можно сделать, определив, что на приоритет влияет не только тип токена, но и его положение в операции сравнения:
- Если операнд передаётся в качестве первого параметра функции NeedPop (это свидетельствует о том, что операнд находится на вершине стека операций), то он будет иметь один приоритет.
- Если же операнд передаётся в качестве второго параметра функции NeedPop (это говорит о том, что данный операнд только что прочитан из входной последовательности), то он будет иметь совсем другой приоритет.
| Кто | Приоритет
(для 1-го параметра) | Приоритет
(для 2-го параметра) |
| Конец последовательности | INT_MIN | INT_MIN |
| Закрывающая скобка | - 1 | - 1 |
| + | 1 | 1 |
| - | 2 | 2 |
| * | 3 | 3 |
| / | 4 | 4 |
| Открывающая скобка | 0 | 5 |
| Операнд | INT_MAX | INT_MAX |
Как это реализовать в коде?
enum TTokenType // Это наш справочник типов токенов
{
| eTokenOperand = 0, | // операнд |
| eTokenPlus, | // операция сложение |
| eTokenMinus, | // операция вычитание |
| eTokenMultiply, | // операция умножение |
| eTokenDivide, | // операция деление |
| eTokenOpeningBracket, | // открывающая скобка |
| eTokenClosingBracket, | // закрывающая скобка |
| eTokenEndOfSequence, | // конец последовательности |
| eTokenTypeCount | // количество значений токенов |
};
int g_iPriorities[eTokenTypeCount][2] = // Учитываем приоритеты
{
| { | INT_MAX, | INT_MAX | }, | // приоритет операнда |
| { | 1, | 1 | }, | // приоритет сложения |
| { | 2, | 2 | }, | // приоритет вычитания |
| { | 3, | 3 | }, | // приоритет умножения |
| { | 4, | 4 | }, | // приоритет деления |
| { | 0, | 5 | }, | // приоритет открывающей скобки |
| { | -1, | -1 | }, | // приоритет закрывающей скобки |
| { | INT_MIN, | INT_MIN | } | // приоритет конца последовательности |
};
bool NeedPop(const TToken & rToken1, const TToken & rToken2)
{
assert(rToken1.GetType() < eTokenTypeCount);
assert(rToken2.GetType() < eTokenTypeCount);
return g_iPriorities[rToken1.GetType()][0] >
g_iPriorities[rToken2.GetType()][1];
}
Учитывая, что "assert" - это макрос проверки условия и обработки ошибок, тело функции NeedPop - это (как и в предыдущем случае с функцией WhereToPut) вновь всего лишь строка "Возьми из таблицы":
return g_iPriorities[rToken1.GetType()];//Возьми приоритет из таблицы g_iPrioriies[]
Далее....
СОГЛАСЕН С ОБРАБОТКОЙ ЛИЧНЫХ ДАННЫХ