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

[pic 1][pic 2]

[pic 3]

Кафедра САПР

КУРСОВАЯ РАБОТА

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

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

Вариант № 1

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

2020 г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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