запись for i in 2.. m неявно преобразуется в (2.. m).each do |i|.

В следующем цикле число не обрабатывается, если оно равно nil, то есть уже вычеркнуто (см. таблицу A.12 на стр. 49). Вычёркивание всех ему кратных осуществляет итератор min.step(limit,step){|i| block} класса Numeric, который выполняет block, начиная со значения i=min, увеличивая его после каждой итерации на step до тех пор, пока оно не станет больше, чем limit. Воспользуйтесь командой ri compact для вы яснения того, что делает метод compact.

Учитесь находить нужную Вам информацию в книгах, справочных системах и сети Интернет.

Пример 11. Числами Фибоначчи называют последовательность, задава емую следующими формулами: f0 = 0, f1 = 1, fn = fn1 + fn2 для n > 1.

Напишите рекурсивный метод вычисления величины fn.

например, http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.

8 Смотри, 9 Integer учитывает также индикаторы системы счисления — префиксы 0, 0b и 0x.

Числа Фибоначчи встречаются и в науке, и в природе чрезвычайно часто10, а последовательность этих чисел занимает весьма почётное место в Интернет-энциклопедии целочисленных последовательностей11, которая является очень интересной сама по себе.

Рекурсивным называют метод, который вызывает сам себя, и написать n < 2 ? n : fib(n-2) + fib(n-1) деление последовательности чисел if a then b; else c end (см. таблицу A.12 на стр. 49).

Пример 12. С помощью написанного рекурсивного метода практически невозможно находить числа Фибоначчи fn для больших значений n, так как даже на вычисление сорокового числа на компьютере с тактовой ча стотой процессора 2.4 Ghz требуется почти 6 минут. Реализуйте метод, позволяющий найти миллионное число Фибоначчи за «разумное время».

Требуемое решение можно получить, рассматривая преобразование F, def fib(n) return n if n < for i in 2.. n (обратите внимание на множественное (параллель a, b = b, a+b ное) присваивание, см. стр. 49) имеет линейную p fib(1_000_000) заданными в постановке задачи характеристиками ведь в его десятичной записи содержится 86784 цифры!

require 'matrix' (Matrix[ [1,1], [1,0] ]**n)[0,1] можно получить ещё более быст на сайт http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci.

10 Загляните 11 http://www.research.att.com/~njas/sequences.

. Первая строка этих матриц содержит числа Фибоначчи, а так как возведение в степень (в том числе и матриц) выполняется быстро, то вычисление чисел Фибоначчи таким способом оказывается весьма эффек тивным.

Для работы с матрицами, которые не входят в число базовых типов языка Ruby, необходимо с помощью директивы require подключить биб лиотеку, в которой определён класс Matrix и методы для манипулирования с объектами этого класса. Миллионное число Фибоначчи последняя про грамма находит почти в два с половиной раза быстрее, чем предыдущая, и разница в скорости их работы увеличивается с ростом номера n числа fn.

1.4 Упражнения Задача 1. Оператор ** в Ruby реализован весьма эффективно по сравнению с наивным способом умножения основания на себя нужное число раз. Напишите программу с применением цикла while, которая будет возводить число a в нату ральную степень n за время, сопоставимое со временем работы оператора a**n даже для больших значений показателя.

Задача 2. Измените написанную при рассмотрении примера 7 программу так, что бы она работала и в ситуации, когда исследуемая строка заключается в апострофы или кавычки. Например, команда ruby palindrome.rb ’аргентина манит негра’ должна печатать true.

Задача 3. Какие изменения следует внести в программу умножения многочленов (пример 9), если коэффициенты многочленов задавать в обратном порядке — от младших степеней к старшим?

Задача 4. Напишите программу, находящую для всех чисел от 1 до задаваемого в командной строке натурального n, массив списков (массивов) всех делителей этих чисел. Для n = 6, например, программа должна напечатать следующую строку:

[[1], [1, 2], [1, 3], [1, 2, 4], [1, 5], [1, 2, 3, 6]].

Задача 5. Назовём билет с натуральным номером, десятичная запись которого состоит из чётного количества (2n) цифр, счастливым, если сумма первых его n цифр равна сумме n последних. Напишите программу, вычисляющую количество счастливых билетов для заданного натурального n.

Задача 6. Напишите программу, способную вычислить количество счастливых билетов (см. задачу 5) для n = 1000 за «разумное время» (например, около секунд на компьютере с тактовой частотой процессора 2.4 Ghz).

Задача 7. Напишите такую программу, решающую задачу 4, чтобы время её ра боты для n = 106 удовлетворяло требованиям, сформулированным в задаче 6 (это ограничение касается собственно нахождения массива; вывод такого огромного количества данных требует заметного дополнительного времени).

