Б) стеки

1. Используя стек, описать функцию:

• проверяющую, является ли стек пустым;

• создающую пустой стек;

• добавляющую заданный элемент в стек;

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

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

3. Постфиксной формой записи выражения а∆b (или его обратной польской нотацией) называется запись, в которой знак операции размещён за операндами: ab∆. Для вычисления значения выражения, записанного в постфиксной форме, применяют следующий алгоритм. Выражение просматривается слева направо. Если встречается операнд, то его значение заносится в стек, а если встречается знак операции, то из стека извлекаются два последних элемента (операнд это операции), над ними выполняется эта операция и результат помещается в стек. По окончании просмотра в стеке останется только одно число - значение выражения. Опишите процедуру, вычисляющую значение выражения, записанного во входном текстовом файле в обратной польской нотации.

4. Для преобразования инфиксной формы выражения в постфиксную (см. задачу 3) можно использовать следующий алгоритм. Выражение просматривается слева направо. Операнды добавляются в стек X, а левые скобки и операции - в стек У. Встретив правую скобку, отыскиваем в стеке соответствующую ей левую. При этом всё, что сверху - выталкивается из стека У и вталкивается в стек X. Очередная операция помещается в стек Y, если только лежащая ниже операция имеет более низкий приоритет или оказывается левой скобкой. В противном случае, вначале элементы из стека Y выталкиваются в Х до тех пор, пока не встретится левая скобка, дно стека операция с более низким приоритетом, а потом очередная операция помещается в У. Исходное выражение обрабатывается до тех пор, пока не встретится знак равенства.

Оператор	Приоритет
* /	3 3
+ -	2 2
(	1
=	0

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

5. Опишите процедуру, переводящую выражение, записанное в постфиксной форме, в инфиксную форму.

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

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

8. Напишите программу, которая печатает построчно заданный во входном файле текст, располагая символы в строках в обратном порядке.

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

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

11. Используя стек, проверить правильность арифметическо­го выражения.

• проверить число открывающих и закрывающих круглых ско­бок в выражении;

• проверить, следует ли перед и за знаком арифметической опе­рации число.