Калькулятор на С. 9301_КряжевскихЕА_курсовая. Преобразование алгебраических формул из инфиксной в постфиксную форму записи и вычисление значения выражения

• Название: Преобразование алгебраических формул из инфиксной в постфиксную форму записи и вычисление значения выражения
• Анкор: Калькулятор на С
• Дата: 29.03.2022
• Размер: 84.44 Kb.
• Имя файла: 9301_КряжевскихЕА_курсовая.docx
• Тип: Курсовая; #425611

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

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

Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” им. В. И. Ульянова (Ленина) (СПбГЭТУ «ЛЭТИ»)









Кафедра САПР

курсовая работа

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

Тема: «Преобразование алгебраических формул из инфиксной в постфиксную форму записи и вычисление значения выражения»

Вариант № 1

Студент(ка) гр. 9301, ФКТИ		Кряжевских Е.А.
Преподаватель		Тутуева А.В.

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

2020 г.

Постановка задачи

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

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

Необходимо включить в работу программы тригонометрические функции, логарифмы, экспоненциальную функцию, модуль и корень числа, а также такие константы как число π=3,14159 и число е=2,71828.

Используемые структуры данных.

В своей программе я реализовала 3 класса: «class Calculator», «class Queue» и «class Stack».

В классе «Calculator» располагается структура «Element», 5 методов для взаимодействия со списком элементов (вставка в конец, удаление с конца, получение размера списка, получение элемента по индексу и вывод списка на экран), а также различные методы, необходимые для решения поставленной задачи. Структура «Element» реализована для хранения данных элементов выражения и удобного передвижения по списку.

Структуры Queue и Stack были выбраны из соображений простоты реализации и не высокой временной сложности.

Алгоритм решения.

Пользователь вводит с клавиатуры формулу, которая записывается программой как символьная строка. Далее программа обрабатывает эту строку на наличие неизвестных символов и корректность ввода, после чего заполняет список элементов выражения. Элементы в список записываются в виде строк. Заполненный список отправляется снова на проверку корректности ввода и если ошибок не возникло, то значит данное выражение можно преобразовать в постфиксную форму.

Элементы списка обрабатываются по-отдельности слева направо и каждому присваивается свой приоритет.

Приоритет операций в программе:

Оператор	Приоритет
Унарный минус	5
Различные функции	4
Возведение в степень	3
Умножение/деление	2
Сложение/вычитание	1
Скобки	0

Далее следуем алгоритму:

1. 
   Если просматриваемый символ является левой скобкой, помещаем его в стек;
   
2. 
   Если просматриваемый символ – операнд, добавляем его в список с постфиксной записью;
   
3. 
   Если просматриваемый символ является правой скобкой, извлекаем из стека все символы до появления левой скобки и добавляем их в список с постфиксной записью;
   
4. 
   Если просматриваемый символ является оператором, удаляем все операторы из стека (пока не увидим оператор с меньшим приоритетом) и помещаем их в список с постфиксной записью, если и только если приоритет оператора, который находится наверху стека, больше или равен приоритету просматриваемого оператора. Затем помещаем просматриваемый оператор в стек. Иначе помещаем просматриваемый оператор в стек сразу.
   

Таким образом у нас есть список с постфиксной записью элементов выражения. Этот список элементов программа выводит на экран пользователю.

Далее вычисляем значение выражения в постфиксной форме по следующему алгоритму:

1. 
   Если просматриваемый символ является операндом, то помещаем его в стек;
   
2. 
   Если просматриваемый символ является оператором, то применяем его к операндам, которые извлекаем из стека. Результат снова помещаем в стек.
   

После того, как программа посчитает все выражение, в стеке останется единственное значение. Это значение и будет являться результатом работы программы. Достаем его из стека и выводим пользователю на экран.

Реализованные методы.

Для решения поставленной задачи я реализовала 4 основных функции:

1. 
   Функция processing_string – обрабатывает строку, проверяет на корректность ввода и создает список из допустимых для программы элементов;
   
2. 
   Функция check_for_error – еще раз проверяет список на корректность ввода и в случае ошибки выводит соответствующее сообщение пользователю на экран;
   
3. 
   Функция infix_to_postfix – переводит обработанную строку в постфиксную форму, согласно алгоритму, описанному выше;
   
4. 
   Функция count_postfix – вычисляет значение выражения в постфиксной форме и возвращает результат вычислений;
   

И 11 дополнительных функций для корректной работы программы:

5. 
   Функции is_digit_char и is_digit_string – проверяют является ли символ или строка соответственно числом;
   
6. 
   Функции is_character_char и is_character_string – проверяют является ли символ или строка соответственно словом или буквой;
   
7. 
   Функции is_operation_char и is_operation_string – проверяют является ли символ или строка соответственно оператором;
   
8. 
   Функция prior – определяет приоритет оператора;
   
9. 
   Функция functions – определяет является ли слово функцией;
   
10. 
    Функции CountFuncions и CountOperations – рассчитывают значения;
    
11. 
    Функция unary_minus – умножает число на (-1).
    

Описание реализованных unit-тестов.

Для проверки работоспособности программы реализовано 15 unit-тестов.

Для функции processing_string реализовано 4 unit-теста: формула введена корректно, введено две точки или запятых подряд, введен неизвестный символ и проверка на правильность заполнения списка элементов.

Для функции check_for_error реализовано 5 unit-тестов. Рассмотрены следующие ошибки: аргумент функции без скобок, после символа идет число, после символа идет функция, введено два оператора подряд и неравное количество скобок.

Для функции infix_to_postfix реализован 1 unit-тест: правильность заполнения постфиксной формы.

Для функции count_postfix реализовано 5 unit-тестов: все пять - это проверка на правильность посчитанных значений.

Пример работы.

Пример 1 – Корректно введенная функция



Пример 2 –Корректно введенная функция.



Пример 3 – Некорректно введенная функция.


Пример 4 – Корень из отрицательного числа.



Пример 5 – Аргумент функции не в скобках.



Пример 6 – Деление на 0.


Листинг.

https://github.com/Elizaveta-git/Calculator.git