Задача 8. Программа умножения многочленов, приведённая на стр. 12, имеет квадратичную сложность (количество операций при перемножении двух многочле нов степени n пропорционально n2). Так называемое быстрое преобразование Фу рье (см. книгу [5]) позволяет сделать это быстрее. Реализуйте алгоритм быстрого умножения многочленов таким образом.

2. Модификация и создание пользовательских классов Ruby является объектно-ориентированным языком программирования.

Давайте рассмотрим особенности представления классов.

Объекты и классы В реальной жизни все объекты обладают индивидуальными свойства ми. Но, введя некоторые обобщения, можно поделить объекты реальной жизни на группы. Каждая из таких групп будет обладать одинаковым набо ром свойств и, как следствие, к ней будут применимы одинаковые наборы действий.

В языке программирования Ruby для описания набора свойств групп объектов и применимых к этим объектам действий используется такое понятие, как Класс — это формальное описание основных end свойств объекта (его атрибутов) и методов, приме def msiu нимых к нему. Задав описание класса, в дальнейшем можно создавать столько его экземпляров, сколько потребуется.

Классы в Ruby — открыты; если нам не хватает функциональности класса, то мы можем дополнить класс новым методом или переопределить старый.

Иерархия классов и полиморфизм Зачастую из класса можно выделить группу объектов, обладающую каким-либо специальным свойством. Такую группу называют подклассом, или дочерним классом. Дочерний класс наследует все свойства родитель ского класса, но обладает отдельной функциональностью. С помощью сим вола < указывается родительский класс.

Пример 1.

Птицы всех видов несут яйца, но не все птицы умеют летать. Хотя в классе Penguin и не описан метод lay_egg, при необходимости он ищется (и находится!) в родительском классе (принцип наследования, иерархиче ская организация классов). Метод fly переопределен для пингвинов, и реакция на вызов этого метода определяется принадлежностью к тому или 18 Модификация и создание пользовательских классов иному классу (полиморфизм, различные реалиции на одинаковую коман ду).

class Bird def lay_egg puts " #{self.class}. !" class Penguin < Bird puts " #{self.class}..."

b = Bird.new; b.lay_egg; b.fly p = Penguin.new; p.lay_egg; p.fly Создание класса Дальнейшее описание проиллюстрируем обыкновенными дробями. В процессе вычислений нередко возникает необходимость работы с дробны ми числами. Учитывая ограничения по точности представления чисел с плавающей точкой в компьютере, иногда бывает необходимо производить вычисления в терминах обыкновенных дробей, представляющих собой от ношение целого числителя и целого знаменателя. В Ruby имеется класс Rational, описывающий такие дроби. Представим на время, что его нет и создадим нечто подобное.

class Frac def initialize(a, b) raise 'Division by zero' if b.to_i == @numerator, @denominator = a.to_i, b.to_i когда мы создаем эк тельную ситуацию (об этом будет рассказано позже) и выдает соот ветствующее сообщение об ошибке.

Переменные экземпляра Переменные @numerator, @denominator — это переменные атрибу ты экземпляра класса. В именах переменных экземпляра необходимо ис пользовать префикс @. Каждый объект, принадлежащий данному классу, имеет свои собственные значения этих атрибутов (свойства), но пока их можно использовать только внутри методов самого класса. При попытке обратиться к таким переменным извне класса будет выдано сообщение об ошибке. Что же делать, если хочется иметь доступ к переменным экзем пляра вне класса?

Один способ состоит в создании методов, возвра щающих значение соответствующего атрибута. Но в случае большого числа атрибутов такой подход не удобен. Язык Ruby предлагает более удобную воз можность.

Для контроля доступа к переменным экземпляра можно использовать макросы attr_reader (для чте ния), attr_writer (для изменения значения) и attr_accessor (для выдачи разрешения на оба действия).

Метод to_s, присут ствующий в классе, опре деляет, как объект должен отображаться при печати.

Переопределение x.denominator = операторов Оперирование дробя ми предполагает возможность производить математические действия, на пример, сложение. Символ + является оператором языка Ruby. Но неко торые операторы для удобства пользователя могут быть переопределены.

Но не все! Например, + может быть переопределен, = нет.

Реализуем операцию сложения дробей самостоятельно. Чтобы дроби не получались избыточными, нам надо будет уметь их сокращать. Это поз воляет сделать алгоритм Евклида.

