Материал: Larin_Anton_AiSD_21_3

МИНОБРНАУКИ РОССИИ

Санкт-Петербургский государственный

электротехнический университет

«ЛЭТИ» им. В.И. Ульянова (Ленина)

Кафедра МО ЭВМ

отчет

по лабораторной работе №3

по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННЫХ»

Тема: Стеки и очереди

Санкт-Петербург

2019

Цель работы.

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

Основные теоретические положения.

Стек - это структура данных, в которой хранятся элементы в виде последовательности, организованной по принципу LIFO (Last In — First Out). Такую структуру данных можно сравнить со стопкой тарелок или магазином автомата. Стек не предполагает прямого доступа к элементам и список основных операций ограничивается операциями помещения элемента в стек и извлечения элемента из стека. Их принято называть PUSH и POP соответственно. Также, обычно есть возможность посмотреть на верхний элемент стека не извлекая его (TOP) и несколько других функций, таких как проверка на пустоту стека и некоторые другие.

Пример добавления и удаления элементов из непустого стека (содержащего единицу)

Очередь

Очередь - эта структура данных, в которой хранятся элементы в виде последовательности, организованной по принципу FIFO (First In — First Out). Эта структура данных более естественна - например, очередь в магазине. Также как и стек, очередь не предполагает прямого доступа к элементам, а основные операции: добавление ENQ (enqueue) и извлечение DEQ(dequeue). Также обычно есть функции получения первого элемента без его извлечения, определения размера очереди, проверки на пустоту и некоторые другие.

Рассмотрим способы реализации таких структур данных как стек и очередь. Фактически, обе структуры данных можно представлять в памяти либо в виде однонаправленного списка, либо в виде массива.

Представление в виде списка

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

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

Представление в виде массива

Стек можно легко реализовать на основе массива. Для этого достаточно хранить индекс "верхнего" элемента в стеке. Операция добавления сопровождается инкрементом этого индекса и записью в соответствующую ячейку нового значения. Операция извлечения сопровождается декрементом этого индекса. Дополнительно, может потребоваться реализовать возможность увеличения и уменьшения размера массива

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

Задание

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

Вариант 5-в

Правильная скобочная конструкция с тремя видами скобок определяется как

< текст > ::= < пусто > | < элемент > < текст >

< элемент > ::= < символ > | ( < текст > ) | [ < текст > ] | { < текст > }

где < символ > - любой символ, кроме ( , ) , [ , ] , { , }. Проверить, является ли текст, содержащийся в заданном файле F, правильной скобочной конструкцией; если нет, то указать номер ошибочной позиции.

Реализация

В основной функции main последовательно происходит:

Вызов функций parseArgs, которая обрабатывает аргумента командной строки;

Затем, если требуется, открытие файлов на вход и выход;

Вызов функции input для считывания данных из потока ввода (либо автоматический сгенерированных функцией ) в строку.

Строка передается в рекурсивную функцию processStr, которая выполняет е рекурсивную обработку(проверку) с использованием стэка

Описание основной функции для решения задачи

char processStr(string str,int &i,int reclvl=0);

Функция принимает строку для проверки str, ссылку-индекс i для обратной связи и глубину рекурсии reclvl для форматного вывода.

Тело функции представляет из себя цикл, проходящий по текущему уровню скобочной записи.

Перед циклом задается стек для хранения скобок. Его пустота свидетельствует о сбалансированности скобочной записи

Внутри цикла в первую очередь происходит всех символов-не скобок и проверка, не был ли достигнут конец строки. Если был — возвращается 0, как знак, что последовательность корректна. В противном случае функция возвращает верхушку стэка — несбалансированную скобку. Индекс содержит индект в строке, на котором произошел сбой. Далее идет проверка текущего символа(скобки, ибо все не скобки промотаны). Если встречена открывающаяся скобка- она кладется в стек и происходит рекурсивный вызов функции с данной позиции для обработки подстроки заключенной в скобки. Функция продолжает работать с позиции окончания предыдущей т. е. с закрывающейся скобки. Если встречена закрывающаяся скобка то идет проверка верхней скобки стэка. Если закрытая скобка соответствует предыдущей открытой, то открытая убирается из стэка как сбалансированная. Если закрытая скобка не соответствует последней открытой то функция возвращает верхнюю скобку в стэке(и сохраняет индекс в i), предполагая что данная скобка является ошибкой(происходит цепное выныривание из рекурсии до вызвавшей изначальной функции), либо соответствует скобочной записи на уровень выше.

Цикл замыкается, идет проверка остальных скобок на данной глубине.

Результат выводится в консоль и, опционально, в файл.

Описание структуры данных и функций

Стэк

template <class Elem>

class Stack

Elem* vec;//Контейнер — вектор

int topOfStack;//Указатель на вершину стэка

Функции для работы со стэком

bool isEmpty(void)

Elem top(void) //Returns top element

Elem ttop(void) //TERMINAL TOP. Reterns top element destroying stack right after(for usage like: return stack.ttop();)

void pop(void)//Removes top element

Elem pop2(void)//Removes top element and returns it.

void push(const Elem &x)//Push element on top

void recClear()//recusrive clear

void destroy(void)//Suicide

Программа поддерживает настройку при помощи параметров из командной строки. Получить информацию от них можно аргументом «-h»

Они следуюшие:

-h help

