1 R Doubly linked lists
class Node:
def __init__(self, value = None):
self.value = value self.next_node = None self.previous_node = None
2 Using linked lists to represent polynomials
Write a program that implements a class Polynomial. An object of this class is built from a string that represents a polynomial, that is, a sum or difference of monomials.
• The leading monomial can be either an integer, or an integer followed by x, or an integer followed by xˆ followed by a nonnegative integer.
• The other monomials can be either a nonnegative integer, or an integer followed by x, or an integer followed by xˆ followed by a nonnegative integer.
Spaces can be inserted anywhere in the string.
A monomial is defined by the following class:
class Monomial:
def __init__(self, coefficient = 0, degree = 0):
self.coefficient = coefficient self.degree = degree self.next_monomial = None
A polynomial is a linked list of monomials, ordered from those of higher degree to those of lower degree. An implementation of the __str__() method allows one to print out a polynomial.
Next is a possible interaction.
1
$ python ...
>>> from polynomial import *
>>> Polynomial(’-0’) Incorrect input
>>> Polynomial(’+0’)
Incorrect input
>>> Polynomial(’0x^-1’)
Incorrect input
>>> Polynomial(’2x + +2’) Incorrect input
>>> Polynomial(’2x + -2’) Incorrect input
>>> Polynomial(’2x - +2’)
Incorrect input
>>> poly_0 = Polynomial(’0’)
>>> print(poly_0)
0
>>> poly_0 = Polynomial(’0x’)
>>> print(poly_0)
0
>>> poly_0 = Polynomial(’0x^0’)
>>> print(poly_0)
0
>>> poly_0 = Polynomial(’0x^5’)
>>> print(poly_0)
0
>>> poly_1 = Polynomial(’x’)
>>> print(poly_1) x
>>> poly_1 = Polynomial(’1x’)
>>> print(poly_1) x
>>> poly_1 = Polynomial(’1x^1’)
>>> print(poly_1) x
>>> poly_2 = Polynomial(’2’)
>>> print(poly_2)
2
>>> poly_2 = Polynomial(’2x^0’)
>>> print(poly_2)
2
>>> poly_3 = Polynomial(’1 + 2-3 +10’)
>>> print(poly_3)
10
>>> poly_4 = Polynomial(’x + x - 2x -3x^1 + 3x’)
>>> print(poly_4)
0
>>> poly_5 = Polynomial(’x + 2 + x - x -3x^1 + 3x + 5x^0’)
>>> print(poly_5)
x + 7
>>> poly_6 = Polynomial(’-2x + 7x^3 +x - 0 + 2 -x^3 + x^23 - 12x^8 + 45 x ^ 6 -x^47’)
>>> print(poly_6)
-x^47 + x^23 - 12x^8 + 45x^6 + 6x^3 - x + 2
2
