Aller au contenu

Piles

On redonne l'interface des piles en OCaml (voir le chapitre sur les piles et files). On utilisera directement ces fonctions dans la suite.

let creer_pile () = ref []
let empile p x = p := x :: !p
let depile p = match !p with
    | [] -> failwith "pile vide"
    | t::q -> p := q; t
let est_vide p = !p = []

Comme on va être amenés à dépiler en ignorant la valeur renvoyée, OCaml va faire un avertissement car on jette la valeur alors qu'elle n'est pas de type unit. Pour éviter cet avertissement, on utilise la fonction ignore : ignore (depile p) pourra ainsi être appelé pour retirer une valeur de la pile en l'ignorant.

Expressions bien parenthésées

Avec un seul type de parenthèses

On va considérer des chaînes de caractères contenant des parenthèses et des lettres comme "(a(bc)a)" et on va chercher à savoir si elles sont bien parenthésées : c'est-à-dire que toutes les parenthèses ouvertes sont bien fermées. Pour cela, il suffit de compter le nombre de parenthèses ouvertes non encore fermées, de s'assurer qu'il ne devient jamais négatif et qu'à la fin il vaut 0.

Rappel, on accède au \(i\)-ème caractère de la chaîne s avec s.[i] et on obtient sa taille avec String.length.

Question 1. Écrire une fonction bien_parenthesee : string -> bool.

Tests 
assert(bien_parenthesee "(a(bc)a)");
assert(not (bien_parenthesee "(a(bc)a"));
assert(not (bien_parenthesee "(a)bc)a("));
assert(bien_parenthesee "(()(()))((())())");
"OK";;
Corrigé 
let bien_parenthesee s : bool =
    let ouvertes = ref 0 in
    let bp = ref true in
    for i = 0 to String.length s - 1 do
       let c = s.[i] in 
       if c = '('
       then incr ouvertes;
       if c = ')'
       then begin
           if !ouvertes = 0 then bp := false;
           decr ouvertes
       end
    done;
    !ouvertes = 0 && !bp

Avec plusieurs types de parenthèses

Maintenant, on va considérer une liste l de couples (ouvrant,fermant) comme ('(', ')') ou ('{','}') indiquant quels types de parenthèses sont autorisés et on va poser la même question du parenthésage. Ainsi avec la liste let l = [('(', ')'); ('{', '}'); ('[', ']') ] la chaîne (a{bc})[a(b)] est bien parenthésée mais (a} ne l'est pas (pas le même symbole qui ferme) et ([(b)] non plus (pas de ) fermante).

On ne va donc plus pouvoir utiliser un simple entier. On ne peut pas non plus utiliser un entier par symbole car cela ne permettrait pas de détecter des problèmes comme ([)] (exercice : vous en convaincre). On va donc utiliser une pile de symboles de fermeture attendus. Au départ, la pile est vide, ensuite, à chaque fois qu'on voit un symbole d'ouverture on empile le symbole de fermeture correspondant, et si on voit un symbole de fermeture on s'assure que ce soit le sommet de la pile, que l'on dépile.

Question 2. Écrire une fonction bien_parenthesee_l : (char * char) list -> string -> bool.

Tests 
assert(bien_parenthesee_l [('(',')')] "(a(bc)a)");
assert(not (bien_parenthesee_l [('(',')')] "(a(bc)a"));
assert(not (bien_parenthesee_l [('(',')')] "(a)bc)a("));
assert(bien_parenthesee_l [('(',')')] "(()(()))((())())");
assert(bien_parenthesee_l [('(', ')'); ('{', '}'); ('[', ']')] "([]{}){[()]()}");
assert(not (bien_parenthesee_l [('(', ')'); ('{', '}'); ('[', ']')] "([)]"));
assert(not (bien_parenthesee_l [('(', ')'); ('{', '}'); ('[', ']')] "([)}"));
"OK";;
Corrigé 
let bien_parenthesee_l (l:(char * char) list) (s:string) : bool =
    let ouvertes = creer_pile () in
    let bp = ref true in
    for i = 0 to String.length s - 1 do
       let c = s.[i] in 
       let rec aux l = match l with
           | (o,f)::q ->
               if c = o
               then empile ouvertes f;
               if c = f
               then bp := !bp && (not (est_vide ouvertes) && depile ouvertes = f);
               aux q
           | [] -> ()
       in aux l
    done;
    est_vide ouvertes && !bp

