Программирование. 2 страница

Например,

union

{

float a;

unsigned int b;

}ab;

Если ввести ab.a=3.78, то затем можно рассматривать код его представления как беззнаковое целое cout<<ab.b;

Основное назначение объединения – обеспечить возможность доступа к одному и тому же участку памяти с помощью объектов разных типов.

Пример. Описать структуру СОТРУДНИК с полями ФАМИЛИЯ, ГОД_РОЖДЕНИЯ, ПОЛ. Для женщин – указывать количество детей, для мужчин – отношение к военной службе. Ввести данные о сотруднике и вывести их на экран.

# include <iostream.h>

# include <conio.h>

main ()

{

enum sextype {male, female};

enum ranktype {not,soldier,officier};

struct

{

char fio[40];

int year;

sextype sex;

union

{

int children;

ranktype rang;

};

}s1;

cout<<"Enter fio ";

cin.getline(s1.fio,40);

cout<<"Enter sex ";

cin>>int(s1.sex);

switch(s1.sex)

{

case male: { cout<< "Enter rank ";

cin>>int (s1.rang);

cout<<"\n"<<s1.fio;

cout<< " male, rank="<<s1.rang;

break;

}

case female:{cout<< "Enter number of children ";

cin>>s1.children;

cout<<"\n"<<s1.fio;

cout<< " female, children ="<<s1.children;

break;

}

}

getch();

}

Вернемся к рассмотрению динамических структур данных. Элемент любой динамической структуры данных представляет собой структуру (в смысле struct), содержащую по крайней мере два поля: для хранения данных и для указателя на этуже структуру. Полей данных и указателей может быть несколько. Например, элемент списка целых чисел имеет вид

struct el

{

int a;

el *b;

}

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

- каким образом может расти и сокращаться данная структура;

- каким образом можно включить в структуру новый и удалить существующий элемент;

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

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

Самый простой способ связать множество элементов – сделать так, чтобы каждый элемент ссылался на следующей. Такую динамическую структуру называют однонаправленным (односвязанным) линейным списком. Если каждый элемент структуры содержит ссылку как на следующий, так и не предыдущий, то говорят о двунаправленном (двусвязанном) линейном списке. Создадим однонаправленный список студентов и их оценок. Каждый элемент списка будет иметь следующий вид:

struct student

{

char *fio;

int mark;

student *next;

}

Для формирования списка требуется иметь по крайней мере один указатель – на начало списка (голова списка).

student * begin=NULL;

и один вспомогательный указатель student *adr;.

Опишем процедуру создания списка

void vvod ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

if (begin==NULL) // выделение памяти под первый элемент списка

{

begin=new (student);

adr=begin;

}

else // выделение памяти под очередной элемент списка

{

adr->next=new(student);

adr=adr->next;

}

//заполнение элементов списка

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=NULL;

}

}

В данном случае мы создали список студентов как очередь. Очередь – это частный случай списка, добавление элементов в который выполняется в один конец, а выборка – из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Очередь реализует принцип FIFO (firs in – first out, первым пришел – первым вышел). В нашем примере указатель begin указывает на начало списка, и не изменяется во время выполнения программы. Добавление элементов происходит в конец списка. Очевидно, что обработка элементов для списка, сформированного таким образом, может происходить только с первого введенного.

Другим частным случаем однонаправленного списка является стек, добавление в который и выборка из которого выполняется с одного конца. Другие операции со стеком не определены. При выборке элемент исключается из стека. Стек реализует принцип LIFO (last in – first out, последним пришел – первым вышел). Создадим список студентов как стек, постоянно передвигая указатель begin и последний созданный элемент делая головой списка.

.

void vvod1 ()

{

int n;

cout<< “Введите количество студентов ”;

cin>>n;

const int dlin=20;

char f[dlin]; // вспомогательный массив для хранения введенной фамилии студента

for (int i=1;i<=n; i++)

{

adr=new(student);

cout<< “Введите фамилию ”;

cin.getline(f,dlin);

adr->fio=new (char [strlen(f)+1]);

strcpy(adr->fio,.f);

cout<< “Введите оценку ”;

cin>>(adr->mark);

adr->next=begin;

begin=adr;

}

}

Чтобы вывести на экран элементы списка, созданного любым из предложных способов, можно использовать следующую процедуру

void vivod()

