Алгоритм Рутисхаузера
Поделись знанием:
Дома еще не спали. Молодежь дома Ростовых, воротившись из театра, поужинав, сидела у клавикорд. Как только Николай вошел в залу, его охватила та любовная, поэтическая атмосфера, которая царствовала в эту зиму в их доме и которая теперь, после предложения Долохова и бала Иогеля, казалось, еще более сгустилась, как воздух перед грозой, над Соней и Наташей. Соня и Наташа в голубых платьях, в которых они были в театре, хорошенькие и знающие это, счастливые, улыбаясь, стояли у клавикорд. Вера с Шиншиным играла в шахматы в гостиной. Старая графиня, ожидая сына и мужа, раскладывала пасьянс с старушкой дворянкой, жившей у них в доме. Денисов с блестящими глазами и взъерошенными волосами сидел, откинув ножку назад, у клавикорд, и хлопая по ним своими коротенькими пальцами, брал аккорды, и закатывая глаза, своим маленьким, хриплым, но верным голосом, пел сочиненное им стихотворение «Волшебница», к которому он пытался найти музыку.
Волшебница, скажи, какая сила
Влечет меня к покинутым струнам;
Какой огонь ты в сердце заронила,
Какой восторг разлился по перстам!
Пел он страстным голосом, блестя на испуганную и счастливую Наташу своими агатовыми, черными глазами.
– Прекрасно! отлично! – кричала Наташа. – Еще другой куплет, – говорила она, не замечая Николая.
«У них всё то же» – подумал Николай, заглядывая в гостиную, где он увидал Веру и мать с старушкой.
– А! вот и Николенька! – Наташа подбежала к нему.
– Папенька дома? – спросил он.
– Как я рада, что ты приехал! – не отвечая, сказала Наташа, – нам так весело. Василий Дмитрич остался для меня еще день, ты знаешь?
– Нет, еще не приезжал папа, – сказала Соня.
– Коко, ты приехал, поди ко мне, дружок! – сказал голос графини из гостиной. Николай подошел к матери, поцеловал ее руку и, молча подсев к ее столу, стал смотреть на ее руки, раскладывавшие карты. Из залы всё слышались смех и веселые голоса, уговаривавшие Наташу.
Алгоритм Рутисхаузера — один из ранних формальных алгоритмов разбора выражений со скобками, его особенностью является предположение о правильной скобочной структуре выражения, также алгоритмом не учитывается неявный приоритет операции. Впервые описан в 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.
<imagemap>: неверное или отсутствующее изображение |
Для улучшения этой статьи желательно?:
|
Отрывок, характеризующий Алгоритм Рутисхаузера
Сказать «завтра» и выдержать тон приличия было не трудно; но приехать одному домой, увидать сестер, брата, мать, отца, признаваться и просить денег, на которые не имеешь права после данного честного слова, было ужасно.Дома еще не спали. Молодежь дома Ростовых, воротившись из театра, поужинав, сидела у клавикорд. Как только Николай вошел в залу, его охватила та любовная, поэтическая атмосфера, которая царствовала в эту зиму в их доме и которая теперь, после предложения Долохова и бала Иогеля, казалось, еще более сгустилась, как воздух перед грозой, над Соней и Наташей. Соня и Наташа в голубых платьях, в которых они были в театре, хорошенькие и знающие это, счастливые, улыбаясь, стояли у клавикорд. Вера с Шиншиным играла в шахматы в гостиной. Старая графиня, ожидая сына и мужа, раскладывала пасьянс с старушкой дворянкой, жившей у них в доме. Денисов с блестящими глазами и взъерошенными волосами сидел, откинув ножку назад, у клавикорд, и хлопая по ним своими коротенькими пальцами, брал аккорды, и закатывая глаза, своим маленьким, хриплым, но верным голосом, пел сочиненное им стихотворение «Волшебница», к которому он пытался найти музыку.
Волшебница, скажи, какая сила
Влечет меня к покинутым струнам;
Какой огонь ты в сердце заронила,
Какой восторг разлился по перстам!
Пел он страстным голосом, блестя на испуганную и счастливую Наташу своими агатовыми, черными глазами.
– Прекрасно! отлично! – кричала Наташа. – Еще другой куплет, – говорила она, не замечая Николая.
«У них всё то же» – подумал Николай, заглядывая в гостиную, где он увидал Веру и мать с старушкой.
– А! вот и Николенька! – Наташа подбежала к нему.
– Папенька дома? – спросил он.
– Как я рада, что ты приехал! – не отвечая, сказала Наташа, – нам так весело. Василий Дмитрич остался для меня еще день, ты знаешь?
– Нет, еще не приезжал папа, – сказала Соня.
– Коко, ты приехал, поди ко мне, дружок! – сказал голос графини из гостиной. Николай подошел к матери, поцеловал ее руку и, молча подсев к ее столу, стал смотреть на ее руки, раскладывавшие карты. Из залы всё слышались смех и веселые голоса, уговаривавшие Наташу.
