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

Алгоритм Рутисхаузера — один из ранних формальных алгоритмов разбора выражений со скобками, его особенностью является предположение о правильной скобочной структуре выражения, также алгоритмом не учитывается неявный приоритет операции . Впервые описан в 1951 году швейцарским математиком ( нем. ), был охарактеризован как «танцевальная процессия вокруг скобочных скал» .

Примеры

При обработке выражения: D:=((C-(B*L))+K)

алгоритм присваивает каждому символу из строки номер уровня по следующему правилу:

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

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

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

Шаги

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

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