Implementation

Data Structures and Algorithms with Object-Oriented Design Patterns in Python

Implementation

To begin with, we need to represent the terms of the polynomial. Program extends the definition of the Term class introduced in Program --some additions are needed to support the the implementation of polynomial addition.

program10311
Program: Term methods.

A number of additional operations are declared in Program . The first method, __copy__, creates a copy of a given term.

Two properties, coefficient and exponent, use the methods getCoefficient and getExponent (respectively) to return the corresponding instance attributes of a Term instance. Clearly, the running time of each of these operations is O(1).

The final method, __add__, provides the means to add two Terms together. The result of the addition is another Term. The working assumption is that the terms to be added have identical exponents. If the exponents are allowed to differ, the result of of the addition is a polynomial which cannot be represented using a single term! To add terms with like exponents, we simply need to add their respective coefficients. Therefore, the running time of the Term addition operator is O(1).

We now turn to the polynomial itself. Program introduces the PolynomialAsSortedList class. This class extends the abstract Polynomial class defined in Program . It has a single instance attribute of type SortedListAsLinkedList. We have chosen in this implementation to use the linked-list sorted list implementation to represent the sequence of terms.

program10351
Program: PolynomialAsSortedList class __init__ and __add__ methods.

Program defines the __add__ method. This method adds two Polynomials to obtain a third. It is intended to be used like this:

p1 = PolynomialAsSortedList()
p2 = PolynomialAsSortedList()
# ...
p3 = p1 + p2