ub fn parse$($ts: Vec$<$&str$>)->$ std::rc::Rc $\{$

$//$TODO: Complete this function

$/*$

The lex function is responsible for breaking down the input expression into tokens. This is the first step of parsing where you identify the individual components of the expression

The parse function is where you convert the tokenized input into an abstract syntax tree $($AST$).$ Think about how you can recursively build the tree by combining expressions based on the tokens

$*/$

let mut toks $=$ ts;

pub fn parse$\_$exp$($toks: &mut Vec$<$&str$>)->$ std::rc::Rc $\{$

$/*$

This function should recursively parse an expression based on the tokens

Consider how each type of expression $($PlusExp$,$ MinusExp, etc.$)$ should be parsed differently

$*/$

$//$ Consider the following example to parse $(+12)$

let num $=$ Regex::new$($r$"^\backslash$d$+$$$").$unwrap$()$; $//$ Digits

let ops $=$ Regex::new$($r$"^(\backslash +|-|\backslash *|\backslash ^)$$$").$unwrap$()$; $//$ Operators

let nexttok $=$ toks$[0]$;

match nexttok $\{$

$"+"=>\{$

expect$($toks$,$ nexttok$)$; $//$ This should remove the $"+"$ from the front of toks

let arg$1=$ parse$\_$exp$($toks$)$; $//$ We recursively parse the first arg of $"+"$

let arg$2=$ parse$\_$exp$($toks$)$; $//$ and the same recursive parse of the second arg of $"+"$

match nexttok $\{$

$"+"=>\{$

return std::rc::Rc::new$($PlusExp $\{$

lhs: arg$1,$

rhs: arg$2,$

$\})$

$\},$

$\}$

$\},$

$"("=>\{$

expect$($toks$,$ nexttok$)$;

let op $=$ toks$[0]$;

if ops.is$\_$match$($op$)\{//$ The item right after a paren should be an operator

expect$($toks$,$ op$)$;

$\}$ else $\{$

return std::rc::Rc::new$($ErrorExp$)$; $//$ Return an error if not

$\}$

let mut next $=$ peek$($toks$,0)$; $//$ This will not remove the item at the front of toks

let mut args: Vec$>=$ vec!$[]$; $//$ A vector to hold args within the parens

while next $!=")"\{$

$//$ Add the args until we see a right hand paren

let next$\_$arg $=$ parse$\_$exp$($toks$)$;

args.push$($next$\_$arg$)$;

next $=$ peek$($toks$,0)$;

$\}$

expect$($toks$,")")$;

if args.len$()==0\{$

return std::rc::Rc::new$($ErrorExp$)$;

$\}$

match op$\{$

$"+"=>\{$

if args.len$()==1\{$

$//$ Addition allows for unary addition, thus we can use $0$ for the left hand side.

$//(+1)->(+10)$

return std::rc::Rc::new$($PlusExp $\{$

lhs: std::rc::Rc::new$($LitExp$\{$n: $0\}),$

rhs: std::rc::Rc::clone$($&args$[0]),$

$\})$;

$\}$

$//$ For binary or more arguments, we use the arg $0$ as our left hand side number and arg $1$ as our right hand arg.

$//(+12)->$ args$[0]=1$ and args$[1]=2$

let mut ast $=$ std::rc::Rc::new$($PlusExp $\{$

lhs: std::rc::Rc::clone$($&args$[0]),$

rhs: std::rc::Rc::clone$($&args$[1]),$

$\})$;

for arg in &args$[2..$args.len$()]\{$

ast $=$ std::rc::Rc::new$($PlusExp $\{$

lhs: ast, $//$ Since we only allow for binary ASTs, we only allow for binary additions, thus our left hand side would be our previously calculated addition. In this case $(+(+12)3)$ would return the AST you parsed for $(+12)$

rhs: arg.to$\_$owned$(),$

$\})$;

$\}$

return ast;

$\}$

$\}$

$\}$

$\_=>\{$

$//$ TODO: complete this match case

$//$ Consider the possibility that you don't match on an op such as $"+"$ above and you don't see an open paren

$\}$

$\}$

std::rc::Rc::new$($ErrorExp$)$

$\}$

let ast $=$ parse$\_$exp$($&mut toks$)$;

if peek$($&toks, $0)==""\{$

return ast;

$\}$ else $\{$

return std::rc::Rc::new$($ErrorExp$)$;

$\}$

$\}$