Pile pour évaluer des expressions

Forme postfixe

On va considérer ici des expressions écrites sous forme postfixe.

La présentation traditionnelle des expressions est infixe : le symbole d'opération est au milieu des opérandes, comme dans 2 + 3. Cette notation est naturelle mais a le désavantage de nécessiter des parenthèses comme dans (2 + 3) * 5. Une autre possibilité est d'avoir une notation postfixe 2 3 + où le symbole vient après ses opérandes. L'avantage est de ne pas avoir besoin de parenthèses, en effet, on peut écrire 2 3 + 5 * dans l'exemple précédent.

En OCaml, on représentera une telle expression sous la forme d'une liste contenant :

  • soit des entiers pour les constantes ;
  • soit une opération parmi +, -, *, /.

Pour cela on définit le type suivant :

type op = Plus | Minus | Mult | Div
type token = C of int | O of op

L'expression précédente correspond alors à la liste [ C 2; C 3; O Plus; C 5; O Mult ].

Pour évaluer une telle expression, on utilise une pile, initialement vide, et on parcourt de gauche à droite l'expression postfixe. Si la valeur lue est

  • un entier : on le place sur la pile ;
  • un symbole d'opération : on dépile deux valeurs sur la pile et on effectue l'opération, puis on empile le résultat.

Quand on a fini le parcours, il ne doit y avoir qu'une seule valeur sur la pile qui est le résultat (sinon, c'est un problème similaire à un mauvais parenthésage). On dit qu'une expression qui permet d'aboutir à une unique valeur à la fin du parcours, sans jamais dépiler une pile vide, est bien formée.

Pour les opérations non commutatives comme - et /, on adopte la convention que a b - calcule a - b. Il faudra donc faire attention à respecter cela dans l'évaluation. On effectue aussi des divisions entières ici et non flottantes.

Question 3. Écrire une fonction d'évaluation des expressions evalue : token list -> int.

Tests 
assert(evalue [C 1; C 2; O Plus] = 3);
assert(evalue [C 1; C 2; O Minus] = -1);
assert(evalue [C 3; C 1; O Minus; C 5; O Mult] = 10);
assert(evalue [C 1; C 2; O Plus;  C 2; O Div] = 1);
assert(evalue [C 1; C 2; C 3; C 4; C 5; C 6; O Plus; O Mult; O Div; O Minus; O Plus] = 3);
"OK";;
Corrigé 
let evalue (e : token list) : int =
    let p = creer_pile () in
    let rec aux e = match e with
        | C k :: e' -> empile p k; aux e'
        | O o :: e' ->
            let op2 = depile p in
            let op1 = depile p in
            let res = match o with
                | Plus -> op1 + op2
                | Minus -> op1 - op2
                | Mult -> op1 * op2
                | Div -> op1 / op2
            in empile p res; aux e'
        | [] -> ()
    in
    aux e;
    let res = depile p in
    if not (est_vide p) then failwith "expression mal formée";
    res

Forme infixe : algorithme de Dijkstra

On a vu comment évaluer une expression postfixe avec une pile. Dijkstra a trouvé un algorithme utilisant deux piles pour évaluer une expression infixe, c'est-à-dire une expression standard avec des parenthèses comme \(((1+(2\times 3))-(3\times (4 \times 2)))\).

Attention Il y a même des parenthèses autour de l'expression entière et on place également les parenthèses pourtant inutiles des opérations associatives : chaque opération est entourée de parenthèses. On verra plus tard qu'il s'agit ici d'un arbre binaire.

On considère deux piles, une pile de nombres et une pile d'opérateurs.

Pour chaque symbole :

  • si c'est une parenthèse ouvrante, on l'ignore ;
  • si c'est un nombre on le pousse sur la pile de nombres ;
  • si c'est un opérateur on le pousse sur la pile d'opérateurs ;
  • si c'est une parenthèse fermante, on dépile un opérateur et autant de nombres que son arité (son nombre d'opérandes), puis on empile le résultat.

Pour simplifier, on ne considère ici que des opérations binaires. Il faudra donc retirer deux nombres de la pile à chaque fois.

