 # Introduction to Computer Science: Week 10

## Overview

Our goal this week will be to bring closure to the Polyonial project. We have three class periods to do it, so with focus and dedication, we should be able to add and multiply polynomials by week's end.

## Wednesday, March 11th

I'm out sick today. Continue to work on your assignment and we be ready to present your progress on Friday in class.

## Monday, March 9th

### Classwork

We will begin with presentations of solutions to the function assigned last Thursday to extract terms from a string representing a polynomial.

### Homework

You will be provided with `__init__` and `__str__` methods for a `Polynomial` class that enable you to read and write polynomials.

Consider the following four ways to store polynomial data for the polynomial represented by the string `3x^4 - 7x^2 + 11`:

1. `[(3, 4), (-7, 2), (11, 0)]`
2. `(3, 0, -7, 0, 11)`
3. `(11, 0, -7, 0, 3)`
4. `{4: 3, 2: -7, 0: 11}`

Work with your partner to prepare a presentation for class on Wednesday addressing the following questions:

1. Which representation would make it easier to add polynomials?
2. Which representation would make it easier to multiply polynomials?
3. How hard would it be to convert from one representation to the other?

### Resources

• Version 1: Leila and Rowan:
```import re

def extract_polynomial_values(s):
"""
Create a list of 2-tuples of coefficents and exponents of a polynomial

>>> extract_polynomial_values('3x^4+7x^2')
[(3, 4), (7, 2)]
>>> extract_polynomial_values('x^9-3x^4-x+42')
[(1, 9), (-3, 4), (-1, 1), (42, 0)]
"""

pattern = r"\s*([+-]?)(\d+)?\s*(x(\^(\d+))?)?"

# sign, coefficent, x-term, ^exponent, exponent

matches = re.findall(pattern, s)
result = []
for e in matches:
coeff = 0
expt = 0
if e != '': # e is the coefficient
coeff = int(e)
if e == '': # theres no coefficient, so implicitly its 1
coeff = 1
if e == 'x': # theres just an x term, so exponent is 1
expt = 1
if (e != ''): # there IS an exponent, so grab it
expt = int(e)
if e == '-': # theres a minus sign, so negate the coefficent
coeff = -coeff
if coeff != 0 or expt != 0: # if there, add it to the result
#print (s, e, coeff, expt)
result.append((coeff, expt))
result.pop()  # discard the empty match at the end
return result

extract_polynomial_values('-3x^5+x-2')
extract_polynomial_values('-3x^5 + x - 2')
```
• Version 2:
```import re

def get_terms(polystr):
"""
>>> get_terms('3x^5-7x^2+11')
[(3.0, 5), (-7.0, 2), (11.0, 0)]
>>> get_terms('x^3-x^2+x')
[(1.0, 3), (-1.0, 2), (1.0, 1)]
"""
regex = re.compile(r"([+-]*)(\d+)?(x(\^(\d+))?)?")
raw_terms = regex.findall(polystr)[:-1]
terms = []

# extract terms from capture groups
for raw_term in raw_terms:
# handle exponent of constant term
if not raw_term[-1] and not raw_term:
exp = 0
# handle exponent of linear term
elif not raw_term[-1]:
exp = 1
else:
exp = int(raw_term[-1])

# handle coefficient of 1
if not raw_term:
coeff = 1.0
else:
coeff = float(raw_term)
# handle negative coefficients
if raw_term == '-':
coeff *= -1

terms.append((coeff, exp))

return terms

class Polynomial:
"""
>>> p = Polynomial('3x^2-7x+9')
>>> print(p)
3.0x^2 - 7.0x + 9.0
"""
def __init__(self, poly_str):
self.terms = get_terms(poly_str)

def __str__(self):
poly_str = ''

for term in self.terms:
coeff, exp = term
coeff_str = ''
# handle negative coefficents
if coeff < 0:
coeff_str += ' - '
coeff *= -1
else:
coeff_str += ' + '
# handle coefficents of 1
if coeff != 1:
coeff_str += str(coeff)

exp_str = ''
# ignore exp_str for constant term, handle linear term
if exp > 1:
exp_str += f'x^{exp}'
elif exp == 1:
exp_str += 'x'

poly_str += coeff_str + exp_str

return poly_str[3:] if poly_str == '+' else '-' + poly_str[3:]

if __name__ == '__main__':
import doctest
doctest.testmod()
```

### Evaluation

You will be evaluated based on your solution to this problem and the presentation of it you provide in class on Wednesday.