Калькулятор на С. 9301_КряжевскихЕА_курсовая. Преобразование алгебраических формул из инфиксной в постфиксную форму записи и вычисление значения выражения
Скачать 84.44 Kb.
|
МИНОБРНАУКИ РОССИИ Федеральное государственное автономное образовательное учреждение высшего образования Санкт-Петербургский государственный электротехнический университет “ЛЭТИ” им. В. И. Ульянова (Ленина) (СПбГЭТУ «ЛЭТИ») Кафедра САПР курсовая работа по дисциплине «АЛГОРИТМЫ И СТРУКТУРЫ ДАННХ» Тема: «Преобразование алгебраических формул из инфиксной в постфиксную форму записи и вычисление значения выражения» Вариант № 1
Санкт-Петербург 2020 г. Постановка задачиНеобходимо написать программу для преобразования алгебраических формул из инфиксной в постфиксную форму записи и вычислить значение введенного выражения. Пользователю должен быть доступен ввод выражения, которое состоит из цифр, функций и арифметических знаков. Программа должна проверять строку на корректность ввода и выводить пользователю сообщение с типом ошибки. Если формула введена корректно, то программа должна вывести на экран постфиксную форму записи (обратную польскую форму записи) и результат вычисления. Необходимо включить в работу программы тригонометрические функции, логарифмы, экспоненциальную функцию, модуль и корень числа, а также такие константы как число π=3,14159 и число е=2,71828. Используемые структуры данных.В своей программе я реализовала 3 класса: «class Calculator», «class Queue» и «class Stack». В классе «Calculator» располагается структура «Element», 5 методов для взаимодействия со списком элементов (вставка в конец, удаление с конца, получение размера списка, получение элемента по индексу и вывод списка на экран), а также различные методы, необходимые для решения поставленной задачи. Структура «Element» реализована для хранения данных элементов выражения и удобного передвижения по списку. Структуры Queue и Stack были выбраны из соображений простоты реализации и не высокой временной сложности. Алгоритм решения.Пользователь вводит с клавиатуры формулу, которая записывается программой как символьная строка. Далее программа обрабатывает эту строку на наличие неизвестных символов и корректность ввода, после чего заполняет список элементов выражения. Элементы в список записываются в виде строк. Заполненный список отправляется снова на проверку корректности ввода и если ошибок не возникло, то значит данное выражение можно преобразовать в постфиксную форму. Элементы списка обрабатываются по-отдельности слева направо и каждому присваивается свой приоритет. Приоритет операций в программе:
Далее следуем алгоритму: Если просматриваемый символ является левой скобкой, помещаем его в стек; Если просматриваемый символ – операнд, добавляем его в список с постфиксной записью; Если просматриваемый символ является правой скобкой, извлекаем из стека все символы до появления левой скобки и добавляем их в список с постфиксной записью; Если просматриваемый символ является оператором, удаляем все операторы из стека (пока не увидим оператор с меньшим приоритетом) и помещаем их в список с постфиксной записью, если и только если приоритет оператора, который находится наверху стека, больше или равен приоритету просматриваемого оператора. Затем помещаем просматриваемый оператор в стек. Иначе помещаем просматриваемый оператор в стек сразу. Таким образом у нас есть список с постфиксной записью элементов выражения. Этот список элементов программа выводит на экран пользователю. Далее вычисляем значение выражения в постфиксной форме по следующему алгоритму: Если просматриваемый символ является операндом, то помещаем его в стек; Если просматриваемый символ является оператором, то применяем его к операндам, которые извлекаем из стека. Результат снова помещаем в стек. После того, как программа посчитает все выражение, в стеке останется единственное значение. Это значение и будет являться результатом работы программы. Достаем его из стека и выводим пользователю на экран. Реализованные методы.Для решения поставленной задачи я реализовала 4 основных функции: Функция processing_string – обрабатывает строку, проверяет на корректность ввода и создает список из допустимых для программы элементов; Функция check_for_error – еще раз проверяет список на корректность ввода и в случае ошибки выводит соответствующее сообщение пользователю на экран; Функция infix_to_postfix – переводит обработанную строку в постфиксную форму, согласно алгоритму, описанному выше; Функция count_postfix – вычисляет значение выражения в постфиксной форме и возвращает результат вычислений; И 11 дополнительных функций для корректной работы программы: Функции is_digit_char и is_digit_string – проверяют является ли символ или строка соответственно числом; Функции is_character_char и is_character_string – проверяют является ли символ или строка соответственно словом или буквой; Функции is_operation_char и is_operation_string – проверяют является ли символ или строка соответственно оператором; Функция prior – определяет приоритет оператора; Функция functions – определяет является ли слово функцией; Функции CountFuncions и CountOperations – рассчитывают значения; Функция 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 |