Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявный приоритет операций при этом не учитывается. Например: D:=((C-(B*L))+K)
Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему правилу:
если это открывающаяся скобка или переменная, то значение увеличивается на 1;
если знак операции или закрывающаяся скобка, то уменьшается на 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 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.