Задача 1. В файле находится текст, в котором используются скобки трех типов: (), | |. { }. Используя стек, проверить, соблюден ли баланс скобок в тексте.
Задача 2. Используя очередь или стек. решить задачу: в файле записан текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров по возрастанию номеров позиций:
а) закрывающих скобок (например, для текста a+(45-f(x)*(b-c)) надо напечатать 8 10; 12 16; 3 17);
б) открывающих скобок (например, для текста a+(45-f(x)*(b-c)) надо напечатать 3 17; 8 10; 12 16).
Задача 3. Используя стек, проверить, является ли содержимое текстового файла правильной записью формулы следующего вида:
Используя стек, вычислить значение этого выражения с учетом общепринятого приоритета операций.
Задача 6. Написать и протестировать функции включения, удаления и чтения очередного элемента стека объемом п элементов. В случае невозможности включения (переполнения стека), удаления из пустого стека выставлять флаг.
Задача 7. Написать и протестировать функции для включения, исключения и поиска элемента кругового списка для:
а) списка без заголовка;
б) списка с заголовком (заголовок может содержать некоторую информацию о списке, например, число элементов всписке).
Задача 8*. Используя двунаправленный список, написать и протестировать функции, реализующие отдельные действия при игре в "новое домино", в котором кроме традиционных правил игрок может на ходу заменить любую кость на свою. Необходимы следующие функции:
1) проверить, можно ли сделать ход;
2) сделать ход;
3) проверить, можно ли сделать замену;
4) заменит кость ;
5) определить закончена ли игра;
Задача 9* Напишите программу сложения двух длинных целых чисел, представленных в виде строк, используя:
1)круговые списки;
2)двунаправленные списки.
Задача 10Для организации вычисления значения выражения на ЭВМ удобнее вместо обычной (инфиксной) записи использовать постфиксную (или польскую инверсную) запись ПОЛИЗ. При вычислении выражения, записанного в ПОЛИЗе, операции выполняются в том порядке, в котором они встречаются при просмотре выражения слева направо; поэтому отпадает необходимость использования скобок и многократного сканирования выражения из-за различного старшинства операций.
Например, выражению 2+3*4 соответствует ПОЛИЗ 234*+, а выражению (а+(b^с)^d)*(e+f/d) – запись abc^d^+efd+*.
Используя стек:
1) вычислить как целое число значение выражения, записанного в ПОЛИЗе;
2) выражение, записанное в ПОЛИЗе, перевести винфексную форму и распечатать.
Задача 11 Многочлен от одной переменной Х можно представить как связанный спиок с узлами вида
Коэффициент при Х
Степень Х
Ссылка на следующий узел
Например, многочлен –3Х6+4Х3+6Х2+9 будет храниться в виде списка
В котором узлы расположены в порядке убывания степеней Х.
Используя список:
1) по введенной безошибочной записи многочлена построить его представление в виде списка;
2) сложить два многочлена, представленных в виде списка( нулевые слагаемые исключить из результирующего списка);
3) проверить на равенство два многочлена;
4) вычислить значение многочлена s(X), представленного в виде списка, в целочисленной точке Х.
5) По многочлену s(X) построить его производную – многочлен р(Х);
6) Привести подобные члены в многочлене и расположить его по убыванию степеней Х (например из –8х4-74х+8х4+5-х3 получить –х3-74х+5);
7) Перемножить два многочлена, заданных в виде списков;
8) Распечатать многочлен, заданный в виде списков в обычном виде(например, так 52х^3-6x^2+x);
Задача 12Состсавить программу, которая читает произвольный СРР-файл и печатает в алфавитном порядке каждую группу имен переменных, совпадающую в первых N символах, но различающихся где-либо дальше. Параметр N задается из командной строки. При решении задачи использовать дерево с узлами вида
Struct NODE
{{;
char *word;
int k;
NODE *left;
NODE *right;
};
(He рассматривать слова внутри символьных строк и комментариев !)
Задача 13*. Формулу вида
<формула>::=<цифра>| <формула><знак><формула>)
<знак>::=+|-|*
<цифра>::=0|1|2|3|4|5|6|7|8|9
можно представить в виде бинарного дерева по следующим правилам:
формула из одной цифры представляется деревом из одной вершины с этой цифрой;
формула вида fl # f2 представляется деревом, в котором корень - это знак # соответствующей операции, а левое и правое поддеревья - это представления формул fl, f2 в виде бинарных деревьев.
Например, формуле 5*(3+8) соответствует дерево
Требуется:
а) построить дерево по формуле указанного выше вида;
б) вычислить как целое число значение дерева-формулы;
в) по заданному дереву распечатать соответствующую формулу. ;
Задача 14. С использованием структуры "стек" переписать содержимое текстового файла, разделенного на строки, в другой файл. Причем, необходимо переносить в конец каждой строки все входящие в нее цифры в обратном порядке.
Задача 15. С использованием структуры "очередь" за один просмотр файла, содержащего целые числа, распечатать файл в следующем виде: сначала - все числа, меньшие А; затем - все числа из [A, B]; потом - все остальные числа.
Задача 16. Пусть имеется ЭВМ, у которой один регистр и шесть команд:
LD А загрузить А в регистр;
ST А запомнить содержимое регистра в А;
AD А сложить содержимое регистра с А;
SB А вычесть А из содержимого регистра;
ML А умножить содержимое регистра на А;
DV А разделить содержимое регистра на А
Напечатать последовательность машинных команд, необходимых для вычисления выражения, задаваемого в постфиксной форме. Выражение может состоять из однобуквенных операндов и знаков операций сложения, вычитания, умножения и деления. В качестве рабочих использовать переменные вида Tn.
Например, выражению ABC*+DE--/ будет соответствовать следующая последовательность команд:
LD В
ML C
AD А
ST T1
LD D
SB E
ST T2
LD T1
DV T2
ST T1
Задача 17*. Составить программу, формирующую "перекрестные ссылки", т.е. печатающую список слов, которые встречаются в анализируемом файле, а для каждого слова - список номеров строк, в которых это слово встречается. При решении задачи рекомендуется использовать следующие структуры данных:
struct LIST // списокномеров строк для данного слова
{
int num;
struct LISТ *p;
}
struct NODE // узел дерева с информацией об очередном слове
