Description
1 Using linked lists to represent polynomials
Extend the program that implements a class Polynomial from the previous lab to implement the
functions __add__(), __sub__(), __mul__() and __truediv__().
Next is a possible interaction.
$ python
…
>>> from polynomial import *
>>> 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
>>> poly_7 = Polynomial(’2x^5 – 71x^3 + 8x^2 – 93x^4 -6x + 192’)
>>> poly_8 = Polynomial(’192 -71x^3 + 8x^2 + 2x^5 -6x – 93x^4’)
>>> poly_9 = poly_7 + poly_8
>>> print(poly_7)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> print(poly_8)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> print(poly_9)
4x^5 – 186x^4 – 142x^3 + 16x^2 – 12x + 384
>>> print(poly_7 * poly_7)
4x^10 – 372x^9 + 8365x^8 + 13238x^7 + 3529x^6 + 748x^5 – 34796x^4 – 27360x^3 + 3108x^2 – 2304x + 36864
>>> print(poly_7)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> print(poly_7 – poly_7)
0
>>> print(poly_7)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> print(poly_9 / poly_7)
2
>>> print(poly_9)
4x^5 – 186x^4 – 142x^3 + 16x^2 – 12x + 384
>>> print(poly_7)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> poly_10 = Polynomial(’-11x^4 + 3x^2 + 7x + 9’)
>>> poly_11 = Polynomial(’5x^2 -8x – 6’)
>>> poly_12 = poly_10 * poly_11
>>> print(poly_12)
-55x^6 + 88x^5 + 81x^4 + 11x^3 – 29x^2 – 114x – 54
>>> print(poly_12 / poly_10)
5x^2 – 8x – 6
>>> print(poly_12 / poly_11)
-11x^4 + 3x^2 + 7x + 9
>>> poly_13 = poly_6 * poly_7
1
>>> print(poly_13 / poly_6)
2x^5 – 93x^4 – 71x^3 + 8x^2 – 6x + 192
>>> print(poly_13 / poly_7)
-x^47 + x^23 – 12x^8 + 45x^6 + 6x^3 – x + 2
2 R Using a stack to evaluate fully parenthesised expressions
Modify the program postfix.py from the 9th lecture so that a stack is used to evaluate an arithmetic expression written in infix, fully parenthesised, and built from natural numbers using the
binary +, -, * and / operators. Fully parenthesised means that all expressions of the form e + e’,
e – e’, e * e’ and e / e’ are surrounded by a pair of parentheses, brackets or braces. Of course a
simple solution would be to replace all brackets and braces by parentheses and call eval(), but
here we want to use a stack.
Hint: think of popping when and only when a closing parenthesis, bracket or brace is being processed.
Here is a possible interaction:
$ python
…
>>> from exercise_2 import *
>>> expression = FullyParenthesisedExpression(’2’)
>>> expression.evaluate()
2
>>> expression = FullyParenthesisedExpression(’(2 + 3)’)
>>> expression.evaluate()
5
>>> expression = FullyParenthesisedExpression(’[(2 + 3) / 10]’)
>>> expression.evaluate()
0.5
>>> expression = FullyParenthesisedExpression(’(12 + [{[13 + (4 + 5)] – 10} / (7 * 8)])’)
>>> expression.evaluate()
12.214285714285714
3 Introduction to context free grammars
A context free grammar is a set of production rules of the form
symbol_0 –-> symbol_1 … symbol_n
where symbol_0, . . . , symbol_n are either terminal or nonterminal symbols, with symbol_0 being
necessarily nonterminal. A symbol is a nonterminal symbol iff it is denoted by a word built from
underscores or uppercase letters. A special nonterminal symbol is called the start symbol. The
language generated by the grammar is the set of sequences of terminal symbols obtained by replacing
2
a nonterminal symbol by the sequence on the right hand side of a rule having that nonterminal
symbol on the left hand side, starting with the start symbol. For instance, the following, where
EXPRESSION is the start symbol, is a context free grammar for a set of arithmetic expressions.
EXPRESSION –> TERM SUM_OPERATOR EXPRESSION
EXPRESSION –> TERM
TERM –> FACTOR MULT_OPERATOR TERM
TERM –> FACTOR
FACTOR –> NUMBER
FACTOR –> (EXPRESSION)
NUMBER –> DIGIT NUMBER
NUMBER –> DIGIT
DIGIT –> 0
…
DIGIT –> 9
SUM_OPERATOR –> +
SUM_OPERATOR –> –
MULT_OPERATOR –> *
MULT_OPERATOR –> /
Moreover, blank characters (spaces or tabs) can be inserted anywhere except inside a number. For
instance, (2 + 3) * (10 – 2) – 12 * (1000 + 15) is an arithmetic expression generated by the
grammar.
Verify that the grammar is unambiguous, in the sense that every expression generated by the
grammar has a unique evaluation.
Write down a program that prompts for an expression, checks whether it can be generated by the
grammar, and in case the answer is yes, evaluates the expression, following this kind of interaction:
$ python exercise_3.py
Input expression: 2
The expression evaluates to: 2
$ python exercise_3.py
Input expression: 2 * 2
The expression evaluates to: 4
$ python exercise_3.py
Input expression: (2 + 3) * (10 – 2) – 12 * (1000 + 15)
The expression evaluates to: -12140
$ python exercise_3.py
Input expression: 2 + +3
Incorrect syntax
3