{

adr=begin;

while (adr!=NULL)

{

cout<<"\n "<<(adr->fio)<<" "<<adr->mark;

adr=adr->next;

}

}

Кроме процедур создания и вывода на экран для списка обычно определяют следующие процедуры:

- добавления элемента в конец списка;

- поиска заданного элемента;

- вставка элемента до или после заданного элемента;

- сортировка списка;

- удаления заданного элемента;

- удаление списка.

Каждому студенту рекомендуется выполнить хотя бы одно из упражнений 1-12 заданий 1-4.

Задание 1. Структуры

Пример. Ввести структуру ДАТА с полями ЧИСЛО, МЕСЯЦ, ГОД. Составить и протестировать функцию

a) ввода и вывода на экран даты;

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

c) находящую в массиве введенных дат самую раннюю.

# include <iostream.h>

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# include <iomanip.h>

struct date

{

int year;

int month;

int day;

};

int tab_day [2][12]= {{31,28,31,30,31,30,31,31,30,31,30,31},

{31,29,31,30,31,30,31,31,30,31,30,31}};

//****Функция, проверяющая является ли год високосным*******

int visokos(int year)

{

int k=year%4==0&&year%100!=0||year%400==0;

return k;

}

//**********Функция ввода даты***************************

date vvod ()

{

date d;

N: cout<<"Введите день, месяц, число\n";

cin>>d.day>>d.month>>d.year;

int k=visokos(d.year);

if (d.day<1||d.day>tab_day[k][d.month-1]||d.month<1||d.month>12||d.year<0)

{cout<<"Ошибка ввода\n"; goto N;}

else cout<<"\Дата введена\n";

return d;

}

//*********Функция вывода даты*****************************

vivod (date d)

{

cout<<setw(2)<<d.day<<'.'<<setw(2)<<d.month<<'.'<<setw(4)<<d.year<<"\n";

}

//*****Функция, вычисляющая порядковый номер дня в году*****

int day_number(date d)

{

int k=visokos(d.year);

for (int i=0; i<d.month-1; i++)

d.day+=tab_day[k][i];

return d.day;

}

//*******Функция вычисляющая наименьшую дату *************

date min (date* m, int n)

{

int imin=0, myear=m[0].year, mmonth=m[0].month, mday=m[0].day;

for (int i=1; i<n; i++)

if (m[i].year<myear || m[i].year==myear&&(m[i].month<mmonth || m[i].month==mmonth && m[i].day<mday))

imin=i;

return m[imin];

}

main ()

{

N:

clrscr();

cout<< "Выберете функцию\n";

cout<<" 1 – ввод даты\n";

cout<<" 2 – вывод даты\n";

cout<<" 3 – порядковый номер даты\n";

cout<<" 4 – минимальная дата\n";

cout<<" 0 – выход из программы\n";

int nom;

cin>>nom;

switch (nom)

{

case 0: exit(0);

case 1: {date d=vvod(); break;}

case 2: {date d=vvod(); vivod (d); break;}

case 3: {date d=vvod();

cout<<"\nПорядковый номер "<<day_number(d);

break;

}

case 4:

{

cout<<"\nВведите количество дат ";

int n; cin>>n;

date* mas = new date [n];

for (int i=0; i<n; i++)

mas[i]=vvod();

cout<<"\nИз введенных дат:\n";

for (int i=0; i<n; i++)

vivod(mas[i]);

cout<<"\наименьшая дата ";

vivod (min(mas,n));

delete []mas;

break;

}

default: cout<<"Ошибка ввода ";

}

cout<<"\nДля продолжения нажмите Enter "; getch();

goto N;

}

1. Ввести структуру с полями ЧИСЛИТЕЛЬ и ЗНАМЕНАТЕЛЬ для описания понятия РАЦИОНАЛЬНОЕ ЧИСЛО. Составить и протестировать функцию

a) ввода и вывода на экран рационального числа;

b) сокращающую рациональное число;

c) вычисляющую произведение двух рациональных чисел;

d) вычисляющую наибольшее из массива X[N] рациональных чисел;

e) поиска в массиве X[N] рациональных чисел всех, равных заданному.

2. Ввести структуру ИСТОРИЧЕСКОЕ СОБЫТИЕ с полями ЧИСЛО, МЕСЯЦ, ГОД, СОБЫТИЕ. Составить и протестировать функцию

