(* ################################################# EXERCICE 2 ################################################# *) type lexeme = Valeur of int | Op_unaire of int -> int | Op_binaire of int -> int -> int ;; let minus = Op_unaire (fun x -> -x) and plus = Op_binaire (fun x -> fun y -> x+y) and moins = Op_binaire (fun x -> fun y -> x-y) and times = Op_binaire (fun x -> fun y -> x*y) and div = Op_binaire (fun x -> fun y -> x/y);; let exemple_flot = [minus; times; moins; Valeur 6; Valeur 4; plus; Valeur 4; Valeur 5];; (* cette exemple représente l'expression -((6-4)*(4+5)) sous forme postfixée. L'évaluateur doit retourner le résultat de cette expression. *) let rec evaluateur pile = function | [] -> begin match sommet pile with | Valeur n -> if est_vide (depile pile) then n else failwith "l'expression est syntaxiquement incorrecte" | _ -> failwith "l'expression est syntaxiquement incorrecte" end | t::q -> match t with | Valeur n -> begin match sommet pile with | Op_unaire f -> evaluateur (depile pile) ((f n)::q) | Valeur p -> let Op_binaire g = sommet (depile pile) in (* ici, les piles sont sans effet de bord *) evaluateur (depile (depile pile)) ((g p n)::q) | Op_binaire g -> evaluateur (empile t pile) q end | _ -> evaluateur (empile t pile) q ;; (* partout où l'on dépile sans se soucier de savoir si la pile est vide, une exception est retournée ssi l'expression en entrée est syntaxiquement incorrecte *) let evaluateur_gene flot = try evaluateur (pile_vide ()) flot with _ -> failwith "l'expression est syntaxiquement incorrecte";; (* ################################################# EXERCICE 3 ################################################# *) type mot == int list;; (* a_i est représentée par 2*i et a_(i+1) par 2*i+1 *) let est_ouvrante n = (n mod 2) = 0;; let rec bien_parenthese_aux pile = function | [] -> est_vide pile | t::q -> if est_ouvrante t then bien_parenthese_aux ( empile t pile ) else if (sommet pile)+1 = t (* le jour du concours, faire le test de est_vide avant de chercher le sommet de pile pour ne pas retourner d'exception *) then bien_parenthese_aux ( depile pile ) else false ;; let bien_parenthese mot = try bien_parenthese_aux ( pile_vide () ) mot with Pile_vide -> false;; (* on montre que le langage de Dyck n'est pas rationnel à l'aide du théorème de l'étoile d'Ogden *) (* ################################################# EXERCICE 4 ################################################# *) (* implémentation à l'aide d'un couple de listes *) exception File_vide;; type 'a file == ('a list)*('a list);; let file_vide () = (([],[]) : 'a file);; let enfile (f : 'a file) x = let (a,b) = f in ( (a,x::b) : 'a file );; let est_vide (f : 'a file) = (fst(f) = []) & (snd(f) = []);; let normalise (f : 'a file) = let (a,b) = f in if a = [] then (rev(b),[]) else f;; let defile f = if est_vide f then raise File_vide else let (a,b) = normalise f in ( hd(a) , ( (tl(a),b) : 'a file ) );; let rec multiEnfile f ens = it_list enfile f ens;; (* ################################################# EXERCICE 5 ################################################# *) type graphe == (int list) vect;; let creerGraphe n donnees = let succ = make_vect n [] in let rec aux = function | [] -> succ | (a,b)::q -> succ.(a) <- b::(succ.(a)); succ.(b) <- a::(succ.(b)); aux q in aux donnees;; let exD = [(0,1);(1,2);(2,3);(5,6);(12,13);(13,14);(14,15); (4,8);(8,12);(1,5);(5,9);(6,10);(10,14);(7,11);(11,15)];; let parcoursLargeur (succ : graphe) ini = let n = vect_length succ in if (ini < 0) or (ini >= n) then failwith "sommet absent"; let f2 = enfile (file_vide ()) ini (* file qui stocke les éléments dont on doit visiterles voisins *) and visites = make_vect n 0 (* stocke le temps auquel on a visité un noeud si c'est zéro, le noeud n'a pas été visité *) and pere = make_vect n (-1) in (* on stocke le père d'un noeud dans l'arborescence du parcours en largeur *) let rec affectPere s = function | [] -> () (* fonction qui affecte le père s à la liste des voisins de s *) | t::q -> if pere.(t) = -1 then pere.(t) <- s; affectPere s q in let rec parcours f temps = if est_vide f then () else let (s,g) = defile f in if visites.(s) <> 0 then parcours g temps else ( visites.(s) <- temps; let suivant = succ.(s) in let h = multiEnfile g suivant in affectPere s suivant; parcours h (temps+1) ) in parcours f2 1; (visites,pere);; (* l'arborescence résultant de ce parcours en largeur est représentée par la fonction père, stockée sous forme d'un tableau. Trouver une solution d'un labyrinthe consiste à faire un parcours en largeur à partir de l'entrée et de remonter l'arborescence obtenue à partir du sommet "sortie". La propriété de ce parcours est que le chemin obtenu est de longueur minimale (en nombre de sommets sur le chemin) *) let cheminLabyrinthe laby entree sortie = let (visites,pere) = parcoursLargeur laby entree in let rec remontee chemin = let t = List.hd(chemin) in if t = entree then chemin else remontee ( (pere.(t))::chemin ) in if visites.(sortie) = 0 then failwith "sortie impossible" else remontee [sortie] ;; cheminLabyrinthe (creerGraphe 16 exD) 3 12;;