Option info - TP4 Evaluation d'expressions arithmétiques

(* Evaluation d'une expression abstraite *)

type ('a,'b) arbre =
    | Feuille of 'b
    | Noeud of 'a*(('a,'b) arbre)*(('a,'b) arbre);;

type expression_abstraite = (char,int) arbre;;

(*** INSERER ICI LES TROIS EXEMPLES ***)
let exemple1 =
Noeud(
    '+',
    Noeud(
            '+',
            Feuille 1,
            Feuille 2),
    Noeud(
            '+',
            Feuille 3,
            Feuille 4));;

let exemple2 =
Noeud(
        '+',
        Noeud(
                '+',
                Noeud(
                        '+',
                        Feuille 1,
                        Feuille 2),
                Feuille 3),
        Feuille 4);;

let exemple3 =
Noeud(
        '+',
        Feuille 20,
        Noeud(
                '+',
                Noeud(
                        '+',
                        Noeud(
                                '*',
                                Feuille 8,
                                Feuille 12),
                        Noeud(
                                '*',
                                Feuille 18,
                                Feuille 5)),
                Noeud(
                        '*',
                        Noeud(
                                '+',
                                Feuille 8,
                                Feuille 12),
                        Noeud(
                                '+',
                                Feuille 18,
                                Feuille 5))));;




let rec evaluer (a : expression_abstraite) = match a with
|Feuille f -> f
|Noeud (n,fg,fd) when n='+' -> (evaluer fg) + (evaluer fd)
|Noeud (n,fg,fd) when n='*' -> (evaluer fg) * (evaluer fd)
|Noeud (n,fg,fd) when n='-' -> (evaluer fg) - (evaluer fd);;


evaluer exemple1;;
evaluer exemple2;;
evaluer exemple3;;


(* Conversion d'une expression concrete *)

let chiffres = ['0';'1';'2';'3';'4';'5';'6';'7';'8';'9']
and operations = ['+';'*';'-'];;

int_of_string "01aa567a9";;

let nombre s =
try
let a=int_of_string s in
true
with
| _ -> false;;


let est_correct s =
    let rec aux s i j =
    (* teste si l'expression s.[i]...s.[j] est correcte *)
        try
        (* le rattrapage des exceptions est tres pratique ici : il permet d'eviter de verifier a chaque instant qu'on n'a pas depasse la longueur de la chaine ; si on depasse, c'est que c'est incorrect *)
            if nombre (String.sub s i (j-i+1)) then true
            (* les nombres sont corrects *)
            else if s.[i]<>'(' || s.[j]<>')' then false
            (* les autres commencent et finissent par une parenthese *)
            else begin
                let p = ref 1 in (* p compte les parentheses *)
                let k = ref i in (* k indique la position *)
                (* Compte s'il y a le bon nombres de parenthèses*)
                while !p>0 do
                    incr k;
                    if s.[!k]='(' then incr p;
                    if s.[!k]=')' then decr p;
                    done;
                (* Appel récursif sur la partie gauche, et la partie droite *)

                aux s (i+1) (!k-1) && (List.mem s.[!k+1] operations) && s.[!k+2]='(' && aux s (!k+3) (j-1) end
        with _ -> false in
        aux s 0 (String.length s - 1);;

est_correct "(((22)+(33))+((3)*(99)))*(100000000000)";;

let analyser s : expression_abstraite =
    let rec aux s i j =
    (* teste si l'expression s.[i]...s.[j] est correcte *)
        try
        (* le rattrapage des exceptions est tres pratique ici : il permet d'eviter de verifier a chaque instant qu'on n'a pas depasse la longueur de la chaine ; si on depasse, c'est que c'est incorrect *)
            if nombre (String.sub s i (j-i+1)) then Feuille (int_of_string (String.sub s i (j-i+1)))
            (* les nombres sont corrects *)
            else if s.[i]<>'(' || s.[j]<>')' then failwith ""
            (* les autres commencent et finissent par une parenthese *)
            else begin
                let p = ref 1 in (* p compte les parentheses *)
                let k = ref i in (* k indique la position *)
                (* Compte s'il y a le bon nombres de parenthèses*)
                while !p>0 do
                    incr k;
                    if s.[!k]='(' then incr p;
                    if s.[!k]=')' then decr p;
                    done;
                (* Appel récursif sur la partie gauche, et la partie droite *)
                (* aux s (i+1) (!k-1) && (List.mem s.[!k+1] operations) && aux s (!k+3) (j-1) end *)
                Noeud(s.[!k+1],aux s (i+1) (!k-1),aux s (!k+3) (j-1));
                end
        with _ -> failwith "Pas content !" in
        aux s 0 (String.length s - 1);;

est_correct "0";;

analyser "(((22)-(33))+((3)*(99)))+(0)";;


(* Boucle Read-Eval-Print *)




exception Fini;;

let boucle_REP () =
while true do
    let s = read_line() in
    if s="quitter" then raise Fini
    else
    if not (est_correct s)
        then print_string "Mauvaise expression\n"
        else begin
                print_string ">";
                print_string s;
                print_string "\n";
                print_int (evaluer (analyser s));
                print_string "\n";
                end
    done;;

boucle_REP ();;