Стеки и очереди

Министерство науки и высшего образования Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего образования

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

Кафедра автоматизированных систем управления (АСУ)

СТЕКИ И ОЧЕРЕДИ

Отчет по лабораторной работе №1

По дисциплине

«Структуры и алгоритмы обработки данных в ЭВМ»

       Выполнил: студент гр. 430-4

_______________ Куминов П.А.

«___»___________ 2021 г.

       Проверил: ассистент каф. АСУ

_______________ Яблонский Я.В.

«___»___________ 2021 г.

Томск 2021

1 Задание на лабораторную работу

Используя стек, решить следующую задачу: в текстовом файле F записана без ошибок формула следующего вида: <формула> ::= <цифра> | М(<формула>, <формула>) | m(<формула>, <формула>) <цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9, где М обозначает функцию max, а m - min. Вычислить как целое число значение данной формулы. Для реализации АТД Стек использовать массив.

2 Алгоритм решения задачи

        Заголовки функций и цифры заносят в стек в очереди своего следования.

        Так как стек работает по принципу Last-In-First-Out, то мы идем с конца формулы. Считываются три значения из стека. Предполагается, что два первых будут цифрами, а третий – названием вызываемой функции. В случае, если это не так, то первое считанное значение заносится во временное хранилище safe, а затем считывается из стека еще одно значение, которое точно будет заголовком функции.

        После этого вызывается одна из двух функций – минимума или максимума – в зависимости от последнего считанного значения. Результат функции кладется в стек. Если во временном хранилище лежало какое-то значение, то оно также возвращается в стек.

        Данный алгоритм циклично выполняется до тех пор, пока в стеке не останется единственный элемент – результат выполнения внешней функции.

3 Текст программы

3.1 Текст заголовочного файла класса

#pragma once

class Stack

{

        private:

                static const int STACK_SIZE = 32; // максимальный размер стека

                char array[STACK_SIZE];

                int T;

        public:

                Stack();

                void Push(char Y);

                char Pop();

                char Top() const;

                bool IsEmpty() const;

};

3.2 Текст файла реализации класса

#include "Stack.h"

#include <process.h>

Stack::Stack()

{

        T = -1;

}

void Stack::Push(char Y)

{

        if (T + 1 == STACK_SIZE)

                _cexit();

        T++;

        array[T] = Y;

}

char Stack::Pop()

{

        if (IsEmpty())

                _cexit();

        else {

                T--;

                return array[T+1];

        }

}

char Stack::Top() const

{

        if (IsEmpty())

                _cexit();

        else

                return array[T];