Write a function called evaluate, which takes a well$-$formed binary tree $($constructed using your build$\_$tree $(10)$

function$)$ and returns the numeric result of evaluating the arithmetic expression represented by the tree.

Examples:

let t $=$ build$\_$tree $(1+(2*3))$;;

let v $=$ evaluate t;; $(*$ v should be the int value $7*)$

Test Cases:

$(1)$ Integer Arithmetic Expression:

$$ Pass an integer arithmetic expression $($e$.$g$.,1+(2*3))$ to build$\_$tree to construct the tree.

Then pass the tree to evaluate, which should return the final integer result $($e$.$g$.,7).$

$(2)$ Float Arithmetic Expression:

$$ Pass a float arithmetic expression $($e$.$g$.,(1\mathrm{.}5+.2\mathrm{.}0)*.3\mathrm{.}0)$ to build$\_$tree.

$$ Pass the tree to evaluate, which should return the final float result $($e$.$g$.,10\mathrm{.}5).$

Preconditions:

$$ The input tree is well$-$formed, created using the build$\_$tree function.

$$ The operators in the tree are valid for the corresponding numeric types $($e$.$g$.,+$ for integers, $+.$ for

floats$).$

Postconditions:

$$ If the tree represents a valid arithmetic expression, the function returns the computed numeric

value.

$$ The result will be an integer or float, depending on the type of the arithmetic expression.

reduce these expressions up to a certain point.

The expressions will only involve addition and multiplication. But now, we distinguish between constants

and variables. The goal is to write a function that reduces expressions using basic rules like $0+$ x $=$ x$,$

x $*1=$ x$,$ etc. If variables are involved, reductions will eventually lead to a $$stuck$$ state. If there are

no variables, then the reductions will go all the way to a single numeric value.

Example:

type expr $=$

$|$ Const of int

$|$ Var of string

$|$ Add of expr $*$ expr

$|$ Mul of expr $*$ expr;;

Your task is to write a function called reduce, which takes a single expr and reduces it as much as

possible by recursive application of reduction rules to the input expression. Test with cases like:

reduce $($Add $($Const $0,$ Var $"$x$"))$;; $(*$ should return Var $"$x$"*)$

reduce $($Mul $($Const $1,$ Var $"$y$"))$;; $(*$ should return Var $"$y$"*)$

reduce $($Mul $($Const $1,($Add $($Const $2,$ Const $4)))$;; $(*$ should return Const $6*)$

For the actual integer addition and multiplication within your reduction process, you should simply use

OCaml$$s internal $+$ and $*$ operators, respectively.