a) ввода исторического события;

b) вывода на экран списка исторических событий;

c) вычисляющую интервал в днях, прошедший между двумя заданными историческими событиями;

d) сортирующую массив исторических событий по полю СОБЫТИЕ.

3. Ввести структуру ДАТА с полями ЧИСЛО, МЕСЯЦ, ГОД. Составить и протестировать функцию

a) ввода и вывода на экран даты;

b) вычисляющую дату, на N дней вперед по заданной;

c) находящую в массиве введенных дат все даты заданного года.

4. Ввести структуру ДАТА с полями ЧИСЛО, МЕСЯЦ, ГОД. Составить и протестировать функцию

a) ввода и вывода на экран даты;

b) по году и порядковому номеру дня в году вычисляющую число и месяц года, соответствующему этому дню;

c) находящую в массиве введенных дат самую позднюю.

5. Ввести структуру АЛГЕБРАИЧЕСКИЙ ПОЛИНОМ с полями СТЕПЕНЬ, КОЭФФИЦИЕНТЫ. Составить и протестировать функцию.

a) ввода и вывода полинома;

b) дифференцирования полинома

c) сложения двух полиномов;

d) поиска полиномов с максимальной степенью в массиве полиномов;

6. Ввести структуру АВТОМАШИНА с полями МАРКА, ГОД ВЫПУСКА, НОМЕР, ФАМИЛИЯ ВЛАДЕЛЬЦА. Написать и протестировать функцию

a) регистрации новой машины;

b) вывода на экран массива машин;

c) поиска в массиве машины по любой из комбинации признаков.

7. Ввести структуру СТУДЕНТ с полями ФИО, ЧИСЛО, МЕСЯЦ, ГОД РОЖДЕНИЯ. Написать и протестировать функцию

a) добавления нового студента;

b) вывода на экран массива студентов;

c) поиска в массиве студентов по году рождения;

d) сортирующую массив студентов по возрасту.

8. Ввести структуру ИСТОРИЧЕСКОЕ СОБЫТИЕ с полями ГОД, СОБЫТИЕ. Написать и протестировать функцию

a) ввода исторического события;

b) вывода на экран массива исторических событий;

c) сортирующую массив исторических событий по полю ГОД;

d) подсчитывающую средний интервал (в годах) между событиями в массиве событий.

9. Ввести структуру СТУДЕНТ с полями ФИО, ГОД РОЖДЕНИЯ, КОД ГРУППЫ. Написать и протестировать функцию

a) добавления нового студента в массив студентов;

b) вывода на экран массива студентов;

c) удаляющую из массива студента с определенной ФИО;

d) поиска в массиве студентов по номеру группы.

10. Ввести структуру ЭКСПОРТИРУЕМЫЙ ТОВАР с полями НАИМЕНОВАНИЕ ТОВАРА, СТРАНА (импортирующая товар), ОБЪЕМ ПАРТИИ (в штуках). Написать и протестировать функцию

a) добавляющую новый товар в массив товаров;

b) вывода на экран массива товаров;

c) сортирующая массив товаров по полю СТРАНА;

d) увеличивающую объем партий на n % для стран, импортирующих более k наименований товара.

11. Ввести структуру УЧЕНИК с полями ФИО, ГОД ОБУЧЕНИЯ, НАЗВАНИЯ КЛАССА (БУКВА). Написать и протестировать функцию

a) добавления нового ученика в массив учеников;

b) вывода на экран массива учеников;

c) сортирующую массив учеников по классам;

d) проверяющую, чтобы в каждом классе было не более n учеников (если количество учеников в классе больше n, то в этом классе оставляется только n учеников, а из остальных формируется новый класс с буквой, следующей по алфавиту за имеющимися).

12. Ввести структуру УЧЕНИК с полями ФИО, ГОД ОБУЧЕНИЯ, НАЗВАНИЯ КЛАССА (БУКВА), ИТОГОВАЯ ОЦЕНКА. Написать и протестировать функцию

a) добавления нового ученика в массив учеников;

b) вывода на экран массива учеников;

c) сортирующую массив учеников по классам;

d) подсчитывающего среднюю оценку для каждого класса.

Задание 2. Динамический список

