Упражнения для программирования¶

Измените алгоритм “из инфикса в постфикс” таким образом, чтобы он обрабатывал ошибки.
Измените алгоритм вычисления постфиксного выражения таким образом, чтобы он обрабатывал ошибки.
Создайте направленный инфиксный вычислитель, который совмещает функциональность преобразования из инфикса в постфикс и алгоритм постфиксных вычислений.
Оберните результат предыдущего задания в калькулятор.
Реализуйте АТД Queue, используя список таким образом, чтобы хвост очереди совпадал с его концом.
Продумайте и воплотите эксперимент по тестовому сравнению двух реализаций очереди. Какие выводы вы можете из него сделать?
Существует возможность реализовать очередь таким образом, чтобы обе операции enqueue и dequeue в среднем имели производительность \(O(1)\). Это подразумевает, что большую часть времени они будут \(O(1)\), за исключением единственного случая, при котором dequeue будет \(O(n)\).
Рассмотрите ситуацию из реальной жизни. Сформулируйте вопрос и создайте симуляцию, которая поможет на него ответить. Возможные ситуации:
- Машины, стоящие в очереди в мойку.
- Покупатели в очереди на кассе бакалейного магазина.
- Самолёты, взлетающие и приземляющиеся на взлётно-посадочную полосу.
- Кассир банка.
Обязательно укажите сделанные вами предположения и предоставьте любые вероятностные данные, которые нужно будет рассмотреть в качестве части сценария.
Измените симуляцию “Hot Potato”, чтобы можно было случайным образом выбирать значение для отсчёта. Таким образом, результат каждого прохода станет непредсказуемым.
Реализуйте машину поразрядной сортировки. Поразрядная сортировка для десятичных целых чисел - это чисто механическая сортировочная техника, использующая набор корзин: одну главную и десять цифровых. Каждая корзина работает как очередь и содержит внутри значения в порядке их поступления. Алгоритм начинает работу с помещения всех заданных чисел в главную корзину, после чего считывает их оттуда по одиночке. Из главной корзины берётся первое число и помещается в цифровую корзину, соответствующую его наименьшему разряду. Например, число 534 отправится в четвёртую корзину, а 667 - в седьмую. После того, как все числа разложены по цифровым корзинам, последовательность вновь собирается в главную, но при этом числа берутся из корзин по порядку. Т.е, сначала из нулевой, потом из первой и так далее. Процесс повторяется, но критерием уже служат цифры десятков, сотен и так далее. После того, как будет обработан последний разряд, главная корзина будет содержать значения в упорядоченном виде.
Другой пример, в котором может возникнуть проблема соответствия скобок, приходит из гипертекстового языка разметки (или HTML). В HTML у каждого тега существуют открывающая и закрывающая формы, которые должны быть сбалансированы, чтобы адекватно описывать веб-документ. Вот пример очень простого веб-документа:
```
<html>
   <head>
      <title>
         Example
      </title>
   </head>

   <body>
      <h1>Hello, world</h1>
   </body>
</html>
```
предназначенный исключительно для того, чтобы показать соответствующие и вложенные структуры тегов языка. Напишите программу, которая проверит HTML документ на соответствие открывающих и закрывающих тегов.
Расширьте программу из листинга 2.15, чтобы обрабатывать палиндромы с пробелами. Например, I PREFER PI - это палиндром, который читается одинаково слева направо и справа налево, если проигнорировать пробелы.
В реализации метода `size` мы подсчитываем количество узлов в списке. Альтернативной стратегией было бы хранить количество узлов в дополнительном поле данных в голове списка. Измените класс UnorderedList, чтобы включить в него эту информацию, и перепишите метод size.
Реализуйте метод remove, который работал бы корректно, если элемент отсутствует в списке.
Измените классы списков, исключив дубляж операций. Какие методы затронет это изменение?
Реализуйте метод __str__ для класса UnorderedList. Как выглядело бы красивое представление списка?
Реализуйте метод __str__, чтобы списки отображались Python-способом (в квадратных скобках).
Реализуйте оставшиеся операции, определённые в АТД UnorderedList (append, index, pop, insert).
Реализуйте метод “среза” для класса UnorderedList. Он должен принимать два параметра - start и stop - и возвращать копию списка, начиная с позиции start и заканчивая (но не включая!) позицией stop.
Реализуйте оставшиеся операции, определённые в АТД OrderedList.
Рассмотрите отношения между упорядоченными и неупорядоченными списками. Возможно ли использовать наследование для создания более эффективной реализации? Воплотите эту наследственную иерархию.
Реализуйте стек, используя связанный список.
Реализуйте очередь, используя связанный список.
Реализуйте дек, используя связанный список.
Продумайте и проведите эксперимент, сравнивающий производительности списков Python и списков, реализованных как связанные.
Продумайте и проведите эксперимент, сравнивающий производительность стека и очереди, основанных на списках Python, с реализациями на основе связанного списка.
Данная выше реализация связанного списка называется единичным связанным списком, поскольку каждый его узел содержит единственную ссылку на следующий в последовательности. Альтернативная реализация известна как двойной связанный список. В ней нужный узел ссылается на следующий за ним (next) и на предыдущий ему (back). Голова также имеет две ссылки: одну на первый узел в связанном списке, а вторую - на последний. Закодируйте эту реализацию в Python.
Создайте реализацию очереди, которая имела бы среднюю производительность \(O(1)\) для операций постановки в очередь и извлечения из неё.

Next Section - Цели