Просмотр кода страницы Алгоритм Рутисхаузера

'''Алгоритм Рутисхаузера''' — один из ранних формальных [[алгоритм]]ов разбора выражений со скобками, его особенностью является предположение о [[Правильная скобочная последовательность|правильной скобочной структуре]] выражения, также алгоритмом не учитывается неявный [[приоритет операции]]. Впервые описан в [[1951 год в науке|1951 году]] швейцарским математиком {{нп2|Рутисхаузер, Хайнц|Хайнцем Рутисхаузером|de|Heinz Rutishauser}}, был охарактеризован как <cite>«танцевальная процессия вокруг скобочных скал»</cite><ref>{{книга
 |автор         = Bauer, Friedrich Ludwig
 |заглавие      = Origins and Foundations of Computing
 |ссылка        = https://archive.org/details/originsfoundatio00baue
 |издание       = 
 |место         = [[Берлин|Berlin]]
 |издательство  = [[Springer Science+Business Media|Springer]]
 |год           = 2010
 |pages         = [https://archive.org/details/originsfoundatio00baue/page/n100 93]
 |allpages      = 142
 |isbn          = 3642029922
}}</ref>.

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

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

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

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

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

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

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


== Примечания ==
{{Примечания}}
{{wikibooks|Реализации алгоритмов/Алгоритм Рутисхаузера|Алгоритм Рутисхаузера}}

{{rq|wikify|style|check}}

[[Категория:Синтаксический анализ]]