Задание 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
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
Основы объектно-ориентированного программирования
Осовными принципами объектно-ориентированного программирования явлются инкапсуляция, наследование и полиморфизм. Принцип инкапсуляции в ООП реализуются с помощью механизма классов. Класс является абстрактным типом данных, определяемым пользователем, и содержит описание данных и функций для работы с этими данным.
Описать класс возможно следующим образом:
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.
Дата добавления: 2015-10-09; просмотров: 1287;