Пример. Ввести структуру СТУДЕНТ с полями ФАМИЛИЯ, ОЦЕНКА. Решить задачу, используя динамическую структуру однонаправленного списка. Составить и протестировать функции: создания списка на основе данных из файла, записи данных из списка в файл, добавления элемента в начало (конец) списка, удаления всего списка, вывода всего списка данных на экран в виде таблицы, удаления всех студентов, имеющих заданную оценку.

#include <iostream.h>

#include <string.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

# include <iomanip.h>

# define dlin 20

struct student

{

char *fio;

int mark;

student *next;

}* begin=NULL;

//----Функция создания списка на основе данных из файла----

//Предполагается, что фамилии и оценки студентов в файле

//введены на разных строках

void vvod ()

{

char filename[50];

cout<< “Введите имя файла”;

cin>>filename;

FILE *fp= fopen(filename,"r");

if (fp!=NULL)

{

student *adr;

char f[dlin];

while(feof(fp)==0)

{

fgets(f, dlin, fp);

int l=strlen(f);

if (f[l-1]=='\n') f[l-1]='\0';

adr=new(student);

adr->fio=new (char [l+1]);

strcpy(adr->fio,f);

fscanf (fp, "%d ", &(adr->mark));

adr->next=begin;

begin=adr;

}

cout<<"Список создан";

}

else cout<<"Файла не существует";

}

//----------Функция вывода данных из файла на экран------

void vivod()

{

if (begin)

{

student *adr;

cout.setf(ios::left);

//Вывод шапки талицы

cout<<"\n"<<setw(dlin+13)<<setfill('-')<<" ";

cout<<setfill(' ')<<"\n| # "<<setw(dlin+2)<<"| FIO"<<"|Mark"<<"|";

cout<<"\n"<<setw(dlin+13)<<setfill('-')<<" ";

adr=begin;

int k=1;

while (adr!=NULL) //Вывод списка

{

cout<<setfill(' ')<<"\n| "<<setw(3)<<k<<"| "<<setw(dlin)<<(adr->fio)<<"| "<<setw(3)<<adr->mark<<"|";

cout<<"\n"<<setw(dlin+13)<<setfill('-')<<" ";

adr=adr->next;

k++;

}

}

else cout<<"Списка не существует";

}

//-----------Функция вывода списка в файл ----------

//Фамилия и оценка студента выводятся на разные строки файла

void vivod_f()

{

if (begin)

{

char filename[50];

cout<< “Введите имя файла”;

cin>>filename;

FILE *fp= fopen(filename,"w");

if (fp)

{

student *adr;

adr=begin;

while (adr!=NULL)

{

fputs(adr->fio, fp);

fputc('\n',fp);

fprintf (fp,"%d",adr->mark);

fputc('\n',fp);

adr=adr->next;

}

fclose (fp);

}

else cout<<"Запись невозможна";

}

else cout<<"Списка не существует";

}

//-----------Функция добавления элемента в список ---------

void add()

{

student *adr;

char f[dlin];

adr=begin;

begin=new(student);

cout<<"\nEnter fio ";

gets(f);

begin->fio=new (char [strlen(f)+1]);

strcpy(begin->fio,f);

cout<<"\nEnter mark ";

cin>> begin->mark;

begin->next=adr;

}

//-----Функция удаления студентов, с заданной оценкой------

void udol () //

{

if (begin)

{

int k;

cout<<"\nEnter mark ";

cin>>k;

student *adr;

//удаление найденных студентов из головы списка

while (k==begin->mark)

{

cout<<begin->fio<<" udal \n";

adr = begin;

begin=begin->next;

delete adr;

}

student *a;

adr=begin;

//удаление найденных студентов из головы списка

while (adr->next!=NULL)

{

if (k==adr->next->mark)

{

cout<<adr->next->fio<<" udal \n";

a=adr->next;

adr->next=adr->next->next;

delete a;

}

else adr=adr->next;

}

}

else cout<<"Списка не существует";

}

//-----------Функция удаления списка ----------

void del()

{

student *adr;

while (begin)

{

adr=begin;

begin=begin->next;

delete adr;

}

cout<<"\nСписок удален";

}

void main ()