20 Модификация и создание пользовательских классов class Frac def initialize(a, b) raise 'Division by zero' if b.to_i == @numerator,@denominator = a.to_i, b.to_i simplify() raise "Undefined method + for class Frac and #{b.class}!" return Frac.new(self.numerator * b.denominator + private def simplify() x, y = @numerator.abs, @denominator.abs @numerator, @denominator = @numerator / m, @denominator / m В операторе сложения мы проверяем, что второй аргумент операции + тоже является объектом типа Frac.

if b.kind_of?(Frac) ект относится к тому или иному классу, при помощи метода kind_of?.

Ключевое слово self указывает на объект, вызвавший метод. Запись self.numerator эквивалентна @numerator.

Метод simplify реализует алгоритм Евклида, упрощающий дроби.

Чтобы у нас всегда были упрощенные дроби, он вызывается в конструкторе класса. Ключевое слово private определяет право доступа к следующим за ним методам только внутри класса. Таким образом, метод simplify не может быть использован вне класса Frac.

Аналогично + мы можем также переопределять и логические опера торы. Например, оператор ==, позволяющий сравнивать два объекта на равество.

class Frac def ==(b) if !b.kind_of?(Frac) raise "Undefined method == for class Frac and #{b.class}!" return (self.numerator == b.numerator and self.denominator == b.denominator) Если нам хочется, чтобы объекты нашего класса можно было бы срав нивать между собой (и, как следствие, сортирововать массив таких объ ектов методом sort), то необходимо переопределить метод. Метод должен возвращать 0 если объекты равны между собой; отрицательное число, если первый аргумент меньше второго; и положительное число в остальных случаях.

class Frac if !b.kind_of?(Frac) raise "Undefined method for class Frac and #{b.class}!" return self.numerator * b.denominator b.numerator * self.denominator Переменные класса В случае необходимости иметь какую-то одинаковую для всех объектов класса характеристику используют переменные класса, которые синтак сически выделяются указанием префикса @@ в их имени.

Предположим, что нам потребовалось знать общее количество дробей, созданных при работе с классом Frac. Добавив в конструктор класса команду инкре мента такой переменной, мы сможем узнать количество созданных дробей.

22 Модификация и создание пользовательских классов Методы класса С понятием применения метода связано понятие ответственности за его выполнение. Иногда за то или иное действие отвечает не объект, а сам класс. В этом случае применяется метод класса. При его задании перед именем метода указывается имя класса.

def dist(a) sqrt((a.x-@x)**2 + (a.y-@y)**2) def R2Point.dist(a, b) sqrt((a.x-b.x)**2 + (a.y-b.y)**2) p2 = R2Point.new(-1,-2) бя ответственность за выполне puts R2Point.dist(p1, p2) обе участвуют в данной опера подход состоит в команде, отдаваемой самому классу: «класс, определи расстояние между двумя объектами».

3. Тестирование и обработка исклительных ситуаций 3.1 Unit-тесты. Проанализировав, на что уходит время у большин ства программистов, — можно обнаружить, что на написание кода в дей ствительности тратится совсем небольшая часть. Какая-то часть уходит на понимание задачи, еще кусок на проектирование, а большую часть вре мени занимает отладка. Отладка — это процесс проверки программы на соответствие поставленной задаче, хотя чаще под этим определением пони мают работу по нахождению ошибок в программе. Отладка — это «страш ная вещь», и любой программист может рассказать о том, как на поиски какой-то ошибки ушел день или даже больше. Исправить ошибку мож но довольно быстро, но самое сложное — найти её. А при исправлении ошибки всегда существует возможность добавить новую, которая проявит ся гораздо позднее.

Из опыта предыдущих курсов было замечено, что студент написав про грамму, как правило, поверхностно проверяет её на работоспособность, а некоторые даже не запускают программу, почему-то считая, что раз уж они её написали, то она просто обязана работать правильно. Доходит до того, что студенты пытаются сдать программы, не обрабатываемые интер претатором или компилятором.

Поэтому одной из основных целей этого курса можно считать задачу обучения студента проверке (тестированию) программ. У новичков процесс тестирования выглядел обычно следующим образом. Написав программу, студент запускал ее один раз (или несколько, в зависимости от количе ства частных случаев, рассмотренных в программе) и, получив похожий на правду ответ, считал, что задача решена. Если же программа выдава ла неверный ответ, то он пытался найти ошибку и затем заново запускал программу.

Очевидно такая схема написания неудобна. Например, пусть отлажи ваемая программа ищет пересечение двух прямоугольников. В процессе проверки нам придется неоднократно (для проверки различных частных случаев) вводить координаты различных прямоугольников (по восемь чи сел на тест). Понятно, что необходимо как-то автоматизировать этот про цесс. Один из способов — поместить тестовые данные в файл и считывать их оттуда при старте программы. Такой способ позволяет нам экономить на вводе тестовых данных, но этапа сравнения полученных решений с тре буемыми при этом способе не избежать. Для решения этой задачи про граммисты на Ruby обычно используют специальную библиотеку TestUnit 24 Тестирование и обработка исклительных ситуаций (подобного рода библиотеки есть в большинстве современных языков про граммирования, в языке Java, например, для этих целей используется пакет JUnit).

Приведем простой пример, в котором протестируем довольно простую программу о разложении чётного числа на сумму простых.

def number_decomposition(number) num1, num2 = number/2, number/ while num1 > 1 and num2 < number if prime?(num1) and prime?(num2) return nil if FILE == $ p number_decomposition(142) Метод number_decomposition использует рассмотренный (стр. 10) нами ранее метод prime? (проверка числа на простоту).

Исходная программа была подготовлена к процессу тестирования. Ме тод number_decomposition возвращает полученный результат (вместо пе чати, который мы будем сравнивать с набором подготовленных шаблонов).

Тело условного оператора в конце программы будет выполнено только в случае, если интерпретатору на выполнение будет передан данный файл с программой, при подключении этого файла командой require условие FILE == $0 будет ложно.

Для тестирования создадим подкласс базовой библиотеки тестирова ния. Обратите внимание на стили наименований: имя такого класса должно начинаться с префикса Test, а имена тестирующих методов — с лексемы test. Каждый тест содержит набор сравнений — специальных функций, имя которых начинается со слова assert.

Метод assert получает два аргумента (второй — необязательный): ло гическое выражение и текстовое сообщение. Если логическое выражение окажется ложно, то программа добавит 1 к числу неуспешных проверок и выведет сообщение о неудаче. Кроме этого, будет напечатано тексто вое сообщение, переданное методу в качестве второго аргумента. Метод assert_equal получает три аргумента (третий — необязательный): ожидае мое значение, сравниваемое значение (как правило результат работы тести руемой функции) и сообщение, которое будет выведено при несовпадении первого и второго аргументов. Метод assert_nil проверяет, является ли аргумент объектом nil.

require "test/unit" require "number_decomposition4test.rb" class TestNumberDecomposition < Test::Unit::TestCase def setup def test_prime?

assert(false == prime?(1)) assert false == prime?(10) assert_equal(true, prime?(2), " 2") assert_equal true, prime?(7), " 7" assert_equal(true, prime?(103)) def test_number_decomposition assert_nil(number_decomposition(2)) assert_equal([5, 5], number_decomposition(10)) assert_equal [7, 11], number_decomposition(18) assert_equal [97, 103], number_decomposition(200) Вы можете добавлять в класс вспомогательные методы и использовать их в тестовых случаях, но только методы, начинающиеся с test, будут за пущены во время выполнения теста! Тесты вызываются в том порядке, в котором они представлены в программе. Если в тестирующем классе при сутствуют методы с именами setup и (или) teardown, то они будут выпол нены соответственно перед запуском всех тестов и после их завершения.

Очень полезно писать тесты до начала программирования.

Посмотрим на результат работы данной программы. Его можно ин терпретировать таким образом. Выполнено 2 теста (tests) и 9 сравнений (assertions). Обнаружено 0 сбоев (failures) и 0 ошибок (errors). Это озна чает, что программа теоретически работает и, наверное, все в порядке.

26 Тестирование и обработка исклительных ситуаций $ ruby test_number_decomposition.rb Loaded suite test_number_decomposition Started Finished in 0.003189 seconds.

2 tests, 9 assertions, 0 failures, 0 errors Ради эксперимента искусственно внесем ошибку в метод prime?, сделав так, чтобы он считал единицу простым числом.

Запуск теста моментально обнаруживает ошибку, показав место, где произошел сбой — седьмую строку с выражением assert false == prime?(1) (отметим, что количество сбоев стало равным одному). Изучив тестовый случай, можно понять, где произошла ошибка и в чем причина. Теперь выполнять тесты стало очень легко.

$ ruby test_number_decomposition.rb Loaded suite test_number_decomposition Started Finished in 0.061807 seconds.

1) Failure:

