Курсовая работа: Синтаксический анализатор полиномов

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

Преобразование полинома к приведенному виду

Одной из основных операций, которую должна реализовывать разрабатываемая программа, является преобразование полинома к приведенному виду. Полином называется приведённым, если в каждом его одночлене каждая из его переменных встречается не более одного раза, и нет подобных одночленов [5].

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

1. Разбор исходного полинома на слагаемые – одночлены;

2. Разбор каждого одночлена на коэффициент и множители (переменные в заданной степени).

3. Приведение подобных множителей в пределах каждого одночлена. Для этого выполняем следующие операции для каждого одночлена:

a) Разбор одночлена на переменные в заданной степени и занесение их в список.

b) Сортировка переменных в заданной степени в алфавитном порядке.

c) Разбор каждой переменной в заданной степени на переменную и соответствующий ей показатель степени и занесение их в список.

d) Анализ и обработка списка переменных (функция Without SimilarPowers ): если встречаются одинаковые переменные, суммируем их показатели степени и полученной суммой заменяем в списке показатель степени одной из одинаковых переменных, другую переменную и соответствующий ей показатель степени удаляем из списков. При этом функция Without SimilarPowers возвращает значение False. В случае если подобных множителей в одночлене нет, функция Without SimilarPowers возвращает значение True.

e) Сборка переменных в заданной степени в их произведение – приведенный одночлен без коэффициента: переменные в нем теперь упорядочены по алфавиту и встречаются только один раз.

4. Приведение подобных одночленов в пределах всего полинома. Для этого выполняем следующие операции:

a) Анализ и обработка списка приведенных одночленов без коэффициентов (функция WithoutSimilarCoeffs ): если встречаются одинаковые одночлены, суммируем их коэффициенты и полученной суммой заменяем в списке коэффициент одного из одинаковых одночленов, другой одночлен и соответствующий ему коэффициент удаляем из списков. При этом функция WithoutSimilarCoeffs возвращает значение False. В случае если подобных одночленов в полиноме нет, функция WithoutSimilarCoeffs возвращает значение True.

b) Собираем одночлены без коэффициентов и соответствующие им коэффициенты в полноценные одночлены

5. Сборка одночленов в приведенный полином. В случае если подобных множителей в одночлене и одночленов в полиноме не было, функция ToReducedPol возвращает True, в противном случае – False).

Определение однородности полинома

Полином называется однородным, если суммы степеней одночленов равны между собой [5]. Проверка полинома на однородность осуществлялась после преобразования его к приведенному виду.

Для работы с показателями степеней переменных, входящих в состав одночленов приведенного полинома, использовался динамический массив Powers ,где первый индекс массива указывает номер одночлена, а второй – номер переменной в одночлене (переменные входят в одночлены приведенного полинома в алфавитном порядке).

Рис.1 Последовательность операций по разбору и преобразованию полинома к приведенному виду

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

Вычисление значения полинома

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

Информация о коэффициентах одночленов приведенного полинома хранится в списке коэффициентов CoeffList , а информация о показателях степеней переменных в каждом одночлене в двумерном массиве Powers , где первый индекс массива указывает номер одночлена, а второй – номер переменной в одночлене (переменные входят в одночлены приведенного полинома в алфавитном порядке). В случае если переменная из списка всех переменных полинома VarList не входит в данный одночлен, ее степень по умолчанию равна нулю.

Вычисление значения полинома осуществляется в двойном цикле путем перебора во внешнем цикле всех одночленов полинома, а во внутреннем – всех переменных в одночлене.

Нахождение полинома-производной исходного полинома по заданной переменной

Полином-производная исходного полинома по заданной переменной формируется путем преобразования копий массива показателей степеней исходного полинома Power _ d и списка коэффициентов его одночленов CoeffList_d по правилам дифференцирования степенных функций.

По преобразованному массиву степеней и списку коэффициентов строится искомый полином-производная.