{

N:

clrscr();

cout<< "Введите номер функции\n";

cout<<" 1 – Создание списка из файла\n";

cout<<" 2 – Вывод списка на экран\n";

cout<<" 3 – Вывод списка в файл\n";

cout<<" 4 – Добавление студента в список\n";

cout<<" 5 – Удаление студентов с заданной фамилией\n";

cout<<" 6 – Удаление списка \n";

cout<<" 0 – Выход из программы \n";

int nom;

cin>>nom;

switch (nom)

{

case 0: {del();exit(0);}

case 1: {vvod(); break;}

case 2: {vivod (); break;}

case 3: {vivod_f(); break;}

case 4: {add(); break;}

case 5: {udol(); break;}

case 6: {udol(); break;}

default: cout<<"Ошибка ввода ";

}

cout<<"\nДля продолжение нажмите Enter "; getch();

goto N;

}

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

- создания списка на основе данных из файла,

- записи данных из списка в файл,

- добавления элемента в начало (конец) списка,

- удаления всего списка,

- вывода всего списка данных на экран в виде таблицы.

1. Ввести структуру АВТОМАШИНА с полями МАРКА, ГОД ВЫПУСКА, НОМЕР, ФАМИЛИЯ ВЛАДЕЛЬЦА. Составить функцию поиска машины по любой из комбинации признаков.

2. Ввести структуру АВТОМАШИНА с полями МАРКА, ГОД ВЫПУСКА, НОМЕР, ФАМИЛИЯ ВЛАДЕЛЬЦА. Составить функцию поиска всех владельцев машин, имеющих более одной машины и вывода полной информации об их машинах.

3. Ввести структуру ИСТОРИЧЕСКОЕ СОБЫТИЕ с полями ЧИСЛО, МЕСЯЦ, ГОД, СОБЫТИЕ. Составить и протестировать функцию

a) сортирующую список исторических событий по дате (год, месяц, число);

b) добавляющее новое событие в отсортированный по датам события список в нужное место.

4. Ввести структуру ИСТОРИЧЕСКОЕ СОБЫТИЕ с полями ГОД, СОБЫТИЕ. Составить функцию

a) вычисляющую в каком году произошло больше всего событий;

b) формирующую новый список из событий, произошедших в этом году.

5. Ввести структуру ИСТОРИЧЕСКОЕ СОБЫТИЕ с полями ГОД, СОБЫТИЕ. Составить функцию

a) сортирующую список исторических событий по полю ГОД;

b) подсчитывающую средний интервал между датами.

6. Ввести структуру СТУДЕНТ с полями ФИО, ЧИСЛО, МЕСЯЦ, ГОД РОЖДЕНИЯ, НОМЕР ГРУППЫ. Составить функцию

a) удаляющую всех студентов из заданной группы,

b) сортирующую список студентов по возрасту.

7. Ввести структуру УЧЕНИК с полями ФИО, ГОД РОЖДЕНИЯ, НОМЕР КЛАССА. Составить функцию

a) сортирующую список студентов по алфавиту

b) добавляющего нового студента в алфавитном порядке

8. Ввести структуру ЭКСПОРТИРУЕМЫЙ ТОВАР с полями НАИМЕНОВАНИЕ ТОВАРА, СТРАНА (импортирующая товар), ОБЪЕМ ПАРТИИ (в штуках). Составить функцию

a) сортирующая список товаров по полю СТРАНА;

b) увеличивающую объем партий на n % для стран, импортирующих более k наименований товара.

9. Ввести структуру УЧЕНИК с полями ФИО, ГОД ОБУЧЕНИЯ, НАЗВАНИЯ КЛАССА (БУКВА). Составить функцию

a) сортирующую список учеников по классам;

b) проверяющую, чтобы в каждом классе было не более n учеников (если количество учеников в классе больше n, то в этом классе оставляется только n учеников, а из остальных формируется новый класс с буквой, следующей по алфавиту за имеющимися).

10. Ввести структуру УЧЕНИК с полями ФИО, ГОД ОБУЧЕНИЯ, НАЗВАНИЯ КЛАССА (БУКВА), ИТОГОВАЯ ОЦЕНКА. Составить функцию

a) сортирующую список учеников по классам;

b) подсчитывающего среднюю оценку для каждого класса.

11. Ввести структуру КНИГА с полями НАЗВАНИЕ, ФИО АВТОРА, ГОД ИЗДАНИЯ, КОЛИЧЕСТВО ЭКЗЕМПЛЯРОВ. Составить функцию

a) подсчитывающую общее количество книг,

