### Fraction form

To gain practice working with symbolic expression trees, we will implement a function that transforms an expression into $\_$fraction form.$\_$ We say that an expression $e$ is in $\_$fraction form$\_$ if one of these two conditions is true:

$*$ either $e$ does not contain the division operator $$/$$$,$

$*$ or $e $=$ e$\_1/$ e$\_2$$$,$ for $e$\_1$$ and $e$\_2$$ not containing $$/$$$.$

Thus, intuitively, an expression $e$ in fraction form either does not contain division, or is in the form of a fraction, with a numerator and a denominator, neither of which contains the division operator.

In order to put an expression in fraction form, we start bottom up$,$ obtaining fraction representations for the expression nodes proceeding from the leaves, and going up to the top, in fashion not dissimilar to what we did in the compute function. At a node $$(\backslash$odot$,$ e$\_1,$ e$\_2)$$$,$ given fraction representations for $e$\_1$$ and $e$\_2$$$,$ we obtain a fraction representation for the node via:

$$

$\backslash$frac$\{$n$\_1\}\{$d$\_1\}\backslash$pm $\backslash$frac$\{$n$\_2\}\{$d$\_2\}\backslash$Rightarrow $\backslash$frac$\{$n$\_1$ d$\_2\backslash$pm n$\_2$ d$\_1\}\{$d$\_1$ d$\_2\},\backslash$quad

$\backslash$frac$\{$n$\_1\}\{$d$\_1\}\backslash$cdot $\backslash$frac$\{$n$\_2\}\{$d$\_2\}\backslash$Rightarrow $\backslash$frac$\{$n$\_1$ n$\_2\}\{$d$\_1$ d$\_2\},\backslash$quad

$\backslash$frac$\{$n$\_1\}\{$d$\_1\}\backslash$Bigm$/\backslash$frac$\{$n$\_2\}\{$d$\_2\}\backslash$Rightarrow $\backslash$frac$\{$n$\_1$ d$\_2\}\{$d$\_1$ n$\_2\}.$

$$

The implementation proceeds as follows. Given a node $$(\backslash$odot$,$ e$\_1,$ e$\_2)$$$,$ we first put $e$\_1$$$,$ $e$2$$ in fraction form, obtaining $e$\text{'}\_1,$ e$\text{'}\_2$$$.$ We then determine whether one of $e$\text{'}\_1$$ or $e$\text{'}\_2$$ is a fraction, that is$,$ has the $$/$$ operator as the root operator. If this is the case, we combine the fractions $e$\text{'}\_1$$ and $e$\text{'}\_2$$ using the rules above. If none of them is a fraction, we simply leave the node unchanged. We leave the code for you to write.

#@title Putting expressions in fraction form.

def to$\_$fraction$($e$)$:

$"""$Returns the expression e converted to fraction form."""

## YOUR SOLUTION HERE

Needs to pass the following tests:

e $=(\text{'}+\text{'},(\text{'}/\text{'},\text{'}$a$\text{'},\text{'}$b$\text{'}),(\text{'}/\text{'},\text{'}$c$\text{'},2))$

print$($to$\_$fraction$($e$))$

e $=(\text{'}/\text{'},\text{'}$a$\text{'},(\text{'}/\text{'},\text{'}$b$\text{'},(\text{'}/\text{'},\text{'}$c$\text{'},\text{'}$d$\text{'})))$

print$($to$\_$fraction$($e$))$

# Tests $5$ points: Simple tests for fraction form.

e $=(\text{'}/\text{'},(\text{'}/\text{'},\text{'}$a$\text{'},3),(\text{'}/\text{'},4,\text{'}$c$\text{'}))$

assert to$\_$fraction$($e$)==(\text{'}/\text{'},(\text{'}*\text{'},\text{'}$a$\text{'},\text{'}$c$\text{'}),(\text{'}*\text{'},3,4))$

e $=(\text{'}*\text{'},(\text{'}/\text{'},\text{'}$a$\text{'},3),(\text{'}/\text{'},4,\text{'}$c$\text{'}))$

assert to$\_$fraction$($e$)==(\text{'}/\text{'},(\text{'}*\text{'},\text{'}$a$\text{'},4),(\text{'}*\text{'},3,\text{'}$c$\text{'}))$

