Динамические структуры данных

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ

ЭЛЕКТРОТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

«ЛЭТИ» ИМ. В.И. УЛЬЯНОВА (ЛЕНИНА)

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

ОТЧЕТ

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

по дисциплине «Программирование»

Тема: Динамические структуры данных

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

2024

1. Цель работы

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

Задание

        Вариант №2

        Стековая машина.

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

1) Реализовать класс CustomStack, который будет содержать перечисленные ниже методы. Стек должен иметь возможность хранить и работать с типом данных int.

Перечень методов класса стека, которые должны быть реализованы:

• void push(int val) -  добавляет новый элемент в стек
• void pop() - удаляет из стека последний элемент
• int top() - доступ к верхнему элементу
• size_t size() - возвращает количество элементов в стеке
• bool empty() - проверяет отсутствие элементов в стеке

2) Обеспечить в программе считывание из потока stdin последовательности (не более 100 элементов) из чисел и арифметических операций (+, -, *, / (деление нацело)) разделенных пробелом, которые программа должна интерпретировать и выполнить по следующим правилам:

Если очередной элемент входной последовательности - число, то положить его в стек,

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

Если входная последовательность закончилась, то вывести результат (число в стеке).

Если в процессе вычисления возникает ошибка:

например вызов метода pop или top при пустом стеке (для операции в стеке не хватает аргументов),

по завершении работы программы в стеке более одного элемента,

программа должна вывести "error" и завершиться.

Примечания:

Указатель на голову должен быть protected.

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

Предполагается, что пространство имен std уже доступно.

Использование ключевого слова using также не требуется.

Структуру ListNode реализовывать самому не надо, она уже реализована.

Выполнение работы

Файлы:

main.cpp — содержит код, выполняющий задачу.

Переменные:

CustomStack stack — объект класса CustomStack для работы со стеком.

int* mData — данные хранящиеся в узле стека.

ListNode* mNext — указатель на следующий элемент стека.

ListNode* mHead — указатель на голову стека.

int counter — счетчик элементов стека.

char* buffer — буфер для считывания очередного элемента.

int firstNumber — предпоследний элемент стека.

int secondNumber — последний элемент стека.

int operand — значение, соответствующее операнду в перечислении.

Функции и методы:

int main() — точка входа в программу.

static void returnError() — метод, возвращающий сообщение об ошибке и завершающий программу.

int calculate() — возвращает результат для переданной последовательности чисел и операндов.

CustomStack() — конструктор класса.

~CustomStack() — деструктор класса.

void push(int value) — добавляет в стек элемент со значением value.

void pop() — удаляет из стека последний элемент.

int top() — возвращает значение последнего элемента стека.

size_t size() — возвращает размер стека.

bool empty() — возвращает true, если стек пуст, иначе false.

int getOperand(char* str) — возвращает числовое значение, соответствующее переданному операнду.