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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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


Примечания

[править | править код]
  1. Bauer, Friedrich Ludwig. Origins and Foundations of Computing. — Berlin: Springer, 2010. — P. 93. — 142 p. — ISBN 3642029922.