Упражнения

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

15.7. Напишите программу, которая объединяет два объекта упорядоченных списков данных целого типа в единый объект упорядоченного списка. Функция merge должна принимать ссылки на каждый из объединяемых списков и возвращать ссылку на объединенный объект.

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

15.9. Напишите программу, которая создает объект связного списка из 10 символов, а затем создает второй объект списка, содержащий копию первого списка, но в обратной последовательности.

15.10. Напишите программу, которая вводит строку текста и использует объект стека для печати строки в обратной последовательности.

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

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

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

15.5. Последовательный обход:

11 18 19 28 32 40 44 49 69 71 72 83 92 97 99

Обход В ширину:

49 28 18 11 19 40 32 44 83 71 69 72 97 92 99

Обратный обход:

11 19 18 32 44 40 28 69 72 71 92 99 97 83 49

При математической записи в привычной, естественной форме обычно пишут выражения, подобные 3 + 4 и 7/9, в которых операции (здесь + и /) записываются между своими операндами. Это называется инфиксной формой записи. В компьютерах используется постфиксная форма записи, в которой операция записывается справа после двух своих операндов. Приведенные выше выражения в инфиксной форме записываются в постфиксной форме соответственно как 3 4 -Ь и 7 9 /.

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

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

Напишите программу, которая преобразовывает простое инфиксное арифметическое выражение (предполагайте, что вводится правильное выражение) с одноразрядными целыми числами, например

(6 + 2) *5-8/4

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

6 2 + 5 * 8 4 /-

Программа должна читать выражение в символьный массив infix и использовать модифицированные варианты функций стеков, реализованные в этой главе, для создания постфиксного выражения в символьном массиве postfix. Алгоритм создания постфиксного выражения приведен ниже:

1) Поместите в стек левую круглую скобку (

2) Добавьте правую круглую скобку ) в конец символьного массива infix.

3) Пока стек не пустой, читайте символьный массив infix слева направо и выполняйте следующие действия:

Если текущий символ в массиве infix является цифрой, то копируйте его в следующий элемент массива postfix.

Если текущий символ массива infix является левой круглой скобкой, то помещайте его в стек.

Если текущий символ в массиве infix является операцией, то

Выталкивайте из вершины стека операции (если они там есть), пока их приоритет не меньше приоритета текущей операции, и помещайте их в массив postfix.

Поместите текущий символ массива infix в стек.

Если текущий символ в массиве infix является правой круглой скобкой, то

Выталкивайте операции из вершины стека и вставляйте их в массив postfix, пока на вершине стека не появится левая круглая скобка.

Вытолкните из стека (и отбросьте) левую круглую скобку.

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

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

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

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

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

a) Функцию convertToPostfix, которая преобразует инфиксное выражение в постфиксное.

b) Функцию isOperator, которая определяет, является ли с операцией.

c) Функцию precedence, которая определяет, является ли приоритет operatorl меньшим, равным или большим, чем приоритет орега-tor2. Функция возвращает соответственно -1, О и 1.

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

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

f) Функцию stackTop, которая возвращает значение в вершине стека, не выталкивая его из вершины.

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

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

15.13. Напишите программу, которая вычисляет постфиксное выражение (полагая, что оно правильное), например

62 + 5*84/

Программа должна читать постфиксное выражение, состоящее из цифр и операций, в символьный массив. Используя модифицированные варианты функций стека, реализованные ранее в этой главе, программа должна просматривать (сканировать) выражение и вычислять его. Алгоритм программы состоит в следующем:

1) Добавьте нулевой символ (\0) в конец постфиксного выражения. Когда встречается нулевой символ, то никакая дальнейшая обработка данных выражения не требуется.

2) Пока \0 не встретился, читайте выражение слева направо. Если текущий символ является цифрой, то