test_prime?(TestNumDecomposition) [test_number_decomposition.rb:7]:

is not true.

2 tests, 5 assertions, 1 failures, 0 errors Когда требуется ввести в программу новую функцию, начните с созда ния теста. Это не так странно, как может показаться. Когда вы пишите тест, то спрашиваете себя, что нужно сделать для добавления этой функ ции и как она должна работать.

3.2 Обработка исключительных ситуаций. В большинстве современных языков программирования предусмотрена возможность ра боты с исключительными (особыми) ситуациями. В языке Ruby програм мисты могут работать как со встроенными ситуациями, так и с ситуа циями, создаваемыми по указанию программиста при наличии того или иного события. Типичные встроенные ситуации — это «деление на ноль»

(ZeroDivisionError) или «достижение конца файла» (EOFError).

Перейдем к простому примеру, в котором мы бу дем обрабатывать исключительную ситуацию «деле ние на ноль». При запуске данной программы возни кает исключительная ситуация (ZeroDivisionError).

Для реализации механизма исключений в языке Ruby присутствуют следующие ключевые слова: rescue, raise, ensure.

rescue — поймать и обработать исключение, находящееся в блоке.

raise — генерировать исключительную ситуацию.

ensure — всегда выполнить код, заключенный в этот блок.

Обработаем ситуацию, описанную выше, внеся опасный участок кода в блок обработки исключения rescue.

