Write a function that evaluates an arithmetic expression with the following requirements:

$-$ Input is the tuple of parsed tokens provided as the output of parse$\_$expression function, ie$.$ a list of characters $($for operators$)$ and float values.

$*$ Output is the result of the evaluation of the expression i$.$e$.$ a floating point number

$-$ Function should raise erception when an invalid expression is given

$-$ Use double stack implementation based expression evaluation algorithm that was provided in the lecture slides.

$-$ Use FloatArrayStack $($with capacity of $20)$ for numbers $($operands$)$

$-$ Use ListStack for operators

$-$ You will improve the algorithm given in the textbook so that it supports parentheses as well

$*$ Allowed operators are defined in function parse$\_$expression, their precedences shall be computed using pred function provided below, ie$.$ precedences are:

$-1$ for $\text{'}$T and $\backslash (\backslash$gamma $\backslash )$

$-2$ for $\text{'}+\text{'}$ and $\text{'}-\text{'}$

$-3$ for $"\backslash (\{\}^\{*\}\backslash )$ and $\text{'}//$

$-$ Here is how you improve the algorithm when parentheses are provided in the input:

$-$ If the operator is $\text{'}$C$,$ push it to the operator stack

$-$ If the operator is $\text{'}$I$\text{'}.$ perform doOp$0$ opreation until $\text{'}$T$\text{'}$ is popped from the stack

$-$ Note that $\backslash (\backslash$gamma $\backslash )$ has lower precedence than alf other arithmetic operators and $\backslash (\backslash$gamma $\backslash )\text{'}$ is never pushed to the stack

$-$ You may define multiple functions or global variables

$-$ There is a buili$-$in python function called evalo. which evaluates an expression it is forbidden to use that function in your solution, however you can use it to test your code.

$*$ You will get partial points anyway even if you don't implement parentheses, it is recommended that you first implement the algorithm given in the slides, then improve it by adding parenthesis support.

$```$

OPERATORS $="()+-*/"$

def prec$($op$)$:

return $1+$ OPERATORS.index$($op$)//2$

def eval$\_$tokens$($tokens$)$:

floats $=$ FloatArrayStack$(20)$

ops $=$ ListStack$()$

# $============$ YOUR CODE HERE $============$

raise NotImplementedError$()$

$```$

$```$

def eval$\_$expression$($expression$)$:

tokens $=$ parse$\_$expression$($expression$)$

return eval$\_$tokens$($tokens$)$

$```$

$\backslash$#You can use the following code to test you code

assert $\backslash (3\mathrm{.}0==\backslash )$ eval$\_$tokens$((3\mathrm{.}0,))$

assert $\backslash (8\mathrm{.}0==\backslash )$ eval$\_$tokens$((3\mathrm{.}0,\text{'}+\text{'},5\mathrm{.}0))$

assert $\backslash (13\mathrm{.}0==\backslash )$ eval$\_$tokens$((3\mathrm{.}0,\text{'}+\text{'},5\mathrm{.}0,\text{'}*\text{'},2\mathrm{.}0))$

assert $\backslash (16\mathrm{.}0=\backslash )$ eval$\_$tokens$((\text{'}(\text{'},3\mathrm{.}0,\text{'}+\text{'},5\mathrm{.}0,\text{'})\text{'},\text{'}*\text{'},2\mathrm{.}0))$

$\backslash$#You can also use the given parse$\_$expression function

assert $\backslash (0\mathrm{.}1342281879194631=\backslash )$ eval$\_$expression$("\backslash (6^\{*\}(2\mathrm{.}0+3)/.(23\mathrm{.}5+(\mathrm{.}2\backslash$mathrm$\{$E$\}3+0\mathrm{.}1\backslash$mathrm$\{$e$\}+3-10000\backslash$mathrm$\{$E$\}-2))\backslash )")$