(** Fonctions Utiles *)

type arbre =
  | Vide
  | Noeud of int * arbre * arbre ;;


let afficher_arbre t =
  let rec afficher depth t = match t with
    | Vide -> ()
    | Noeud (i, l, r) ->
        for i=0 to depth do print_string " " done;
        printf__printf "- %d\n" i;  (* affiche i *)
        afficher (depth+2) l;
        afficher (depth+2) r
  in
  afficher 2 t;;

let arbre_aleatoire () =
  let rec make depth =
    if depth > 4 || random__int 4 < depth then Vide
    else Noeud (random__int 100, make (depth+1), make (depth+1))
  in
  make 0;;

(* change la forme de l'arbre a aléatoirement, sans changer
  son ordre de parcours infixe *)
let rec rebalancer a = match a with
  | Vide -> Vide
  | Noeud (Noeud (x, l1, r1), x2, r2) when random__int 2 = 1 ->
      Noeud (x, rebalancer l1, Noeud (x2, rebalancer r1, rebalancer r2)
  | Noeud (x2, l2, Noeud (x, l1, r1) when random__int 2 = 1 ->
      Noeud (x, Noeud (x2, l2, l1), r1)
  | Noeud (x, l, r) -> Noeud (x, rebalancer l, rebalancer x)
;;

let stack_of_list l =
  let p = stack_create () in
  let rec iter l = match l with
    | [] -> p
    | x :: l' -> stack_push p x; iter l'
  in
  iter l
;;

type expr =
    | Const of int  (* constante *)
    | Plus of expr * expr (* x plus y *)
    | Fois of expr * expr (* x fois y *)
    | Moins of expr  (* -x *)
;;

type operation =
  | OpConst of int (* constante *)
  | OpPlus         (* addition *)
  | OpFois         (* multiplication *)
  | OpSoustraire   (* soustraction *)
;;

let expr_aleatoire () =
  let rec make depth =
    if depth > 4 then Const (random__int 41 - 20)
    else match random__int 4 with
    | 0 -> Const (random__int 41 - 20)
    | 1 -> Plus (make (depth+1), make (depth+1))
    | 2 -> Fois (make (depth+1), make (depth+1))
    | 3 -> Moins (make (depth+1))
    | _ -> failwith "impossible"
  in
  make 0;;

let rec afficher_expr e =
  match e with
  | Const i -> string_of_int i
  | Plus(a,b) -> "(" ^ afficher_expr a ^ " + " ^ afficher_expr b ^ ")"
  | Fois(a,b) -> "(" ^ afficher_expr a ^ " * " ^ afficher_expr b ^ ")"
  | Moins a -> "- " ^ afficher_expr a
;;

(** Debut du TP ici *)