Алгоритм Рутисхаузера
Перейти к навигации
Перейти к поиску
Алгоритм Рутисхаузера — один из ранних формальных алгоритмов разбора выражений со скобками, его особенностью является предположение о правильной скобочной структуре выражения, также алгоритмом не учитывается неявный приоритет операции. Впервые описан в 1951 году швейцарским математиком Хайнцем Рутисхаузером (нем. Heinz Rutishauser), был охарактеризован как «танцевальная процессия вокруг скобочных скал»[1].
Примеры
[править | править код]При обработке выражения:
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 до тех пор, пока во входной строке не останется одна переменная, обозначающая общий результат выражения.
Примечания
[править | править код]- ↑ Bauer, Friedrich Ludwig. Origins and Foundations of Computing. — Berlin: Springer, 2010. — P. 93. — 142 p. — ISBN 3642029922.
Для улучшения этой статьи желательно:
|