e $=(\text{'}-\text{'},(\text{'}/\text{'},\text{'}$a$\text{'},3),(\text{'}/\text{'},4,\text{'}$c$\text{'}))$

assert to$\_$fraction$($e$)==(\text{'}/\text{'},(\text{'}-\text{'},(\text{'}*\text{'},\text{'}$a$\text{'},\text{'}$c$\text{'}),(\text{'}*\text{'},4,3)),(\text{'}*\text{'},3,\text{'}$c$\text{'}))$

# Tests $5$ points: More complicated tests for fraction form.

e $=(\text{'}/\text{'},(\text{'}/\text{'},\text{'}$a$\text{'},(\text{'}/\text{'},\text{'}$b$\text{'},\text{'}$v$\text{'})),(\text{'}*\text{'},(\text{'}+\text{'},\text{'}$f$\text{'},\text{'}$g$\text{'}),\text{'}$c$\text{'}))$

assert to$\_$fraction$($e$)==(\text{'}/\text{'},$

$(\text{'}*\text{'},(\text{'}*\text{'},\text{'}$a$\text{'},\text{'}$v$\text{'}),1),$

$(\text{'}*\text{'},(\text{'}*\text{'},1,\text{'}$b$\text{'}),(\text{'}*\text{'},(\text{'}+\text{'},\text{'}$f$\text{'},\text{'}$g$\text{'}),\text{'}$c$\text{'})))$

e $=(\text{'}-\text{'},(\text{'}+\text{'},\text{'}$a$\text{'},(\text{'}/\text{'},\text{'}$b$\text{'},\text{'}$v$\text{'})),(\text{'}*\text{'},(\text{'}+\text{'},\text{'}$f$\text{'},\text{'}$g$\text{'}),\text{'}$c$\text{'}))$

assert to$\_$fraction$($e$)==(\text{'}/\text{'},$

$(\text{'}-\text{'},$

$(\text{'}*\text{'},(\text{'}+\text{'},(\text{'}*\text{'},\text{'}$a$\text{'},\text{'}$v$\text{'}),(\text{'}*\text{'},\text{'}$b$\text{'},1)),1),$

$(\text{'}*\text{'},(\text{'}*\text{'},(\text{'}+\text{'},\text{'}$f$\text{'},\text{'}$g$\text{'}),\text{'}$c$\text{'}),(\text{'}*\text{'},1,\text{'}$v$\text{'}))),$

$(\text{'}*\text{'},(\text{'}*\text{'},1,\text{'}$v$\text{'}),1))$

# Finally, here are some randomized tests.

# This generates random expressions.

op$\_$names $=\text{'}+-*/\text{'}$

var$\_$names $=$ 'abcdefghilmnopqrstuvz'

def random$\_$expression$($bias$=0)$:

$"""$Returns a random expression."""

p $=(1-$ math.exp$(-$bias $/7))$

if random.random$()<$ p $/3$:

# Number.

return random.random$()*10$

elif random.random$()<$ p:

# Symbol.

return $"".$join$([$random$.$choice$($var$\_$names$)$ for $\_$ in range$(16)])$

else:

op $=$ random.choice$($op$\_$names$)$

return $($op$,$ random$\_$expression$($bias$=$bias$+1),$ random$\_$expression$($bias$=$bias$+1))$

def is$\_$in$\_$fraction$\_$form$($e$)$:

$"""$Returns True if e is in fraction form, and False otherwise."""

## YOUR SOLUTION HERE

Needs to pass the following test:

# Tests $10$ points: These are the random tests.

class NotEqual$($Exception$)$:

pass

for $\_$ in range$(100)$:

e $=$ random$\_$expression$()$

ee $=$ to$\_$fraction$($e$)$

assert is$\_$in$\_$fraction$\_$form$($ee$),("$not in form:", ee$)$

try:

assert value$\_$equality$($e$,$ ee$,$ num$\_$samples$=100,$ tolerance$=0\mathrm{.}1),("$e:$",$ e$,"$ee:$",$ ee$)$

except:

raise NotEqual$("$e: $\{\},$ ee: $\{\}".$format$($e$,$ ee$))$

Please fill in everywhere it says $\text{'}$##YOUR SOLUTION HERE'$\text{'}$