b) вычисляющее в какой год было издано больше всего книг (по наименованию, а не по количеству экземпляров)

12. Ввести структуру КНИГА с полями НАЗВАНИЕ, ФИО АВТОРА, ГОД ИЗДАНИЯ, КОЛИЧЕСТВО ЭКЗЕМПЛЯРОВ. Составить функцию

a) удаляющую все книги, изданные ранее заданного года;

b) формирующую новый список из книг заданного автора.

Задание 3. Использование стеков и очередей

Пример. По введенной формуле необходимо построить ее постфиксную (польскую инверсную) запись (ПОЛИЗ). При вычислении выражений, записанных в ПОЛИЗе, операции выполняются в том порядке, в котором они встречаются при просмотре выражения слева направо, поэтому отпадает необходимость использования скобок и многократного сканирования выражения из-за различного приоритета операций. Например, выражению 2+3*4 соответсвует ПОЛИЗ 234*+, а выражению (a+(b^c)^d*(c+f/d) – ПОЛИЗ abc^d^+cfd/+*. Будем считать что в введенной формуле встречаются только операции +, -,*, / и буквы операнды.

#include <iostream.h>

#include <conio.h>

#include <stdio.h>

#include <stdlib.h>

#include <ctype.h>

#include <string.h>

#define ZNAK (c=='*' || c=='/')

struct STACK

{

int info;

STACK *next;

};

//-------Функция добавления элемента в вершину стека-------

void push (STACK ** s, int i)

{

STACK * new_el;

new_el= new (STACK);

new_el->info=i;

new_el->next=*s;

*s=new_el;

}

//-----Функция удаления верхнего элемента из стека--------

int pop (STACK ** s, int * error)

{

STACK * old=*s;

int info=0;

if (*s) //если стек не пуст

{

info=old->info;

*s=(*s)->next;

delete old;

*error=0; //элемент успешно удален

}

else *error=1;

return info;

}

//--Функция получение значения из стека (без удаления элемента)--

int peek (STACK ** s, int *error)

{

if (*s)

{

*error=0;

return (*s)->info;

}

else {*error=1; return 0;}

}

void main ()

{

char s[80], s1[80];//массив для считывания формулы и для записи ПОЛИЗа

char c; //вспомогательный символ

STACK *st=NULL;

cout<<"vvedite formulu ";

gets(s);

int l= strlen (s);

push(&st,'(');//заносим '(' в стек

int k=0, er;

for (int i=0; i<l; i++) //просматриваев выражение

//cлева направо

{

if (isalpha(s[i])) s1[k++]=s[i];

//isalpha(x), функция описанная в сtype.h, проверяет,

//является ли x латинской буквой

else if (s[i]=='(') push (&st, '(');

else if (s[i]==')')

while ((c=pop (&st, &er))!='(') s1[k++]=c;

else

switch (s[i])

{

case '+':case'-':

while ((c=peek(&st, &er))!='(') s1[k++]=pop(&st, &er);

case '*':case'/':

while ((c=peek(&st, &er))!='(')

{if (!ZNAK) break;

s1[k++]=pop(&st, &er);

}

push(&st,s[i]); break;

default: cout<<"Nevernuy simvol "<< s[i]; getch(); exit(-1);

}

}

//в заключение выполняются такие же действия,

//как если бы встретилась закрывающая скобка

while ((c=pop (&st, &er))!='(') s1[k++]=c;

s1[k]='\0';

cout<<"POLIS "<<s1;

getch();

}

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

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

2. В файле находится текст, в котором используют скобки трех типов: (), ||,{}. Используя стек, проверить соблюден ли баланс скобок в тексте.

3. Используя стек, решить задачу: в файле находится текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексте, упорядочив пары номеров по возрастанию номеров позиций закрывающих скобок. Например, для текса a+(45-f(x)*(b-c)) надо напечатать 8 10, 12 16, 3 17

4. Используя очередь, решить задачу: в файле находится текст, сбалансированный по круглым скобкам. Требуется для каждой пары соответствующих открывающей и закрывающей скобок напечатать номера их позиций в тексе, упорядочив пары номеров по возрастанию номеров позиций открывающих скобок. Например, для текса a+(45-f(x)*(b-c)) надо напечатать 3 17, 8 10, 12 16

Дата добавления: 2014-12-27