Description
1 R Doubly linked lists
Modify the module linked_list.py which is part of the material of the 8th lecture into a module
doubly_linked_list.py, to process lists consisting of nodes with a reference to both next and
previous nodes, so with the class Node defined as follows.
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.
$ 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
