Программирование на языке Ruby
Программирование на языке Ruby читать книгу онлайн
Внимание! Книга может содержать контент только для совершеннолетних. Для несовершеннолетних чтение данного контента СТРОГО ЗАПРЕЩЕНО! Если в книге присутствует наличие пропаганды ЛГБТ и другого, запрещенного контента - просьба написать на почту [email protected] для удаления материала
end def push(x) @store.push x end def pop @store.pop end def peek @store.last end def empty? @store.empty? endendМы добавили одну операцию, которая для массивов не определена; метод
peekНижеследующие примеры подтверждают адекватность такого определения класса.
9.2.2. Обнаружение несбалансированных скобок
В силу самой природы употребления различного вида скобок в выражениях проверить корректность написания можно с помощью стека. При открытии каждого следующего уровня вложенности скобок стек растет. Как только встречается закрывающая скобка, соответствующий элемент выталкивается из стека. Если при обнаружении закрывающей скобки в стеке ничего не оказалось или, наоборот, выражение уже закончилось, а в стеке что-то осталось, значит, выражение записано неверно.
def paren_match(str) stack = Stack.new lsym = "{I(<" rsym = "}])>" str.each_byte do |byte| sym = byte.chr if lsym.include? sym stack.push(sym) elsif rsym.include? sym top = stack.peek if lsym.index(top) != rsym.index(sym) return false else stack.pop end # Игнорируем символы, отличные от скобок... end end # Убедимся, что стек пуст... return stack.empty?endstr1 = "(((a+b))*((c-d)-(e*f))"str2 = "[[(a-(b-c))], [[x,y]]]"paren_match str1 # falseparen_match str2 # trueНаличие вложенности естественным образом наводит на мысль о применении стека. Чуть сложнее распознать несбалансированные теги в HTML- или XML-документе. Лексемы состоят из нескольких символов, но логическая структура задачи остается той же самой. Вот еще типичные примеры задач, требующих стека: преобразование выражений из инфиксной формы в постфиксную (и наоборот), вычисление постфиксного выражения (как делается в виртуальной машине Java и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.
9.2.3. Стек и рекурсия
В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.
По легенде где-то далеко на востоке существует старинный храм. Обитающие в нем монахи заняты решением единственной задачи: перемещением дисков с одного шеста на другой с соблюдением определенных правил. Первоначально на первом шесте было 64 диска. Когда все диски будут перемещены, настанет конец света.
Попутно разоблачим миф. Похоже, что на самом деле эту задачу впервые сформулировал французский математик Эдуард Люка в 1883 году, и никаких истоков в восточной культуре она не имеет. Сам Люка называл ее «Ханойской башней».
Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 264-1 ходов. Небольшой расчет на калькуляторе покажет, что монахи будут заняты своим делом несколько миллионов лет.
Однако вернемся к правилам игры. (Сформулируем их, хотя эту загадку знал уже самый первый студент самого первого факультета информатики.) Имеется шест, на который надето несколько дисков; назовем его исходным. Мы хотим переместить все диски на целевой шест, используя еще один вспомогательный шест как место промежуточного хранения. Проблема в том, что за один ход можно перемещать только один диск; при этом нельзя класть больший диск на меньший.
В следующем примере приведено решение этой задачи с использованием стека. Мы ограничились тремя дисками, потому что для перемещения 64 компьютеру потребовались бы века.
def towers(list) while !list.empty? n, src, dst, aux = list.pop if n == 1 puts "Перемещаем диск с #{src} на #{dst}" else list.push [n-1, aux, dst, src] list.push [1, src, dst, aux] list.push [n-1, src, aux, dst] end endendlist = []list.push([3, "a", "c", "b"])towers(list)Вот что напечатает эта программа:
Перемещаем диск с а на сПеремещаем диск с а на bПеремещаем диск с с на bПеремещаем диск с а на сПеремещаем диск с b на аПеремещаем диск с b на сПеремещаем диск с а на сКонечно, классическое решение этой задачи рекурсивно. Но, как мы отмечали, тесная связь между обоими алгоритмами не должна вызывать удивления, так как для рекурсии применяется невидимый системный стек.
def towers(n, src, dst, aux) if n==1 puts "Перемещаем диск с #{src} на #{dst}"
