Алгоритм Рутисхаузера
Материал из Википедии — свободной энциклопедии
Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявное старшинство операций при этом не учитывается. Например: D:=((C-(B*L))+K)
Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему пpавилу:
- если это откpывающаяся скобка или пеpеменная, то значение увеличивается на 1;
- если знак опеpации или закpывающаяся скобка, то уменьшается на 1.
Для выражения (А+(В+С)) присваивание значений уровня будет происходить следующим образом :
| N симв. | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| Символы строки | ( | A | + | ( | B | * | C | ) | ) |
| Номера уровней | 1 | 2 | 1 | 2 | 3 | 2 | 3 | 2 | 1 |
Алгоритм складывается из следующих шагов:
- выполнить расстановку уровней;
- выполнить поиск элементов строки с максимальным значением уровня;
- выделить тройку — два операнда с максимальным значением уровня и операцию, которая заключена между ними;
- результат вычисления тройки обозначить вспомогательной переменной;
- из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;
- выполнять п.п.2 — 5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.