Если кроме блока rescue присутствует блок ensure, то он будет выполнен в лю бом случае. Поэтому зача стую блок ensure использу ют для освобождения заре зервированных ресурсов. В puts " ensure !" следующей программе блок end ensure следит за освобож дением дескриптора файла.

f = File.open("testfile") begin #..

f.close unless f.nil?

Будьте внимательны при использовании исключений. Использование конструкции rescue без ука зания конкретного исключения приводит к обработке всех ошибок.

Любая библиотека Ruby возбуждает исключения при возникновении любой ошибки, и вы также можете явно возбуждать ошибки в своем коде.

Создать исключение программист может с помощью метода raise модуля Kernel (или его синонима fail). Рассмотрим его применение на следую щих примерах:

28 Тестирование и обработка исклительных ситуаций raise raise "Missing name" if name.nil?

if i >= names.size raise IndexError, "#{i} >= size (#{names.size})" Первая форма просто перехватывает текущее исключение и позволяет тем или иным способом затем обработать его. Старайтесь не использовать форму возбуждения исключения без аргумента, так как она не информатив на. Второй пример демонстрирует передачу сообщения при возбуждении исключения. Вид возбужденного исключения в этом случае можно узнать, определив тип переменной $!

sum = begin a.each { |x| sum += 1 } rescue end В некоторых ситуациях программист не может сказать, когда закончит ся процесс ввода данных. Например, на вход поступает некая последова тельность чисел. При завершении ввода требуется выдать какую-нибудь характеристику последовательности. В такой систуации уместно исполь зовать обработку исключений (конкретно, ситуацию EOFError). Начнем с ряда простых примеров.

begin rescue EOFError puts " #{sum}" end прибавляем его значение к переменной sum. При завершении ввода печа тается значение переменной sum. (При вводе даннных с консоли нажатие Ctrl-D (CTRL-Z в Windows) завершает ввод.) Обратим внимание на распро страненную ошибку. При работе с последовательностью не следует использовать контейнеры (объекты arr = @str.length cur = @str[@index].chr def compileT compileM return if @index >= @str.length cur = @str[@index].chr def compileM if @str[@index].chr == '(' def compileV print "#{@str[@index].chr} " Аналогичным способом в соответствии с грамматикой реализуются ме тоды «обработать терм», «обработать множитель». А метод «обработать переменную» заключается лишь в выводе на экран переменной и пропуске очередного элемента.

Однако, если попытаться откомпилировать нашим компилятором фор мулу a b c, то мы увидим, что последовательность символов для стеко вого калькулятора соответствует формуле a (b c), т.е. в этой ситуации компилятор работает неверно (традиционная операция вычитания ассоци ативна слева, а у нас скобки «накапливаются» справа) 1.

Обработка ввода формул (RunRecursComp.rb) require "RecursCompf" c = RecursComp.new while true c.compile(readline.chomp) 4.2 Реализация компилятора с помощью стека. Граммати ку, описанную в предыдущем разделе, легко преобразовать к виду, соответ ствующему правильному порядку выполнения арифметических действий:

формулатерм|формула + терм|формулатерм терммножитель|терммножитель|терм/множитель множитель(формула)|переменная переменнаяa|b|c|...|z Однако рекурсивно реализовать соответствующий этой грамматике ком пилятор так, как это было сделано раньше, нельзя. Невозможно, напри мер, при обработке формулы по очередному элементу определить, надо ли обрабатывать терм или формулу. Но даже если бы это оказалось возмож ным, мы бы не имели права в программе обработки формулы рекурсивно обратиться к себе, так как в этот момент непрочитанная часть еще не из менилась и, следовательно, в этом месте программа бы обращалась к себе до бесконечности.

Приведенную выше реализацию компилятора правильных формул мож но подправить так, чтобы операции выполнялись в нужном порядке. Заме 1 На самом деле ошибка возникла не из-за работы компилятора, а из-за некорректно написанной грамматики, в чем легко убедиться, рассмотрев дерево вывода формул для данной грамматики.

тим, однако, что при этом основное достоинство рекурсивной реализации — простая связь грамматики и программы — будет утеряно. Поэтому мы сначала изменим форму описания языка и лишь потом переделаем компи лятор.

Введем новые понятия: аддитивная операция = +, ; мультипликатив ная операция =·, /; и зададим понятия терма и формулы в новой форме:

формулатерм{ терм } терммножитель{ множитель}, где фигурные скобки означают повторение содержимого нуль или более раз. Остальные понятия грамматики, описанной в предыдущем разделе, оставим без изменения. При реализации компилятора в соответствии с но вым описанием языка паре фигурных скобок будет соответствовать цикл.

Метод «обработать формулу», например, будет заключаться в следую щем: сначала обрабатывается терм, затем начинается цикл, внутри кото рого происходит выбор: непрочитанных элементов нет выход из цикла;

очередной элемент + пропустить очередной элемент, обработать терм, напечатать “+”; очередной элемент пропустить очередной элемент, обработать терм, напечатать “”; иначе выход из цикла.

Аналогичным образом модифицируется метод «обработать терм». При компиляции по новой программе формула a b c будет обработана пра вильно.

Такая реализация компилятора корректно обрабатывает правильные арифметические формулы, однако, чтобы внести какие-нибудь изменения в процесс обработки формулы, надо переписать изрядную часть програм мы. Поэтому давайте рассмотрим реализацию компилятора правильных формул с помощью стека.

Прежде всего заметим, что любую правильную формулу можно ском пилировать так, что: 1) переменные в последовательности для стекового калькулятора будут идти в том же порядке, что и переменные в форму ле; 2) все операции в последовательности будут расположены позже соот ветствующих знаков операций в формуле. (Этот факт легко доказывается индукцией по числу знаков операций в формуле.) Таким образом, формулу можно компилировать так: встретив имя пере менной, немедленно его напечатать, а встретив знак операции или скобку, печатать те из предыдущих, но еще невыполненных операций (будем их называть отложенными), которые выполнимы в данный момент, после чего «откладывать» и новый знак. Поскольку среди оставшихся отложен ных операций нет таких, которые выполнимы до пришедшего знака, то для хранения можно воспользоваться стеком (назовем его стеком операций).