Question 4. Évaluer ainsi à la main \((1+((2+3)\times (4\times 5)))\).

Corrigé

En notant les piles avec le sommet à droite :

Symbole lu Pile de nombres Pile d'opérateurs
(1+((2+3 1 2 3 + +
) 1 5 +
*(4*5 1 5 4 5 + * *
) 1 5 20 + *
) 1 100 +
) 101

Le résultat est \(101\).

Pour simplifier, on ne va considérer que des chiffres, ainsi, il suffira de s'assurer qu'un caractère est entre '0' et '9' pour le convertir avec int_of_char c - int_of_char '0' en un int.

Remarque

En OCaml, on peut filtrer une plage de caractères comme ici en utilisant le filtrage | '0'..'9' ->

Question 5. Écrire une fonction evalue_infixe : string -> int qui met en œuvre cet algorithme.

Tests 
assert (evalue_infixe "(1+2)" = 3);
assert (evalue_infixe "(2-1)" = 1);
assert (evalue_infixe "(3*(1+2))" = 9);
assert(evalue_infixe "(1+((2+3)*(4*5)))" = 101);
"OK";;
Corrigé 
let evalue_infixe s =
    let nb = creer_pile () in
    let op = creer_pile () in
    for i = 0 to String.length s - 1 do
        match s.[i] with
        | '(' -> ()
        | '0'..'9' ->
            empile nb (int_of_char s.[i] - int_of_char '0')
        | '*' | '-' | '/' | '+' -> empile op s.[i]
        | ')' -> begin
            let b = depile nb in
            let a = depile nb in
            match depile op with
            | '*' -> empile nb (a*b)
            | '-' -> empile nb (a-b)
            | '/' -> empile nb (a/b)
            | '+' -> empile nb (a+b)
            | _ -> failwith "unreachable"
        end
        | _ -> failwith "Invalid character"
    done;
    depile nb

File avec deux piles

On va implémenter une file avec deux piles.

On a vu qu'il suffisait de faire une 'a list ref pour avoir une pile en OCaml, mais pour réaliser une file, comme on va changer les deux listes, on considère plutôt le type suivant :

type 'a file = { 
    mutable entree : 'a list;
    mutable sortie : 'a list
}

Ainsi, chaque champ mutable sera une sorte de référence. On enfile en tête de la liste entree et on défile en tête de la liste sortie ; quand sortie est vide, on y transvase entree en la renversant.

Question 6. Écrire les fonctions suivantes :

  • cree_file : unit -> 'a file qui crée une file vide ;
  • est_vide : 'a file -> bool ;
  • enfile : 'a file -> 'a -> unit ;
  • transvase : 'a file -> unit qui, lorsque sortie est vide, y place les éléments de entree dans le bon ordre ;
  • defile : 'a file -> 'a qui retire et renvoie l'élément le plus ancien.
Tests 
let f = cree_file () in
Printf.printf "Test enfile: ";
assert(est_vide f);
enfile f 1;
enfile f 2;
enfile f 3;
Printf.printf "OK\n";
Printf.printf "Test transvase: ";
assert(f.entree = [3;2;1] && f.sortie = []);
transvase f;
Printf.printf "OK\n";
Printf.printf "Test defile: ";
assert(f.entree = [] && f.sortie = [1;2;3]);
assert(defile f = 1);
assert(defile f = 2);
enfile f 4;
assert(defile f = 3);
assert(defile f = 4);
assert(est_vide f);
Printf.printf "OK\n";;
Corrigé 
let cree_file () : 'a file =
    {
        entree = [];
        sortie = []
    }

let est_vide (f:'a file) : bool =
    f.entree = [] && f.sortie = []

let enfile (f:'a file) (x:'a) : unit =
    f.entree <- x::f.entree

let transvase (f:'a file) : unit =
    assert(f.sortie = []);
    f.sortie <- List.rev f.entree;
    f.entree <- []

let defile (f : 'a file) : 'a =
    if f.sortie = []
    then transvase f;
    match f.sortie with
    | [] -> failwith "File vide"
    | t::q -> f.sortie <- q; t

Chaque élément est déplacé au plus une fois de entree vers sortie : une suite de \(n\) opérations coûte \(O(n)\), soit un coût amorti constant par opération (voir le chapitre sur la complexité amortie).