(* ==================================================================
   Calculatrice interactive : parseur + évaluateur
   ================================================================== *)

(* --- AST (arbre de syntaxe abstraite) --- *)
type expr =
  | Num of int
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr

(* --- Mini-librairie de parseurs (repris de parsec.ml) --- *)
type 'a parser = char list -> ('a * char list) list

let return x = fun input -> [x, input]
let fail = fun _ -> []

let (>>=) (p : 'a parser) (f : 'a -> 'b parser) : 'b parser =
  fun input ->
    List.concat_map (fun (x, reste) -> f x reste) (p input)

let any = function [] -> [] | c :: cs -> [c, cs]

let satisfy p =
  any >>= fun c -> if p c then return c else fail

let char c = satisfy (fun x -> x = c)

let alt p1 p2 = fun input ->
  match p1 input with [] -> p2 input | res -> res

let ( <|> ) = alt

let rec rep p =
  alt (p >>= fun x -> rep p >>= fun xs -> return (x :: xs))
      (return [])

let map f p = p >>= fun x -> return (f x)

let ( *> ) p1 p2 = p1 >>= fun _ -> p2
let ( <* ) p1 p2 = p1 >>= fun x -> p2 >>= fun _ -> return x

(* --- Parseur d'entiers naturels --- *)
let digit = satisfy (fun c -> c >= '0' && c <= '9')

let rec rep1 p =
  p >>= fun x -> rep p >>= fun xs -> return (x :: xs)

let entier_naturel : int parser =
  rep1 digit >>= fun cs ->
  return (int_of_string (String.of_seq (List.to_seq cs)))

(* --- Parseur d'expressions arithmétiques --- *)
(* Grammaire (sans précédence explicite, on la gère par hiérarchie) :
     expr     = terme (('+' | '-') terme)*
     terme    = facteur (('*' | '/') facteur)*
     facteur  = entier | '(' expr ')' | '-' facteur
*)

let parse input =
  let ws = rep (satisfy (fun c -> c = ' ' || c = '\t')) *> return () in
  let token p = ws *> p <* ws in

  let addop = token (char '+' >>= fun _ -> return (fun x y -> Add (x, y))) <|>
              token (char '-' >>= fun _ -> return (fun x y -> Sub (x, y)))
  and mulop = token (char '*' >>= fun _ -> return (fun x y -> Mul (x, y))) <|>
              token (char '/' >>= fun _ -> return (fun x y -> Div (x, y))) in

  let rec expr input =
    (terme >>= fun x ->
     rep (addop >>= fun op ->
          terme >>= fun y ->
          return (fun gauche -> op gauche y)) >>= fun ops ->
     return (List.fold_left (fun acc f -> f acc) x ops)) input

  and terme input =
    (facteur >>= fun x ->
     rep (mulop >>= fun op ->
          facteur >>= fun y ->
          return (fun gauche -> op gauche y)) >>= fun ops ->
     return (List.fold_left (fun acc f -> f acc) x ops)) input

  and facteur input =
    ((token entier_naturel >>= fun n -> return (Num n)) <|>
     (token (char '-') *> facteur >>= fun f -> return (Sub (Num 0, f))) <|>
     (char '(' *> expr <* char ')')) input
  in
  expr (List.of_seq (String.to_seq input))

(* --- Évaluateur --- *)
let rec eval = function
  | Num n -> n
  | Add (g, d) -> eval g + eval d
  | Sub (g, d) -> eval g - eval d
  | Mul (g, d) -> eval g * eval d
  | Div (g, d) ->
    let d' = eval d in
    if d' = 0 then failwith "Division par zéro"
    else eval g / d'

(* --- Affichage de l'AST (pour déboguer) --- *)
let rec affiche_ast = function
  | Num n -> string_of_int n
  | Add (g, d) -> "(" ^ affiche_ast g ^ " + " ^ affiche_ast d ^ ")"
  | Sub (g, d) -> "(" ^ affiche_ast g ^ " - " ^ affiche_ast d ^ ")"
  | Mul (g, d) -> "(" ^ affiche_ast g ^ " * " ^ affiche_ast d ^ ")"
  | Div (g, d) -> "(" ^ affiche_ast g ^ " / " ^ affiche_ast d ^ ")"

(* --- REPL : boucle principale --- *)
let rec repl () =
  Printf.printf "> %!";
  try
    let ligne = input_line stdin in
    if ligne = "quit" || ligne = "exit" then ()
    else if ligne = "" then repl ()
    else
      match parse ligne with
      | [] -> Printf.printf "  Erreur de syntaxe\n%!"; repl ()
      | (ast, reste) :: _ ->
        Printf.printf "  AST : %s\n%!" (affiche_ast ast);
        if reste <> [] then
          Printf.printf "  Attention : reste non analysé\n%!";
        (try
           let r = eval ast in
           Printf.printf "  = %d\n%!" r
         with Failure s -> Printf.printf "  Erreur : %s\n%!" s);
        repl ()
  with End_of_file -> Printf.printf "\n%!"

(* --- Programme principal --- *)
let () =
  Printf.printf "=== Calculatrice ===\n";
  Printf.printf "Entrez une expression arithmétique (ou 'quit' pour quitter).\n\n";
  repl ()