Этот стек и есть та информация, которая необходима для индуктивной компиляции формулы.

Рассмотрим реализацию стека. Для этого мы создадим класс Stack.

Вообще стек реализовать достаточно просто, так как фактически для его правильной работы необходимы всего лишь четыре метода: конструктор;

метод, помещающий элемент в стек; метод, берущий элемент из стека, и метод, показывающий вершину стека.

class Stack def initialize @array = Array.new def push(c) @array.push(c) @array.pop @array.last Класс Compf Давайте теперь разберем класс Compf — компилятор формул, исполь зующий стек операций. Класс Compf является подклассом класса Stack и имеет методы всех трёх типов доступа: public, protected и private. Компи лятор допускает только однобуквенные имена переменных.

require 'Stack' class Compf < Stack def compile(str) "(#{str})".each_byte { |c| processSymbol(c.chr) } def symType(c) when '+', '-', '*', '/' def processSymbol(c) case symType(c) processSuspendedSymbol(c) processSuspendedSymbol(c) def processSuspendedSymbol(c) while precedes(top, c) Работа начинается с вызова метода compile, в котором все символы строки str последовательно передаются методу processSymbol.

def priority(c) def precedes(a, b) return false if symType(a) == SYM_LEFT return true if symType(b) == SYM_RIGHT priority(a) >= priority(b) protected def symOther(c) def nextOper(c) def nextOther(c) nextOper(c) Квалификатор доступа protected и метод nextOther нужны для созда ния на базе класса Compf нового класса Calc, реализующего калькулятор формул2.

Класс Calc (калькулятор числовых формул) выведен из класса Compf, переопределяет некоторые методы последнего, и имеет дополнительный стек для размещения в нём чисел. Калькулятор работает только с цифрами (числами от 0 до 9).

Несколько комментариев к методу nextOper(c) класса Calc. Множе ственное присваивание в первой строке метода корректно, т.к. в языке Ruby при выполнении множественного (параллельного) присваивания сна 2 Хотя в языке Ruby в данном случае можно убрать "protected тем самым размещая все нижеописываемые константы и методы в зоне действия квалификатора private, в языках Java и C++ здесь нужен именно квалификатор protected.

чала последовательно вычисляются все выражения в правой части опе ратора присваивания.

require 'Compf' class Calc < Compf def initialize def compile(str) protected def symOther(c) def nextOper(c) second, first = @s.pop, @s.pop @s.push(first.method(c).call(second)) def nextOther(c) @s.push(c.to_i) Конструкция first.method(c).call(second) во второй строке метода мо жет быть объяснена таким примером: выражение 3.metod(’-’).call(2), экви валентно выражению 3.-(2) или просто 3-2.

Задача 1. Добавьте операции sin, cos и унарный минус.

Задача 2. Добавьте правоассоциативную операцию ^ возведения в степень.

Задача 3. Добавьте квадратные и фигурные скобки.

Задача 4. Измените программу так, чтобы допускались в качестве имен переменных произвольные идентификаторы языка Ruby.

