Глава 15

c) Разрешите компилятору распознавать в операторах ЯП буквы в верхнем и нижнем регистрах (например, считать, что А эквивалентно а). Никаких модификаций моделируюш;ей программы не требуется.

d) Разрешите оператору input читать значения сразу нескольких переменных, например, input х, у. Никаких модификаций моде-лируюш;ей программы не требуется.

e) Разрешите оператору print выводить значения сразу нескольких переменных, например, print х, у. Никаких модификаций моделирующей программы не требуется.

f) Добавьте в компилятор проверку синтаксиса, чтобы он выводил сообщения о синтаксических ошибках, встретившихся в программе на ЯП. Никаких модификаций моделирующей программы не требуется.

g) Разрешите использовать массивы целых чисел. Никаких модификаций моделирующей программы не требуется.

h) Разрешите определять подпрограммы, задаваемые при помощи команд ЯП gosub и return. Команда gosub передает управление подпрограмме, а команда return возвращает управление на оператор, следующий за gosub. Это похоже на вызов функции в С-Н-. Одна и та же подпрограмма может быть вызвана с помощью нескольких команд gosub, размещенных в разных местах программы. Никаких модификаций моделирующей программы не требуется.

i) Разрешите использовать структуры повторения вида

for X = 2 to 10 step 2

Операторы ЯП next

Этот оператор for организует цикл от 2 до 10 с шагом 2. Строка next обозначает конец тела цикла for. Никаких модификаций моделирующей программы не требуется.

j) Разрешите компилятору обрабатывать вводимые и выводимые строки. Это потребует модификации моделирующей программы Простотрона, чтобы она могла обрабатывать и сохранять строки. Совет: Каждое машинное слово Простотрона можно разделить на две группы - на два полуслова, каждое из которых состоит из двухразрядного целого. Каждое двухразрядное целое представляет десятичный эквивалент кода АЗСП символа. Добавьте в ЯМП инструкцию, которая будет печатать строку, начиная с определенной ячейки памяти Простотрона. Нервое полуслово в этой ячейке содержит число символов в строке (т.е. длину строки). Каждое последующее полуслово содержит двухразрядный десятичный код АЗСП очередного символа. Инструкция печати воспринимает длину строки и печатает эту строку, преобразуя каждое двухразрядное значение в его символьный эквивалент.

к) Разрешите компилятору обрабатывать значения с плавающей запятой в дополнение к обработке целых значений. Моделирующая программа Простотрона также должна быть модифицирована для обработки значений с плавающей запятой.

15.30. {Интерпретатор ЯП) Интерпретатор - это программа, которая поочередно читает операторы кода, написанного на языке высокого уровня, определяет операцию, которая должна быть выполнена с помощью данного оператора, и немедленно выполняет эту операцию. Программу, написанную на языке высокого уровня, не надо при этом преобразовывать в программу на машинном языке. Интерпретаторы работают медленно, поскольку каждый оператор в программе должен быть сначала декодирован. Если операторы включены в тело цикла, то они декодируются на каждом шаге цикла. Более ранние версии языка программирования БЕЙСИК были реализованы именно как интерпретаторы.

Напишите интерпретатор для ЯП, рассмотренного в упражнении 15.26. Для вычисления выражений, входящих в оператор let, в программе необходимо использовать разработанный в упражнении 15.12 преобразователь инфиксной формы выражений в постфиксную и программу вычисления постфиксного выражения, разработанную в упражнении 15.13. В этой программе интерпретатора следует придерживаться тех же ограничений ЯП, которые были введены в упражнении 15.26. Проверьте интерпретатор на программах, написанных на ЯП в упражнении 15.26. Сравните результаты выполнения этих программ интерпретатором с результатами компиляции и выполнения этих программ моделирующей программой, построенной в упражнении 5.19.

15.31. (Вставка и удаление любого элемента связного списка) Наш шаблон класса связных списков выполняет операции вставки и удаления элементов только в начале и конце списка. Эти возможности удобны в том случае, если мы используем скрытое наследование и композицию для разработки шаблонов класса стеков и класса очередей с помощью незначительных добавлений к повторно используемому шаблону класса связных списков. Действительно, связные списки являются наиболее общими структурами, которые мы используем в программах. Модифицируйте шаблон класса связных списков, который мы создали в этой главе, для вьшолнения операций вставки и удаления любого элемента списка.

15.32. (Списки и очереди без указателей на конец) Наша реализация связного списка (рис. 15.3) использует два указателя на начало и конец: firstPtr и lastPtr. Указатель lastPtr используется функциями-элементами insertAtBack и removeFromBack класса List. Функция insertAtBack соответствует функции enqueue класса Queue. Перепишите класс List так, чтобы он не использовал lastPtr. В этом случае любые операции в конце списка должны начинаться с про-мотра всего списка с его начала до конца. Влияет ли это на реализацию класса Queue (рис. 15.12)?

15.33. Используйте вариант программы стека с композицией (рис. 15.11) для создания законченной работающей программы. Модифицируйте эту программу, введя в нее встраиваемые функции-элементы. Сравните эти два подхода. Обобщите достоинства и недостатки встраиваемых функций-элементов.

15.34. (Сортировка и поиск на бинарном дереве) Одной из проблем сортировки бинарного дерева является то, что последовательность, в которой вставляются данные, влияет на его структуру: для того же самого набора данных различная последовательность их появления может кардинально изменять форму дерева. Производительность обработки бинарного дерева алгоритмами сортировки и поиска чувствительна к структуре дерева. Какую структуру будет иметь бинарное дерево, если данные вставлялись в него в порядке возрастания? А ели они вставлялись в порядке убывания? Какую структуру должно иметь дерево, чтобы достигнуть максимальной производительности поиска.

15.35. (Индексированные списки) Мы рассматривали связные списки, которые должны просматриваться последовательно. Для больших списков это может приводить к плохой производительности. Обычный способ улучшения производительности поиска заключается в создании и поддержке индексных указателей списка. Индексный указатель - это множество указателей на места размепдения в списке различных ключей. Например, приложение, которое осу-ш;ествляет поиск в большом списке имен, может повысить производительность, создав индексный указатель с 26 элементами, по одному на каждую букву английского алфавита. Тогда, например, поиск последнего имени, начинающегося с Y будет начинаться с поиска в индексном указателе желательного элемента Y, а затем можно проводить поиск в списке, начиная с той позиции, на которую указывает соответствующий индекс. Поиск будет много быстрее, чем если бы пришлось просматривать весь список с самого начала. Используйте класс List на рис. 15.3 как основу класса индексированных списков IndexedList. Напишите программу, которая осуществляет операции с индексированными списками. Не забудьте включить функции-элементы inserlnlndexedList (вставить), searchlndexedList (поиск) и deleteFromlndexedList (удалить).