-A Автоматическое считывание данных строка за строкой для автоматизированной проверки

-r Дает выбор перезапустить программу после исполнения.

-i [file] Ввод из файла file, вместо стандартного потока stdin («in» по умолчанию)

-o [file] Вывод в файл file помимо стандартного потока stdout («out по умолчанию»)

Тесты.

1.

Input:

(qwe)

Inter results:

(

<-

)

Result:

Correct!

2.

Input:

{asd}

Inter results:

{

<-

}

Result:

Correct!

3.

Input:

{qwe[asd]zxc(tyu)zxc}

Inter results:

{

[

<-

]

(

<-

)

<-

}

Result:

Correct!

4.

Input:

(ad[]dwmk{dq[dqw]ffwq}zz)

Inter results:

(

[

<-

]

{

[

<-

]

<-

}

<-

)

Result:

Correct!

5.

Input:

Inter results:

Result:

Correct!

6.

Input:

)Booooo(!)

Inter results:

<-

Result:

) <<ERROR HERE!

Unexpected ')'

7.

Input:

{What's this!---->[a]}(

Inter results:

{

[

<-

]

<-

}

(

Result:

Bracket '(' left unclosed

8.

Input:

[This ([is] {not}) {bracket] youre} (looking for)

Inter results:

[

(

[

<-

]

{

<-

}

<-

)

{

<-

<-

Result:

[This ([is] {not}) {bracket] <<ERROR HERE!

Expected '{' while got ']'

Выводы.

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

Приложение(листинг программы)

Векторная реализация стэка

st_interf2.h

#include<iostream>

//Memory is allocated for BLOCK elements at once

#define BLOCK 16

namespace st_modul2 {

//-------------------------------------

template <class Elem>

class Stack {

private:

Elem* vec;

//std::vector<Elem>* vec;

int topOfStack;

//size_t alloc_mem;

//node *topOfStack;

public:

Stack() {

vec=0;

topOfStack=-1;

}//;

// -------------------------------------

bool isEmpty(void)//

{

return (topOfStack<0);

}

//-------------------------------------

Elem top(void) //Returns top element

{// PreCondition: not null

if (this->isEmpty()) {

std::cerr << "Error: top(Empty) \n";

exit(1);

}

else return vec[topOfStack];

}

Elem ttop(void) //TERMINAL TOP. Reterns top element destroying stack right after(for usage like: return stack.ttop();)

{// PreCondition: not null

if (this->isEmpty()) {

std::cerr << "Error: ttop(Empty) \n";

exit(1);

}

else {auto ret = vec[topOfStack]; destroy(); return ret;}

}

//-------------------------------------

void pop(void)//Removes top element

{// PreCondition: not null

if (this->isEmpty()) {

std::cerr << "Error: pop(Empty) \n";

exit(1);

}

else {

if(topOfStack%BLOCK==0)vec=(Elem*)realloc(vec,sizeof(Elem)*topOfStack);

topOfStack--;

}

}

//-------------------------------------

Elem pop2(void)//Removes top element and returns it.

{// PreCondition: not null

if (this->isEmpty()) {

std::cerr << "Error: pop2(Empty) \n";

exit(1);

}

else {

Elem r = this->top();

this->pop();

return r;

}

}

//-------------------------------------

void push(const Elem &x)//Push element on top

{

topOfStack++;

if(topOfStack%BLOCK==0)

vec=(Elem*) realloc(vec,sizeof(Elem)*(topOfStack+BLOCK));

if(!vec){

std::cerr << "Can not allocate more memory!\n";

exit(1);

} else{

vec[topOfStack]=x;

}

}

//-------------------------------------

void destroy(void)//Suicide

{

topOfStack=0;

if(vec)

{

delete vec;

vec=0;

}

//delete this;

}

};

}

Основной код

main2.cpp

#include <iostream>

#include <fstream>

#include <cstdlib>

#include <vector>

#include <sstream>

#include "st_interf2.h"

#define DEFAULT_IFILE_NAME "in"

#define DEFAULT_OFILE_NAME "out"

#define BUF_SIZE 1024

//#define printStr(str) cout<<(str)

using namespace std;

istream *inFile = NULL;

bool readFromFile= false;

ostream *outFile = NULL;

bool printToFile= false;

bool repeat= false;

bool awto = false;

int awtoLim = 0;

void help(){

cout<<"-h\t\thelp\n";

cout<<"-A\t\tAuto reading input line by line\n";

cout<<"-r\t\tchose to repeat input after compliton. Incompatable with \"-i\"!\n";

cout<<"-i [file]\t input from file (\""<<DEFAULT_IFILE_NAME<<"\" by default)\n";

cout<<"-o [file]\t output to file (\""<<DEFAULT_OFILE_NAME<<"\" by default)\n";

}

void setIFile(istream* istr){

//cin.rdbuf()

//cin.rdbuf((*istr).rdbuf());

inFile=istr;

}

void setOFile(ostream* ostr){

//cout.rdbuf((*ostr).rdbuf());

outFile=ostr;

}

int parseArgs(int argc, char** argv, string &iFileName, string &oFileName); //Parses arguments. Returns 1 if program is to be closed

char bracketPair(char b);

char processStr(string str,int &i,int reclvl=0);

void printStr(string str);

int input(string &inp);

using namespace st_modul2;

int main (int argc, char** argv ) {