Введение 3 страница. 5. Используя стек, проверить, является ли содержимое текстового файла правильно записью формулы следующего вида:

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

<формула>::=<терм>|<терм>+<формула>|<терм>-<формула>

<терм>::=<имя>|<формула>

<имя>::=x | y |z

6. В текстовом файле записана без ошибок формула следующего вида:

<формула>::=<цифра>|M(<формула>,<формула>) |m(<формула>,<формула>)

<цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

M обозначает функцию максимума, а m – функцию минимума

Используя стек, вычислить как целое число значение заданной формулы. Например, М(5,m(6,8))=6.

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

<выражение>::=true | false |! <выражение> | <выражение>&&<выражение> | <выражение>||<выражение>

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

8. Используя стек вычислить как целое число значение выражения, записанного в ПОЛИЗе.

9. Используя стек, выражение, записанное в ПОЛИЗе, перевести в инфиксную форму.

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

11. Используя очередь за один просмотр файла, содержащего целые числа, распечатать файл в следующем виде: сначала все числа меньшие A, затем все числа из интервала [A, B] и затем - все остальные числа.

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

<формула>::=<цифра>|(<формула><знак><формула>)

<знак>::=+|-|*

<имя>::=x | y |z

<цифра>::=0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

ГЛАВА 3. Основы объектно-ориентированного программирования

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

Описать класс возможно следующим образом:

class имя_класса {список_элементов};

Элементы касса (компоненты класса member) делятся на поля (данные-члены, элементы данных), которые представляют собой данные и методы (компонентные функции, функции-члены), которые представляют собой функции для работы с данными.

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

Синтаксис описания методов класса в целом соответствует синтаксису описания функций. Метод можно объявить как константный (метод, который не может менять значения полей класса). В этом случае указывается спецификатор const после списка параметров. Рекомендуется описывать как константные методы, которые предназначены для получения значений полей.

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

· private (элементы видимые только внутри класса – скрытые элементы),

· public (элементы видимые как внутри так и вне класса – открытые элементы – интерфейс класса),

· protected (элементы, которые видимы только внутри класса и наследникам класса – защищенные элементы).

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

Например,

class имя_класса

{

private:

описание скрытых элементов

public:

описание доступных элементов

};

Приведем пример описания класса «Строка».

class CStr

{

char * s; // поле для хранения строки

int len; // поле для хранения длины строки

public:

CStr () {len=0; s=new char; *s=’\0’;} // метод создания пустой строки

CStr (char *); // метод создания строки, равной заданной

char * get_str() const {return s;} //метод получения строки

int get_len() const {return len;}// метод получения длины строки

}

В данном классе два скрытых поля и четыре доступных метода. Причем тело одного из методов -CStr (char*) - не определено внутри класса.

Если тело метода определяется внутри класса, то он называется встроенными (inline). Обычно встроенными делают только короткие методы. Если тело метода описывается вне класса, то используется операция изменения видимости (::). Например,

CStr::Cstr(char * st)

{len=strlen(st); s=new (char[len+1]); strcpy(s,st); s[len]=’\0’;}

Переменные, имеющие тип описанного класса, принято называть объектами. Для описания объектов класса используется одна из следующих конструкций:

имя_класса имя_объекта [(список параметров)]; // список не может быть пустым

имя_класса (список параметров); // создается объект без имени, список может быть пустым

имя_класса имя_объекта= выражение; // создается объект без имени и копируется

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

СStr s1; // создание объекта класса СStr – пустых строк

CStr s2(“aaa”); //создание объекта класса СStr – строки «aaa» с длиной 3

CStr *s3=&s2;//указатель на объект s2

CStr s4=СStr(“bbb”); //создается безымянный объект со значением строки строки «bbb» и длиной 3 и копируется в создаваемый объект s4;

Можно также создать константный объект, значения полей которого изменять запрещается. К нему должны применяться только константные методы, например.

const CStr er(“Error”);

Конструктор – это специальный метод класса, имя которого совпадает с именем класса. Именно конструктор вызывается автоматически при создании объекта класса. В каждом классе есть хотя бы один конструктор. Если он не описан программистом, то создается автоматически. Конструктор не возвращает значения, даже типа void и не наследуется. Конструкторы нельзя описывать со спецификаторами const, virtual, static. Класс может содержать несколько конструкторов с разными типами параметров. Конструктор без параметров или конструктор, все параметры которого имеют значение по умолчанию, называют конструктором по умолчанию. Параметры конструктора могут иметь любой тип кроме типа этого же класса. Один из конструкторов может иметь значения параметров по умолчанию. При задании нескольких конструкторов следует соблюдать те же правила что и при описании перегруженных функций – у компилятора должна быть возможность распознать нужный конструктор по типу параметров.

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

