Материал: Larin_Anton_AiSD_21_3 (copy)

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

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

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

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

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

отчет

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

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

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

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

2019

Цель работы.

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

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

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

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

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

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

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

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

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

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

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

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

Задание

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

Вариант 5-в

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

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

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

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

Реализация

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

Стек

template <class Elem>

На базе вектора

Elem* vec;

int topOfStack;

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

bool isEmpty(void)// Возвращает true если стек пуст

Elem top(void) //Возвращяет верхний элемент

Elem ttop(void) //Возаращает верхний элемент, затем удаляет стек(для конструкций return stack.ttop();)

void pop(void)//Удаляет верхний элемент

Elem pop2(void)//Удаляет и возвращает верхний элемент

void push(const Elem &x)//Кладет элемент на верх стека

void recClear()//Рекурсивная функция отчистки стека

void destroy(void)//Suicide

Функции реальзованные для решения задачи

int input(string &inp);//Ввод скобочной последовательности из выбранного потока

void printStr(string str);//Вывод данных в выбранный поток

char bracketPair(char b);//Принимает скобку, возвращает ее пару

int processStr(string str);/Основная функция обработки скобочной последовательности

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

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

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

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

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

Описание основной рекурсивной функции

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

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

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

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

Внутри цикла в первую очередь происходит всех символов-не скобок и проверка, не был ли достигнут конец строки.

Если был — возвращается 0, как знак, что последовательность корректна.

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

Далее идет проверка текущекго символа(скобки, ибо все не скобки промотаны)

Если встречена открывающаяся скобка- она кладется в стек и происходит рекурсивный вызов функции с данной позиции для обработки подстроки заключенной в скобки. Функция продолжает работать с позиции окончания предудущей т. е. с закрывающейся скобки

Если встречена закрывающаяся скобка то идет проверка верхней скобки стека.

Если закрытая скобка соответствует предудущей открытой, то открытая убирается из стека как сбалансированная.

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

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

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

Программа поддерживает настройку при помощи параметров из командной строки. Получить информацию от них можно аргументом «-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:

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

Stack:

(

Bracket '(' left unclosed

8.

Input:

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

Inter results:

<< [

[ << (

[ ( << [

[ ( >> [ <]>

[ ( << {

[ ( >> { <}>

[ >> ( <)>

[ << {

Result:

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

Stack:

[ {

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:

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

//size_t alloc_mem;

//node *topOfStack;

public:

Elem* vec;

int topOfStack;

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 {recClear(); 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 recClear()//recusrive clear

{

if (!vec) {

return;

}

if(!this->isEmpty()){

pop();

recClear();

}

return;

}

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

void destroy(void)//Suicide

{

recClear();

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;