Поместите целое значение этого символа в стек (целое значение символа цифры состоит из значения его кода в наборе символов компьютера минус значение кода О).

Иначе, если текущий символ является операцией, то

Вытолкните два последних элемента из стека в переменные X и у.

Вычислите выражение (у операция х).

Поместите результат вычисления в стек.

3) Когда в выражении встретится нулевой символ, вытолкните значение из вершины стека. Это значение и является результатом вычисления постфиксного выражения.

Замечание. На шаге 2) алгоритма, если операцией является /, в вершине стека находится 2 и следующий элемент стека - 8, то 2 выталкивается в х, 8 выталкивается в у, вычисляется 8/2 и результат 4 помещается в стек. Аналогично выполняется и операция В выражениях допускаются следующие арифметические операции:

+ сложение - вычитание * умножение / деление

возведение в степень % вычисление остатка

Каждый узел стека содержит элемент данных и указатель на следующий узел стека.

Вы можете при желании обеспечить следующие функциональные возможности:

a) Функцию evaluatePostfixExpression, которая вычисляет постфиксное выражение.

b) Функцию calculate, которая вычисляет выражение ор1 operator ор2.

c) Функцию push, которая помещает значение в стек.

d) Функцию pop, которая выталкивает значение из стека.

e) Функцию isEmpty которая определяет, является ли стек пустым.

f) Функцию printStack, которая печатает содержимое стека.

15.14. Модифицируйте программу вычисления постфиксных выражений из упражнения 15.13 так, чтобы она могла обрабатывать операнды целого типа, значения которых больше 9.

15.15. (Моделирование супермаркета). Напишите программу, которая моделирует очередь в супермаркете. Покупатели (объекты) появляются в ней случайным образом в интервале времени от 1 до 4 минут (будем рассматривать только целые значения). Обслуживается очередной покупатель также случайным образом в интервале времени от 1 до 4 минут (тоже будем рассматривать только целые значения). Очевидно, что скорость обслуживания и скорость по-

ступления покупателей в очередь должны быть сбалансированы. Если средняя скорость поступления покупателей в очередь превышает среднюю скорость их обслуживания, то очередь будет бесконечно расти. Даже при сбалансированных скоростях могут случайным образом появляться длинные очереди. Запустите модель супермаркета при условии 12-часового рабочего дня (720 минут), используя следующий алгоритм:

1) Сгенерируйте случайное целое число в диапазоне от 1 до 4, означающее минуту появления первого покупателя.

2) В момент появления первого покупателя:

Определите время обслуживания (случайное целое число от 1 до 4);

Начните обслуживание покупателя;

Спланируйте время появления следующего покупателя (добавьте к текущему времени случайное целое в диапазоне от 1 до 4);

3) Для каждой минуты дня:

Если появился следующий покупатель, то Поставьте его в очередь;

Спланируйте время появления следующего покупателя;

Если обслужен очередной покупатель, то

Исключите из очереди следующего покупателя;

Определите время его обслуживания.

Теперь запустите ваше моделирование супермаркета в течение 720 минут и ответьте наследующие вопросы:

a) Какое максимальное число покупателей было в очереди?

b) Каково максимальное время ожидания для покупателя?

c) Что происходит, если интервалы времени изменить с 1-4 минут до 1-3 минут?

15.16. Модифицируйте программу, приведенную на рис. 15.16, таким образом, чтобы она позволяла объекту двоичного дерева включать дубликаты.

15.17. Напишите программу, основанную на программе, приведенной на рис. 15.16, которая вводила бы строку текста, разбивала бы предложение на отдельные слова (вы можете использовать библиотечную функцию strtok), вставляла бы слова в дерево двоичного поиска и печатала маршруты при последовательном обходе дерева, обходе в ширину и обратном обходе. Используйте подходы объектно-ориентированного программирования.

15.18. В этой главе мы увидели, что удалять дубликаты проще всего непосредственно при создании дерева двоичного поиска. Опишите, каким образом вы могли бы выполнить удаление дубликатов, используя только один одномерный индексированный массив. Сравните эффективность удаления дубликатов с помощью массива с эффективностью удаления дубликатов на основе дерева двоичного поиска.

15.19. Напишите функцию depth, которая принимает двоичное дерево и определяет число уровней в нем.

15.20. (Рекурсивная печать списка в обратной последовательности) Напишите функцию-элемент printListBackwards, которая рекурсивно выводит элементы связного списка объектов в обратной последовательности. Напишите программу проверки, которая создает сортированный список целых чисел и печатает этот список в обратной последовательности.

15.21. (Рекурсивный поиск в списке) Напишите функцию-элемент search-List, которая с помощью рекурсии осуществляет поиск объекта связного списка с заданным значением. Если значение найдено, функция должна возвращать указатель на него; в противном случае, должен быть возвращен нулевой указатель. Используйте вашу функцию в программе проверки, которая создает список целых чисел. Программа должна запрашивать пользователя значения, помещаемые в список.

15.22. (Удаление из двоичного дерева) В этом упражнении мы обсудим удаление элементов из дерева двоичного поиска. Алгоритм удаления не является таким простым, как алгоритм вставки. При удалении элемента могут быть три случая: элемент находится в концевом узле дерева (не имеет узлов-потомков); элемент находится в узле, в которого есть один узел-потомок; элемент находится в узле, у которого имеется два узла-потомка.

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

Если удаляемый элемент находится в узле с одним узлом-потомком, то он удаляется и указатель в его родительском узле устанавливается на этот узел-потомок. В этом случае узел-потомок занимает в дереве место удаленного.

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

Какой узел использовать как замещающий, чтобы сохранить это свойство? Это или узел, содержащий наибольшее значение в дереве, меньшее значения в удаляемом узле, или узел, содержащий наименьшие значения в дереве, большее значения в удаляемом узле. Допустим, что это узел с наименьшим значением. В дереве двоичного поиска наибольшее значение, меньшее значения в родительском узле, размещается в левом поддереве родительского узла и гаранированно находится в самом правом узле этого поддерева. Это узел должен быть размещен путем обхода левого поддерева