#Обработка и перевод арифметического выражения в обратную польскую форму
##Постановка задачи Основная задача лабораторной работы — разработать статическую библиотеку на языке С++, реализующую динамическую структуру данных — стек. Структура стек основана на динамической структуре данных - список.
Необходимо создать репозиторий на сайте (http://github.com), в котором будут отображены все действия с проектом с соответствущими комментариями.
Так же необходимо написать тестирующие программы для каждого метода структур данных с помощью Google C++ Testing Framework.
В качестве примера работы со стеками, разработать программу, реализующую обработку арифметического выражения и его перевод в постфиксную форму.
Написать консольные приложения, где будет демонстрироваться работа со списками, стеками и обработчиком арифметического выражения.
##Руководство пользователя ###Запуск приложения и ввод данных
Консольное приложение предназначено для обработки и перевода сивольного арифметического выражение из прямой (инфиксной) в обратную (постфиксную) форму и для дальнейшего подсчета выражения с введенными пользователем данными.
Чтобы запустить приложение, необходимо открыть исполняемый файл sample_postfix.exe
и следовать инструкциям.
Пример:
-
По очереди введите значения каждой переменной и получите результат.
-
Для завершения работы нажмите любую клавишу.
##Руководство программиста ###Общая структура проекта
Структура проекта:
gtest
— библиотека Google Test.img
— директория с изображениями, используемых в отчете к лабораторной работе.include
— директория для размещения заголовочных файлов.samples
— директория для размещения тестового приложения.sln
— директория с файлами решений и проектов для Visual Studio 2015.src
— директория для размещения исходных кодов.test
— директория с тестами для каждого модуля и основным приложением, инициализирующим запуск.README.md
— отчет о лабораторной работе.- Служебные файлы
.gitignore
— перечень расширений файлов, игнорируемых Git при добавлении файлов в репозиторий.
###Описание структуры программы
Программа состоит из 6 проектов:
gtest
— фреймворк Google Test.postfix_form
- статическая библиотека, которая содержит объявление и реализацию шаблонных классовnode
,list
,stack
и классаpostfix
.node
— описывает "узел" списка. "Узел" хранит в себе значение "ключа" и указатель на следующий узел, включает в себя конструктор по умолчанию и конструктор копирования.list
— класс "список", агрегирующий в себе классnode
, включается в себя конструктор по умолчанию, конструктор копирования, деструктор и 10 методов по работе с элементами списка.stack
— класс "стек", агрегирующий в себе классlist
, включающий в себя конструктор по умолчанию, конструктор копирования, деструктор и 7 методов по работе с элементами стека.postfix
- класс обработки арифметического выражения в постфиксную форму, использующий классstack
и включающий в себя 3 метода по обработке строки и 2 метода для обработки арифметического выражения:Record
- метод перевода выражения в постфиксную форму, запрашивающий данные переменных у пользователя;Count
— метод вычисления результата, использующий введенные данные. Входные данные - выражение в постфиксной форме, выходные данные - числа заданного типа.
sample_list
— консольное приложение, демонстрирующее работу методов классаlist
, не требует ввода данных пользователем.sample_stack
— консольное приложение, демонстрирующее работу методов классаstack
, не требует ввода данных пользователем.sample_postfix
— консольное приложение, являющееся калькулятором, который принимает арифметическое выражение, переводит его в постфиксную форму и осуществляет подсчет данных.test
— консольное приложение, использующее библиотеку Google Test, проверяющее корректность реализации методов классовlist
иstack
. Содержит 39 тестов.
###Описание структур данных ####Структура данных "список"
Односвязный линейный список — динамическая структура данных, имеющая неограниченное количество элементов. Состоит из узлов, каждый из которых содержит данные определенного типа и указатель на следующий элемент списка. Признак конца списка - равенство указателя нулю. Начало списка - указатель на его первый элемент (First). Особенностью списка является хранение элементов в памяти: последовательно идущие элементы могут располагаться в памяти совершенно в другом порядке.
Динамическая структура данных "список" представлена в лабораторной работе в виде шаблонного класса list
, который содержит в себе следующие методы:
- Конструктор по умолчанию;
- Конструктор копирования;
- Деструктор;
Print
— метод печати элементов списка;Find
— метод поиска элемента с заданным ключом, возвращающая указатель на элемент;Remove
— метод удаления элемента с заданным ключом;PushStart
— метод создания и вставки элемента с заданным ключом в начало списка;PushEnd
— метод создания и вставка элемента с заданным ключом в конец списка;PushtBefore
— метод создания и вставка элемента с заданным ключом перед элементом с заданным ключом;PushAfter
— метод создания и вставки элемента с хаданным ключом после элемента с заданным ключом;GetFirst
— метод, возвращающий указатель на первый элемент списка;operator==
- перегруженный метод сравнения списков на равенство;operator!=
- перегруженный метода сравнения списков на неравенство. Данные методы протестированы в проектеtest
в файлеtest-list.cpp
и продемонстрированы в проектеsample_list.exe
.
####Структура данных "стек"
Стек — динамическая структура данных, которая хранит наборы однотипных элементов и работает по принципу "первый вошел - последний вышел".
Динамическая структура данных "стек" представлена в лабораторной работе в виде шаблонного класса stack
, основанного на односвязном списке и содержащего следующие методы:
- Конструктор по умолчанию, который явно вызывает конструктор класса
List
; - Конструктор копирования;
- Деструктор;
IsEmpty
— метод проверки стека на пустоту;IsFull
— метод проверки стека на полноту (наличие памяти для создания элемента);Push
— метод добавления элемента с заданным ключом на вершину стека;Pop
— метод изъятия элемента с вершины стека, возвращающийзначение элемента;Print
— метод печати элементов стека;operator==
- перегруженный метод стравнения стеков на равенство;operator!=
- перегруженный метод сравнения списков на неравенство; Данные методы протестированы в проектеtest
в файлеtest-stack.cpp
и продемонстрированы в проектеsample_stack.exe
.
###Описание алгоритмов
####Алгоритм перевода в постфиксную запись
Описание алгоритма перевода из инфиксной записи в постфиксную:
-
Строка обрабатывается, смотрится корректность записи арифметического выражения, количество скобок.
-
Каждой операции ставится приоритет:
- Операциям умножения
*
и деления/
ставится приоритет 3. - Операциям сложения
+
и вычитания-
ставится приоритет 2. - Операции открывающей скобки
(
ставится приоритет 1.
- Операциям умножения
-
Создается 2 стека: стек для хранения результата
result
и стек для хранения операцийoperationsstack
. -
Выражение просматривается слева-направо, при этом возможно 4 случая:
- Встретился операнд, который добавляется в стек
result
; - Встретилась операция, приоритет которой выше, чем приоритет операции, лежащей на вершине стека
operationsstack
, или этот стек пуст. В этом случае операция добавляется в стек для хранения операцийoperationsstack
. - Встретилась операция, приоритет которой равен или ниже приоритета операции, лежащей на вершине стека
operationsstack
, тогда этом случае все операции, приоритет которых больше данной перекладываются в стекresult
, пока на вершине стекаoperationstack
не появится операции с меньшим приоритетом илиoperationsstack
не станет пустым. Следующая операция добавляется в стек хранения операций. - Встретилась операция ")", тогда из стека
opeartionsstack
все элементы перемещаются в стекresult
до первого вхождения "(", которая удаляется из стека.
- Встретился операнд, который добавляется в стек
-
Все операции из стека операций
operationsstack
перемещаются в стек хранения результатаresult
.
####Алгоритм подсчета выражения в постфиксной записи
Описание алгоритма вычисления арифметического выражения в постфиксной форме:
-
Создается стек с заданным типом данных ExpType
result
. -
Выражение просматривается слева-направо, при этом возможно 2 случая:
- Встретился операнд, тогда от пользователя запрашивается его значение и добавляется на вершину стека
result
. - Встретилась операция, огда из стека
result
изымаются 2 операнда, над ними совершается указанная операция, и результат добавляется в стек.
- Встретился операнд, тогда от пользователя запрашивается его значение и добавляется на вершину стека
-
При полном проходе выражения в стеке останется численный результат выражения с заданными значениями.
##Заключение В ходе лабораторной работы была разработана программа, реализующая обработку и перевод арифметического выражение в обратную польскую форму. Динамические структуры "узел", "список" и "стек" были реализованы с помощью шаблонных классов для преобразования выражения. Для каждого метода каждого класса были написаны тесты, проверяющие корректность работы, и приложения, показывающие работу методов классов. Приложение для списка и стека показывало работу с методами, не запрашивая данных у польхователя, приложение для преобразования выражения представляет собой калькулятор, который запрашивает арифметическое выражение и значение переменных. Все введенные выражения были подсчитаны правильно. Так же была использована система управления версиями Git: была создана ветка, в которой выполнялась реализация лабораторной работы. По мере добавления методов, тестов и приложений файлы добавлялись в репозиторий с соответствующими комментариями. Данная система позволяет отслеживать выполнение работы и восстанавливать данные в случае их потери.
##Литература
- Шилдт Г. Полный справочник по С++ - М.: Вильямс, 2006. — 791 с.