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

1. Расширьте функцию buildParseTree, чтобы она могла работать с математическими выражениями, в которых нет пробелов между каждым символом.
2. Измените функции buildParseTree и evaluate, чтобы они могли работать с логическими операторами (и, или, не). Помните, “не” - унарный оператор, что некоторым образом усложняет ваш код.
3. Используя метод findSuccessor, напишите нерекурсивный симметричный обход двоичного дерева поиска.
4. Измените код для двоичного дерева поиска, чтобы сделать его потоковым. Напишите нерекурсивный симметричный метод обхода для такого дерева. Потоковое двоичное дерево поддерживает в каждом узле ссылку на его преемника.
5. Измените нашу реализацию двоичного дерева поиска, чтобы оно правильно работало с дубликатами ключей. Т.е., если ключ в дереве уже присутствует, то новая полезная нагрузка заменяет старую, вместо того, чтобы добавлять новый узел с тем же ключом.
6. Создайте двоичную кучу с ограниченным размером. Другими словами, куча может отслеживать только n важных элементов. Если её размер становится больше, то наименее приоритетный элемент отбрасывается.
7. Почистите функцию printexp, чтобы она не расставляла дополнительные наборы скобок вокруг каждого числа.
8. Используя метод buildHeap, напишите сортировочную функцию, которая будет работать за время \(O(n\log{n})\).
9. Напишите функцию, которая принимает дерево синтаксического разбора математического выражения и вычисляет его производную по отношению к некоторой переменной.
10. Реализуйте двоичную кучу как max heap.
11. Используя класс BinaryHeap, реализуйте новый класс PriorityQueue. Он должен содержать конструктор и методы enqueue и dequeue.