Алгоритм Рутисхаузера
Алгоритм Рутисхаузера является
одним из наиболее ранних алгоритмов разбора
выражений. Его особенностью является
предположение о полной скобочной
структуре выражения. Под полной
скобочной записью выражения понимается
запись, в которой порядок действий
задается расстановкой скобок.
Неявный приоритет операций при
этом не учитывается. Например:
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 до тех пор, пока во входной строке
не останется одна переменная, обозначающая
общий результат выражения.