type tree = Num of int | Minus of tree | Add of tree * tree | Mul of tree * tree | Sub of tree * tree | Div of tree * tree;; let rec optimize expr = match expr with Num x -> Num x |Minus (Minus x) -> (optimize x) |Minus x -> Minus (optimize x) |Add (x, y) -> Add (optimize x, optimize y) |Sub (x, y) -> Sub (optimize x, optimize y) |Mul (x, y) -> Mul (optimize x, optimize y) |Div (x, y) -> Div (optimize x, optimize y);; let int_of_ascii x = int_of_char x - 48;; let parse s = let len = String.length s in let parse_num i = let rec pn acc pos = if (pos < len) then match s.[pos] with '0'..'9' as x -> pn (10 * acc + (int_of_ascii x)) (pos + 1) |_ -> (Num acc, pos) else (Num acc, pos) in pn 0 i in let rec parse_expr i = let rec pp i acc = if (i < len) then match s.[i] with '+' -> let (t, i') = parse_term (i + 1) in pp i' (Add (acc, t)) |'-' -> let (t, i') = parse_term (i + 1) in pp i' (Sub (acc, t)) | _ -> (acc, i) else (acc, i) in let (tr, i'') = parse_term i in pp i'' tr and parse_term i = let rec pp i acc = if (i < len) then match s.[i] with '*' -> let (t, i') = parse_part (i + 1) in pp i' (Mul (acc, t)) |'/' -> let (t, i') = parse_part (i + 1) in pp i' (Div (acc, t)) | _ -> (acc, i) else (acc, i) in let (tr, i'') = parse_part i in pp i'' tr and parse_part i = match s.[i] with '0'..'9' -> parse_num i |'+' -> parse_part (i + 1) |'-' -> let (t, i') = parse_part (i + 1) in (Minus t, i') |'(' -> let (t, i') = parse_expr (i + 1) in if s.[i'] <> ')' then failwith ")" else (t, i' + 1) |_ -> failwith "?!!" in optimize (fst (parse_expr 0));; let rec count expr = match expr with Num x -> x |Minus x -> -(count x) |Add (a, b) -> (count a) + (count b) |Sub (a, b) -> (count a) - (count b) |Mul (a, b) -> (count a) * (count b) |Div (a, b) -> (count a) / (count b);; let rec string_of_tree t = match t with Num x -> string_of_int x |Minus x -> "-" ^ (string_of_tree x) |Add (a, b) -> "(" ^ (string_of_tree a) ^ "+" ^ (string_of_tree b) ^ ")" |Mul (a, b) -> "(" ^ (string_of_tree a) ^ "*" ^ (string_of_tree b) ^ ")" |Sub (a, b) -> "(" ^ (string_of_tree a) ^ "-" ^ (string_of_tree b) ^ ")" |Div (a, b) -> "(" ^ (string_of_tree a) ^ "/" ^ (string_of_tree b) ^ ")";; let ( >> ) x f = f x;; let print x = let res = parse x in Printf.printf "%s\t -> %s\t -> %d\n" x (string_of_tree res) (count res);; print "-128";; print "(+8192)";; print "25+81";; print "3-5-1";; print "5-(8-1)";; print "1+01*01";; print "-(5*+3)";; print "----1-2";; print "---2*8";; print "--(3*5)";; print "-+-+1+4";;