Description
1 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