CStr (): len (0) {s=new char; *s=’\0’;}

Специальным видом конструктора является конструктор копирования. Его единственным параметром является указатель на объект этого же класса:

имя класса (const имя класса&){тело}

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

Пример конструктора копирования для класса CStr

CStr::CStr (const CSrt &А)

{

len= strlen(A.s);

s=new char[strlen(A.s)+1];

strcpy(s, A.s);

}

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

Пример деструтора для класса CStr

СStr::~Csrt(){delete [] s};

Доступ к элементам класса осуществляется обычно с помощью операции уточненного имени

имя объекта. имя элемента,

Например,

cout<<s3.get_str()<<s3.get_len();

Если определен указатель на объект, то можно использовать операцию ->, например

cout<<s4->get_str()<<s4->get_len();

Внутри каждого метода неявным образом используется указатель this - это константный указатель на объект, вызвавший метод. Он передается в метод как скрытый параметр. В явном виде указатель this применяется в основном для возращения из метода указателя (return this) или ссылки (return *this) на вызвавший метод объект. Например, рассмотрим метод, сравнивающий длину двух строк и возвращающий строку, имеющую максимальную длину.

CStr & long (CStr & A)

{

if (len>A.get_len()) return *this;

return A;

}

Пример вызова метода:

CStr a(“aaaa”), b(“bbb”);

CStr max=a.long(b);

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

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

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

Синтаксис описания функции-операции

тип operator операция (список параметров) {тело}

Например, опишем операцию удаления из строки последнего символа

class CStr

{ … CStr & operator --() {s[len-1]=’\0’; --len; return *this;} };

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

class CStr

{ bool operator = =(const CStr & st)

{if (strcmp (s, st.get_str())==0) return true; return false; }

}

Приведем пример функции -операции, являющейся дружественной двум классам.

friend ostream& operаtor << (ostream& out, CStr& st)

{return out<<st.s;}

Таким образом, нами описан следущий класс CStr

class CStr

{

protected:

char* s; int len;

public:

CStr(); CStr(char*);

CStr(char); CStr(const CStr&);

CStr& operator=(const CStr&);

bool operator ==(CStr &);

void empty();

operator int(){return len;}

~CStr(){delete[]s; cout<<" \nDestructor! ";}

char* get_str() const {return s;} int get_len()const {return len;}

friend ostream& operator<<(ostream&,CStr&);

}

// Конструктор создания пустой строки

Str::CStr():len(0)

{s=new char;*s='\0'; cout<<"\nContructor1";}

// Конструктор создания строки, равной заданной С- строке

CStr::CStr(char* a)

{s=new char[len=strlen(a)];

strcpy(s,a);

cout<<"\nContructor2";

}

// Конструктор создания строки из одного символа

CStr::CStr(char a)

{s=new char[len=2];s[0]=a; s[1]='\0';cout<<"\nContructor3";}

// Конструктор копирования

CStr::CStr(const CStr& a)

{s=new char[len=a];strcpy(s,a.s);cout<<"\nContructor4 ";}

// Операция присваивания

CStr& CStr::operator = (const CStr & a)

{

if (&a==this) return *this;

if (len) delete []s;

s=new char [len=a];

strcpy(s,a.s);

cout<<" \nDONE == ";

return *this;

}

// Операция сравнения строк

bool CStr::operator ==(CStr & st)

{

if (strcmp (s, st.s)==0) return true;

return false;

}

// Метод, делающий строку пустой

void CStr::empty()

{ if (len)

{ len = 0; delete []s; s = new char; *s= '\0';}

}

// Операция записи в поток вывода на экран

ostream& operator<<(ostream& a, CStr& x)

{return a<<x.s;}

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

Синтаксис описания класса-наследника

сlass имя: [ключ доступа] имя базового класса { тело класса};

Ключ доступа может иметь одно из трех значений private, protected, public

Ключ доступа private (защищенное наследование, действует по умолчанию) – понижает статусы доступа public и protected элементов базового класса до private. Ключ доступа public (открытое наследование) - не изменяет статуса доступа элементов базового класса. Ключ доступа рrotected (защищенное наследование) понижает статус доступа public элементов базового класса до protected.

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

class CBStr: public CStr

{public:

CBStr();

CBStr(char* a);

CBStr& operator = (const CBStr &);

CBStr operator +(const CBStr&);

void empty();

operator int();

};

