(*
write a fubction that checks that parenthisis are balnaced:
Parenthisis are balenced if there are no parenthises
Parenthisis are balenced if ( and ) enclose a balenced parenthises
Parenthisis are balenced if balenced parenthises are ajacent to a balenced parenthisis
For example,
matching_parens “” = true
matching_parens “((((((((((()))))))))))” = true
matching_parens “()()()()()()” = true
matching_parens “(()())” = true
matching_parens “())(()” = false
*)
(* Hint
write mutually recirsive functions
matching_paren_prefix : (char list) -> ((char list) option)
matching_parens_prefix : (char list) -> ((char list) option)
the and keyword allows mutual recursion
let rec matching_paren_prefix (ls: char list) : ((char list) option) = failwith “unimplemented”
and matching_parens_prefix (ls: char list) : ((char list) option) = failwith “unimplemented”
such that
matching_paren_prefix [] = None
matching_paren_prefix (explode “(???”) = None
matching_paren_prefix (explode “()???”) = Some [‘?’; ‘?’; ‘?’]
matching_paren_prefix (explode “(((())))123”) = Some [‘1’; ‘2’; ‘3’]
matching_paren_prefix (explode “()()()”) = Some [‘(‘; ‘)’; ‘(‘; ‘)’]
matching_paren_prefix (explode “(()()())abc”) = Some [‘a’; ‘b’; ‘c’]
matching_parens_prefix [] = Some []
matching_parens_prefix (explode “()()()”) = Some []
matching_parens_prefix (explode “()())))”) = Some [‘)’; ‘)’; ‘)’]
matching_parens_prefix (explode “)aa”) = Some [‘)’; ‘a’; ‘a’]
*)
let rec matching_parens (tree: string) : bool = failwith “unimplemented”