## 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.

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