Рассмотрим поля и методы производного класса.

Все поля базового класса наследуются.

Если поля родителя имеют тип private, то для работы с ними в классе – наследнике необходимо использовать методы базового класса или объявить их явным образом в наследнике в секции public следующим образом имя базового_класса::имя_поля. Например, если бы поля s, len были бы описаны в классе CStr как private, то в классе CBStr их следует объявить следующим образом:

class CBStr: public CStr

{

….

public:

СStr::s;

СStr::len;

….

};

Кроме того, если функциям производного класса требуется работать с полями базового, то в базовом классе такие поля можно описать как protected, как это и сделано в классе CStr.

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

То есть класс CBStr наследует методы empty(), operator ==, operator int(), get_str(), get_len(), и и дружественную функцию-оператор operator<<;

Однако, как мы видим в классе CBStr методы empty(), operator int() переопределены.

//Метод, делающий строку пустой

void CBStr:: empty()

{ if (len)

{ delete []s;

len = 1;

s = new char[2];

s[0]='0';

s[1]= '\0';

}

}

//Функция-операция преобразования типа, возвращающая десятичное значение двоичной строки

CBStr:: operator int()

{

int k=s[len-1]-48;

int st=2;

for (int i=len-2; i>=0; i--)

{ k+=((s[i]-48)*st); st*=2;}

return k;

}

Кроме того, в классе CBStr определен новый метод

// Операция сложения двух двоичных чисел

CBStr CBStr::operator+(const CBStr& a)

{

int l;

if (len>a.len) l=len; else l=a.len;

char * str =new char[l+2];

itoa (int(*this)+int (a), str, 2);

CBStr S(str);

delete str;

return S;

}

Опредлелим конструкторы класса

Предположим, что создание пустой бинарной строки равносильно созданию обычной строки, состоящей из одного символа ‘0’. Тогда конструктор производного класса должен вызывать конструктор базового класса с параметром ‘0’:

CBStr():CStr('0'){}

Конструктор бинарной строки, равной заданной С-строке, должен вызывать конструктор и если созданная строка, содержит символы отличнее от 0 и 1, делать строку пустой

CBStr::CBStr(char* a):CStr (a){if (!bin(a)) empty();}

{ if (!bin(a)) empty(); }

где bin() – функция проверки С-строки на бинарность, empty () – метод, делающий строку пустой.

bool bin(char *a)

{

int i=0;

while (a[i])

{ if (a[i]!='0' && a[i]!='1') return false;

i++;

}

return true;

}

Конструктор копирования создастся автоматически и вызовет конструктор копирования базового класса.

Для класса CBStr не требуется явным образом создавать деструктор, так как удалить бинарную строку это тоже самое, что и удалить строку (если в производном классе деструктор не определен программистом, то он создастся автоматически компилятором, причем из созданного деструктора будет вызван деструктор базового класса.)

Так как операция присваивания не наследуеются, ее необходимо явным образом переопределить

CBStr& CBStr::operator = (const CBStr & a)

{ CStr:: operator = (a);}

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

Рассмотрим пример работы с объектами одной иерархии через указатели.

CStr a("aaa");

CBStr b("101");

CStr * p1=&a;

CBStr * p2=&b;

cout<<"\na= "<<a <<" "<<int(a);

cout<<"\nb= "<<b <<" "<<int(b);

p1->empty();

p2->empty();

cout<<"\na= "<<a <<" "<<int(a);

cout<<"\nb= "<<b <<" "<<int(b);

CBStr c("1011");

CStr * p3=&c;

cout<<"\nc= "<<c <<" "<<int(c);

p3->empty();

cout<<"\nc= "<<c <<" "<<int(c);

Эта программа выведет на экран

a=aaa 3

b=101 5

a= 0

b= 0

c=1011 11

c= -48

Как мы видим, для объекта, на который ссылается указатель p3, был вызван метод empty() базового класса CStr, что семантически неверно. Таким образом, переопределенный метод empty() производного класса оказался недоступным. Это происходит из-за того, что компилятор не может предсказать на объект какого класса будет фактически ссылается указатель во время выполнения программы и выбирает всегда метод базового класса. Чтобы избежать этой ситуации необходимо объявить в баовом классе метод empty() как виртуальный, то есть со спецификатором virtual.

Задание 1. Описание простейшего класса

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

Пример. Решим пример из задания 7.1., заменив описание структуры на описание класса. Описать класс ДАТА с полями ЧИСЛО, МЕСЯЦ, ГОД и следующими методами:

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

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

c) нахождения в массиве введенных дат самой ранней.

