Алгоритм Рутисхаузера

Для улучшения этой статьи желательно?: Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное. Викифицировать статью. Проставить интервики в рамках проекта Интервики.

Алгоритм Рутисхаузера является одним из наиболее ранних алгоритмов разбора выражений^{[источник не указан 54 дня]}. Его особенностью является предположение о полной скобочной структуре выражения. Под полной скобочной записью выражения понимается запись, в которой порядок действий задается расстановкой скобок. Неявный приоритет операции при этом не учитывается. Например: D:=((C-(B*L))+K)

Обрабатывая выражение с полной скобочной структурой, алгоритм присваивает каждому символу из строки номер уровня по следующему правилу:

1. если это открывающаяся скобка или переменная, то значение увеличивается на 1;
2. если знак операции или закрывающаяся скобка, то уменьшается на 1.

Для выражения (А+(В*С)) присваивание значений уровня будет происходить следующим образом:

Номер символа	1	2	3	4	5	6	7	8	9
Символы строки	(	A	$+$	(	B	*	C	)	)
Номера уровней	1	2	1	2	3	2	3	2	1

Алгоритм складывается из следующих шагов:

1. выполнить расстановку уровней;
2. выполнить поиск элементов строки с максимальным значением уровня;
3. выделить тройку — два операнда с максимальным значением уровня и операцию, которая заключена между ними;
4. результат вычисления тройки обозначить вспомогательной переменной;
5. из исходной строки удалить выделенную тройку вместе с ее скобками, а на ее место поместить вспомогательную переменную, обозначающую результат, со значением уровня на единицу меньше, чем у выделенной тройки;
6. выполнять 2-5 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.