В виде списка удобно хранить стек с элементами переменной длины или трудно предсказуемым количеством элементов. Вершина стека размещается в начале списка, где выполнять операции включения и исключения элемента проще, чем в конце (рис. 19.5).
Рис. 19.5 Стек в виде списка
1. Что такое стек?
2. Как можно хранить стек?
3. Опишите стек, состоящий из целых чисел, в виде списка. Опишите отдельные функции вталкивания элемента в стек и выталкивания элемента из стека. Приведите примеры их вызова.
1. Получите у преподавателя индивидуальное задание.
2. Составьте программу на языке С и подберите тесты для проверки программы на компьютере.
3. Отладьте программу на компьютере.
5. Оформите и сдайте отчет.
1. Дано арифметическое выражение длиной до 20 символов, оканчивающееся пробелом. Выражение содержит однобуквенные идентификаторы и знаки операций +, -, *, /. Преобразовать выражение в обратную польскую запись, используя стек операций и приоритетов.
Пример.
Вх. текст: a*b+c/d-e
Результат: ab*cd/+e-
2. Дано арифметическое выражение в постфиксной (обратной польской) записи длиной до 20 символов, оканчивающееся пробелом. Получить эквивалентную последовательность элементарных присваиваний, содержащих одну арифметическую операцию (используя стек операндов).
а) В левой части операторов присваивания использовать вспомогательные переменные R1,R2,R3,...
Пример.
Вх. текст: abc*+def+/-
Результат: R1:=b*c
R2:=a+R1
R3:=e+f
R4:=d/R3
R5:=R2-R4
б) В левой части операторов присваивания использовать вспомогательные переменные R1,R2,R3,..., сократив до минимума число этих переменных.
Пример.
Вх. текст: abc*+def+/-
Результат: R1:=b*c
R1:=a+R1
R2:=e+f
R2:=d/R2
R2:=R1-R2
3. Дано арифметическое выражение длиной до 30 символов, оканчивающееся знаком равенства. Выражение содержит знаки операций +, -, *, / и однозначные целые числа и представлено в обратной польской записи. Вычислить значение выражения, используя стек операндов.
Пример.
Вх. текст: 345+2*63/-+= 19
результат
4. Дано скобочное выражение длиной до 50 символов, оканчивающееся пробелом. Напечатать попарно порядковые номера соответствующих открывающих и закрывающих скобок в выражении.
Пример.
1 4 8 10 14 19 27
Вх. текст: (a+(b+c)/(a-b)*(x+(y+2)**3))/2
Результат: 4 8
10 14
19 23
16 27
1 28
Указание. Для запоминания номеров открывающих скобок использовать стек.
5. Дана последовательность чисел, оканчивающаяся нулем.
а) Напечатать только отрицательные числа из этой последовательности, причем, если подряд идет несколько отрицательных чисел, печатать их в обратном порядке. Например:
Указание. Последовательность подряд расположенных отрицательных чисел помещать в стек.
б) Напечатать только положительные числа из этой последовательности, причем, если подряд идет несколько положительных чисел, печатать их в обратном порядке. Например:
Указание. Последовательность подряд расположенных положительных чисел помещать в стек.
6. Дана последовательность из n слов (n<=20) в алфавитном порядке. Длина каждого слова не более 10 букв. Напечатать слова, начинающиеся с одной и той же буквы в обратном порядке, используя стек. Например:
Вх. последовательность: Результат:
Август апрель
Апрель август
Май море
Март март
Море май
Лето лето
Часть 1 Оглавление
Оглавление. 2
Введение. 4
1. Этапы и проблемы решения задач с использованием компьютера. 4
2. Общие сведения о языке программирования C++ и системе программирования. 4
2.1. История создания языка C++. 4
2.2. Краткая характеристика языка C++. 5
Алфавит языка. 5
Ключевые слова. 6
Идентификаторы.. 6
Знаки операций. 7
Константы.. 7
Комментарии. 7
2.3. Структура и основные элементы программы.. 7
2.4. Трансляция программ и их выполнение. 9
3. Стандартные (базовые) типы данных, операции и выражения. 11
3.1. Типы данных, переменные и константы.. 12
Понятие типов данных. 12
Классификация простых предопределенных типов данных. 13
Переменные, константы.. 13
3.2. Целочисленные типы данных. 15
3.3. Вещественные типы данных. 16
3.4. Логический тип данных. 17
3.5. Символьный тип данных. 17
3.6. Операции и выражения. 19
Преобразования типов данных. 21
Операция присваивания. 24
Арифметические операции. 26
Операции отношения. 30
Логические операции. 30
Поразрядные (битовые) операции. 31
Операции составного присваивания. 35
Условная операция. 36
Операция sizeof 36
Приоритеты рассмотренных операций. 37
3.7. Ввод и вывод простых типов данных. 38
Вывод текстовых строк. 39
Ввод/вывод арифметических типов данных. 41
Форматирование ввода / вывода. 42
4. Основные управляющие структуры программирования и управляющие конструкции в языке С++ 49
4.1. Идеи структурного программирования. 49
4.2. Управляющие структуры и инструкции языка C++. 52