Будем использовать технологию модульного программирования для написания программы. Описание класса поместим в заголовочный файл date.h, реализацию методов класса – в файл date.сpp, а главную программу в файл date_main.сpp

// Файл date.h

#ifndef __DATE_H

#define __DATE_H

class date

{

int year;

int month;

int day;

int visokos(int) const;//скрытый метод, проверяющий

//является ли год високосным

public:

date ();//Конструктор

int get_year() const {return year;}// метод,

//возвращающий год

int get_month() const {return month;};}// метод, возвращающий месяц

int get_day() const {return day;};}// метод,

//возвращающий день

void vvod();// метод, обеспечивающий ввод даты

void vivod () const; ();// константный метод,

//обеспечивающий вывод даты

int day_number() const; // константный метод, вычисляющий

// порядковый номер дня в

//году по введенной дате;

date & min (date &);// метод, возвращающий самую

//раннюю из двух дат

};

#endif

Заметим, что в данной задаче нет необходимости описывать конструктор явным образом – он создастся автоматически и будет корректно работать, так как в классе нет полей, память под которые выделяется динамически. Однако мы описали конструктор явным образом. В теле конструктора укажем отладочную запись cout<<"Done!"; чтобы увидеть, в какие именно моменты работает конструктор. Этот прием полезен для начинающих программистов и для выявления трудно диагнастируемх ошибок.

// Файл date.cpp

#include <iostream.h>

#include <iomanip.h>

#include "date.h"

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}};

/************************* конструктор*********************************

date:: date (){cout<<"Done!";}

/******* Метод, проверяющий является ли год високосным******

int date:: visokos(int year) const

{

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

return k;

}

//*********Метод, обеспечивающий ввод даты*****************

void date::vvod()

{

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

cin>>day>>month>>year;

int k=visokos(year);

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

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

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

}

//*********Метод, обеспечивающий ввод даты****************

void date:: vivod () const

{

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

}

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

int date::day_number() const

{

int d=day;

int k=visokos(year);

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

d+=tab_day[k][i];

return d;

}

//********Метод, возвращающий раннюю из двух дат **********

date & date:: min (date & M)

{

if (year<M.get_year() || year==M. get_year()&&(month<M.get_month()|| month==M.get_month()&& day<M.get_day())) return *this;

return M;

}

//Файл date_main.cpp

# include <iostream.h>

# include <stdio.h>

# include <conio.h>

# include <stdlib.h>

# include "date.h"

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; d.vvod(); break;}

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

case 3: {date d; d.vvod(); cout<<"\nПорядковый номер"<<d.day_number(); 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";

date m=mas[0];

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

{

mas[i].vivod();

m=mas[i].min(m);

}

cout<<"\nСамая ранняя ";

m.vivod();

delete []mas;

break;

}

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

}

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

goto N;

}

Задание 2. Класс string

Каждому студенту рекомендуется выполнить хотя бы одно из упражнений 1-12 задания 3 из параграфа 1.6, использую класс string.

В С++ описан стандартный класс string, который обеспечивает различные операции для манипулирования строками. Данный класс описывается в заголовочном файле cstring.h.

В классе string имеется несколько конструкторов. Ниаболее употребляемыми из них явлются конструктор, создающий пустую строку - string () и конструктор, создающий строку со значением С-строки - string (const char*).

Например,

string S1, S2; // создали два объекта класса string – пустые строки

string S3 (“Hello!!!”);// создали объект класса string – строку со значение “Hello!!!”

Класс содежит три операции присваивания:

string& opertor=(const srting& str); // присваивание объекта-строка

string& opertor=(const char *str);// присваивание значения С-строки

string& opertor=(char s);// присваивание значения символа

Например,

string S4=S3, S5= “Error”, S6= ‘a’;

В классе string опрделена константа NPOS, задающая максимально возможное число, которое в зависимости от конекста означет либо «все элементы строки», либо отрицательный результат поиска.

В классе переопредлены следющие операции

Опреция	Значение
=	присваивание
+	конкантенация
== (!=)	равенство(неравенство)
< (<=)	меньше (меньше или равно)
> (>=)	больше (больше или равно)
[ ]	индексация
<< (>>)	вывод(ввод)
+=	добавление

Пример 1. Ввести с клавиатуры два слова. Если они одинаковы, то вывести на экран их первый символ, в противном случае вывести строку, состоящую из этих слов, разделенных пробелом.

# include <iostream.h>

# include <cstring.h>

void main()

{

int k,k1;

string s1,s2;// описали два объекта класса string

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