Задача 5. Добавьте левоассоциативную операцию % с приоритетом, рав ным приоритету операции /.

Задача 6. Добавьте возможность записи формулы с пробелами и коммен тариями двух типов (/* */ и //).

Задача 7. Измените программу так, чтобы ввод, содержащий в качестве аргументов только восьмеричные числа (начинающиеся с нуля, например 056), компилировался в программу, содержащую десятичные числа.

Задача 8. Измените программу так, чтобы ввод, содержащий в качестве ар гументов только шестнадцатеричные числа (начинающиеся с 0x, например 0x56), компилировался в программу, содержащую восьмеричные числа.

Задача 9. Измените программу так, чтобы ввод, содержащий в качестве ар гументов только римские числа, не превосходящие 5000, компилировался в программу, содержащую десятичные числа.

Задача 10. Измените программу так, чтобы для коммутативной операции аргументы выдавались в алфавитном порядке.

Задача 11. Добавьте фигурные скобки, означающие возведение в квадрат.

Используйте операцию DUP стекового калькулятора.

Задача 12. Считая, что a = 0, оптимизируйте формулу (уберите лишние сложения).

Задача 13. Считая, что b = 1, оптимизируйте формулу (уберите лишние умножения).

Задача 14. Добавьте возможность ввода формулы на нескольких строках.

A. Язык программирования Ruby A.1 Базовые типы. Базовыми типами языка Ruby являются чис ла, строки (объекты класса String), массивы (класс Array), диапазоны (Range), хэши или ассоциативные массивы (Hash), символы (Symbol) и ре гулярные выражения (объекты класса Regexp). Любое целое число x Z может быть представлено объектом класса Fixnum (если величина |x| не слишком велика) или Bignum (иначе), но лишь конечное подмножество из несчётного множества действительных чисел R представимо в виде объек тов класса Float, часто называемых числами с плавающей точкой.

-1234567890 -1234567890345 целое число — объект класса Bignum 1_234_567_890 1234567890345 подчёркивания в записи чисел игнорируются -123.45 -123.45 «действительное» число (класс Float) 1.2345e+2 123.45 экспоненциальная формы записи Для задания строк можно использовать кавычки (") или апострофы (').

В первом случае распознаются и интерпретируются так называемые эс кейп-последовательности (например, \n, \", \t, \r) и выполняется подста новка результатов вычисления выражения expr вместо подстроки #{expr}.

В обоих случаях последовательности \\ и \' преобразуются в символы \ и ' соответственно. Существуют и другие способы задания строк, некото рые из которых показаны в таблице A.2.

"2 + 3 = #{2+3}" "2 + 3 = 5" подстановка вычисленного выражения '2 + 3 = #{2+3}' "2 + 3 = #{2+3}" подстановка не выполняется %q( Ruby) " Ruby" аналог строки в апострофах %Q(#{2**32}) "4294967296" аналог строки в кавычках "a\nb" всего три символа: буквы a и b разделены символом \n Массив (Array) в Ruby — это набор (коллекция, множество) произ вольных объектов (см. таблицу A.3).

[1, 2.3, "Ruby"] [1, 2.3, "Ruby"] массив из трёх элементов [[1,2],[3]] [[1, 2], [3]] массив из двух массивов %w( ?) ["", "?"] способ создания массива строк %w(\ ?) [" ", "?"] экранирование пробела %W(2 3 #{2*3}) ["2", "3", "6"] подстановка значения выражения Диапазон (Range) — последовательность объектов, которая включает (для e1..e2) или не включает (для e1...e2) в себя элемент e2. Исполь зуемый в качестве итератора диапазон передаёт в блок все свои элементы (как при вызове метода to_a, преобразующего диапазон в массив).

'd'..'n' ["d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n"] Хэш (Hash) — это набор пар ключ–значение. Хэш схож с массивом, за исключением одной особенности — индексация производится с помощью объектов любых типов, кроме integer. Причем порядок обхода элементов не зависит от порядка вставки.

Примеры хэшей приведены ниже:

Hash["a",1,"b",2,"c",3 ] {"a"=>1, "b"=>2,"c"=>3} хэш из трех элементов Hash["a" => 1, "b" => 2] {"a" => 1, "b" => 2} хэш из двух элементов Как видно из примера, для создания хэша часто используются лите ралы key => value. Ключ и значения находятся в паре, поэтому число аргументов должно быть четным.

Хэши имеют значение по умолчанию. Это значение возвращается ка ким-либо итератором при попытке обращения к ключу, не существующему в хэше. И этим значением является nil.

Регулярные выражения (объекты класса Regexp) используются для подбора шаблона строки. Для создания регулярных выражений нужно ис пользовать литералы /.../ или %r..., а также конструктор Regexp.new. От метим, что разные версии Руби используют разные средства для работы с регулярными выражениями.

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

С помощью регулярных выражений можно:

Проверять, соответствует ли вся строка целиком заданному шаблону.

Находить в строке подстроки, удовлетворяющие заданному шаблону.

Извлекать из строки подстроки, соответствующие заданному шабло Изменять в строке подстроки, соответствующие шаблону.

Примеры использования регулярных выражений приведены в таблице А7.

Каждый символ регулярного выражения последовательно сравнивается с проверяемой строкой. Все, что не является указанными ниже спецсим волами или операторами, воспринимается, как обычный символ, рассмат риваемый на простое совпадение.

A.2 Термы и выражения. Термами в языке Ruby являются лите ралы (объекты базовых типов), результаты выполнения команд операци онной системы, генерации символов и вызова методов, а также значения констант и переменных.

Вызов метода m объекта obj1 со списком параметров arg и блоком blk (иначе называемый посылкой сообщения m получателю obj) записывают в виде obj.m(arg){blk} или obj.m(arg) do blk end. Для вызовов, выпол няемых вне классов («на верхнем уровне»), получателем является main — экземпляр класса Object, создаваемый при старте Ruby-программы. При меры вызовов методов приведены в таблице A.8.

В языке Ruby имена используются для ссылок на константы, перемен ные, методы, классы и модули. В таблице A.9 перечислены зарезервиро ванные слова, которые не могут быть использованы в качестве имён.

Имена констант должны начинаться с большой латинской буквы (от A до Z), за которыми может следовать любая последовательность больших и малых латинских букв, цифр и символов подчёркивания (_).

Переменные в языке Ruby бывают четырёх различных видов: локаль ные, экземпляра, класса и глобальные. Имена локальных переменных должны начинаться с малой латинской буквы (от a до z) или символа подчёркивания, за которыми может следовать любая последовательность больших и малых латинских букв, цифр и символов подчёркивания. В име нах локальных переменных, состоящих из нескольких слов, рекомендуется использовать подчёркивание, например, day_week.

К именам переменных экземпляра вначале добавляется символ @ (на пример, @x), переменных класса — два таких символа (например, @@name), а глобальных переменных — символ $ (например, $_). Некоторые пред определённые объекты имеют имена, отступающие от этого правила.

Методы, не являющиеся переопределяемыми операторами (см. табли цу A.11), должны иметь имя, образованное по тем же правилам, что и име на локальных переменных. К имени метода может быть добавлен восклица тельный (!) или вопросительный знак (?), либо символ =. Рекомендуется использовать такие имена для методов, изменяющих объект-получатель (self), возвращающих логическое значение и допускающих использова ние в левой части оператора присваивания соответственно.

Имена классов и модулей являются константами и следуют описанным выше правилам. Рекомендуется для констант, определяемых в классах, ис 1 В случае отсутствия явного получателя им является объект self некоторого класса, в контексте которого происходит данный вызов.

puts ", !" Получатель — предопределённый объект main клас 2.+(3) Получатель — число 2 (объект класса Fixnum).

[1,2,3][0]=4 Получатель — массив [1,2,3] (см. таблицу A.11).

"123".to_i Получатель — строка "123". Метод to_i класса "123".to_i(8) Параметр 8 указывает, что строку надо рассматри 3.times do |i| p i end Получатель — число 3. Параметров нет, но имеется a=[1,2,3,4,5] Получатель — экземпляр a класса Array, включаю a.inject(0){|s,x|s+x} щего в себя модуль Enumerable. Метод inject при [1,2].to_i Получатель — массив [1,2]. Так как класс Array, пользовать только большие буквы и символ подчёркивания, а при построе нии имён классов и модулей применять так называемый MixedCase, когда каждое из слов, образующих сложное имя, пишется с большой буквы.

Выражение представляет терм или несколько термов, объединённых с помощью перечисленных в таблице A.11 операторов. Приоритеты операто Таблица A.9. Зарезервированные слова языка Ruby ров, разделённых горизонтальными линиями, различны и убывают сверху вниз. Многие из операторов являются методами и могут быть переопреде лены. Примеры использования операторов приведены в таблице A.12.

Таблица A.10. Некоторые предопределённые стандартные объекты ARGF или $< Object Объект, предоставляющий доступ к конкатенации всех ARGV или $* Array Массив строк, содержащий аргументы командной стро ENV Object Подобный хэшу объект, содержащий значения перемен DATA IO Если программа содержит директиву END, то DATA RUBY_PLATFORM String Идентификатор платформы (операционной системы с дополнительными характеристиками), на которой вы RUBY_VERSION String Версия интерпретатора Ruby STDOUT IO Стандартный вывод, начальное значение $stdout FILE String Имя файла, содержащего выполняемую программу LINE String Номер текущей строки в программе = %= ~= /= -= += Присваивание и присваивания с операцией Нет