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