(** Un type pour les s-expressions *)
type s_exp =
    Nil
  | N of int
  | Op of char
  | Cons of s_exp * s_exp ;;

(* Expressions valides. *)
let e0 = N 0 ;;
let e1 = Cons (Op '+', Cons (N 2, Cons (N 3, Nil))) ;;
let e2 = Cons (Op '*', Cons (N 2, Cons (N 3, Nil))) ;;

(* S-expressions valides n'étant pas des expressions valides. *)
let s3 = Nil ;;
let s4 = Op '#' ;;
let s5 = Cons (Nil, Nil) ;;
let s6 = Cons (N 5, Nil) ;;
let s7 = Cons (s4, Nil) ;;
let s8 = Cons (Op '+', N 4) ;;
let s9 = Cons (Op '+' , Cons (N 2, N 3)) ;;

(** (string_of_s_exp se) retourne la représentation totalement parenthésée de
  la s-expression se. *)
let rec string_of_s_exp = function
    Nil -> "()"
  | N n -> string_of_int n
  | Op c -> Char.escaped c
  | Cons (e1, e2) ->
      "(" ^ string_of_s_exp e1 ^ "." ^ string_of_s_exp e2 ^ ")" ;;

string_of_s_exp e0 ;;
string_of_s_exp e1 ;;
string_of_s_exp e2 ;;
string_of_s_exp s3 ;;
string_of_s_exp s4 ;;
string_of_s_exp s5 ;;
string_of_s_exp s6 ;;
string_of_s_exp s7 ;;
string_of_s_exp s8 ;;
string_of_s_exp s9 ;;

(** (toString se) retourne la représentation de la S-expression se avec un
  parenthésage minimum à la scheme. *)
let rec toString = function
    Nil -> "()"
  | N n -> string_of_int n
  | Op c -> Char.escaped c
  | Cons (e1, e2) -> "(" ^ toString e1 ^ tscdr e2
and
  (* (tscdr sp) retourne la représentation du cdr sp d'une suite de paires de
     S-expressions, sans ajout de parenthèse ouvrante. *)
  tscdr = function
      Nil -> ")"
    | Cons (d1, d2) -> " " ^ toString d1 ^ tscdr d2
    | d -> " . " ^ toString d ^ ")"
;;

toString e0 ;;
toString e1 ;;
toString e2 ;;
toString s3 ;;
toString s4 ;;
toString s5 ;;
toString s6 ;;
toString s7 ;;
toString s8 ;;
toString s9 ;;

(** (eval e) retourne la valeur de l'expression représentée par la
  S-expression e ;
  lève l'exception (Failure "eval : ...") si la S-expression e
  n'est pas une expression valide. *)
let rec eval = function
    N n -> n
  | Cons (Op '+', Cons (e1, Cons (e2, Nil))) -> eval e1 + eval e2
  | Cons (Op '*', Cons (e1, Cons (e2, Nil))) -> eval e1 * eval e2
  | e -> failwith ("eval : " ^ toString e) ;;

eval e0 ;;
eval e1 ;;
eval e2 ;;
eval s3 ;;
eval s4 ;;
eval s5 ;;
eval s6 ;;
eval s7 ;;
eval s8 ;;
eval s9 ;;