Probleme – De l'arbre à la pile : évaluer une expression

Exercice · niveau 3 (difficile) · informatique (MP2I/MPI), chapitre 10 — Arbres

Énoncé

Une expression arithmétique est l'ensemble inductif engendré par les constantes et les deux règles $+$ et $\times$ .

Écrire l'évaluation directe sur l'arbre.
Écrire la production de la suite postfixée des jetons.
Écrire l'évaluation d'une suite postfixée par une pile, et prouver qu'elle donne le même résultat.
Quelle hauteur de pile faut-il prévoir ?

Corrigé

1. L'évaluation sur l'arbre est le cas d'école de l'induction : la structure de la fonction est la structure du type.


type expr = Cst of int | Plus of expr * expr | Fois of expr * expr

(* Valeur de e. Terminaison : ordre induit. Complexite : Theta(n). *)
let rec evalue = function
  | Cst n -> n
  | Plus (a, b) -> evalue a + evalue b
  | Fois (a, b) -> evalue a * evalue b

2. La suite postfixée.


type jeton = J of int | Op of char

(* Suite postfixee des jetons de e : les operandes AVANT l'operateur. *)
let rec postfixe = function
  | Cst n -> [J n]
  | Plus (a, b) -> postfixe a @ postfixe b @ [Op '+']
  | Fois (a, b) -> postfixe a @ postfixe b @ [Op '*']

Mesures : $2 + 3 \times 4$ donne 2 3 4 <em> + et vaut $14$ ; $(2 + 3) \times 4$ donne 2 3 + 4 </em> et vaut $20$ . Les deux suites contiennent les mêmes jetons dans un ordre différent, et aucune parenthèse n'y figure : la priorité est portée par l'ordre. C'est ce qui fait l'intérêt de la notation postfixée.

3. L'évaluation par une pile.


(* Valeur de la suite postfixee l.
   Precondition : l provient de `postfixe` appliquee a une expression.
   Complexite : Theta(|l|) en temps, O(hauteur de pile) en memoire. *)
let evalue_postfixe l =
  let pile = List.fold_left (fun p j -> match j, p with
    | J n, p -> n :: p                                   (* on EMPILE *)
    | Op c, y :: x :: r -> (if c = '+' then x + y else x * y) :: r
    | Op _, _ -> failwith "pile trop courte") [] l in
  match pile with
  | [v] -> v
  | _ -> failwith "pile finale de taille differente de 1"

Noter l'ordre y :: x :: r et le calcul x + y : le sommet de pile est le second opérande, puisqu'il a été empilé en dernier. Sur l'addition et la multiplication cela ne se voit pas ; sur une soustraction, l'inversion serait une faute silencieuse.

<details class="group my-6 border border-gray-300 rounded-2xl bg-black/[0.03] overflow-hidden transition-all duration-300"><summary style="color:#1e3a8a" class="flex items-center justify-between p-4 cursor-pointer text-xs font-bold select-none"><div class="flex items-center"><i class="fa-solid fa-key mr-2"></i>Démonstration (que les deux évaluations coïncident)</div><span class="transition-transform group-open:rotate-180"><i class="fa-solid fa-chevron-down"></i></span></summary><div style="color:#1d4ed8" class="force-blue p-4 pt-0 border-t border-gray-200 bg-black/[0.02] leading-relaxed font-sans text-xs select-text"> On démontre l'énoncé renforcé, par induction structurelle sur $e$ :

$(R) pour toute pile p, parcourt (postfixe (e), p) = evalue (e) :: p,$

où $parcourt$ est le fold_left partant de la pile $p$ .

Cas $Cst (n)$ . La suite est $[J n]$ : on empile $n$ , et l'on obtient $n :: p = evalue (e) :: p$ .

Cas $Plus (a, b)$ . La suite est $postfixe (a) @ postfixe (b) @ [O p +]$ . Par hypothèse d'induction sur $a$ avec la pile $p$ , on arrive à $evalue (a) :: p$ . Par hypothèse d'induction sur $b$ avec cette nouvelle pile, on arrive à $evalue (b) :: evalue (a) :: p$ . Le jeton $O p +$ dépile les deux et empile leur somme : $(evalue (a) + evalue (b)) :: p = evalue (e) :: p$ .

Cas $Fois$ : identique.

Là encore, c'est la quantification « pour toute pile $p$ » qui fait passer l'induction — exactement comme la quantification sur $ℓ$ dans le problème précédent. Sans elle, l'hypothèse ne s'applique pas au second sous-arbre, dont l'évaluation commence sur une pile non vide.

Vérification : sur $20000$ expressions tirées au hasard jusqu'à la profondeur $6$ , $evalue_postfixe (postfixe (e)) = evalue (e)$ à chaque fois.

4. La hauteur de pile. Elle vaut exactement $1 +$ (nombre de jetons empilés en attente), et l'on montre par induction que la hauteur maximale atteinte en évaluant $e$ à partir d'une pile vide est

$H (Cst) = 1, H (a ⋆ b) = max (H (a), 1 + H (b)) .$

Le $1 +$ devant $H (b)$ dit que la valeur de $a$ occupe une case pendant toute l'évaluation de $b$ . Il en résulte $H (e) \leq 1 + h (e)$ , où $h$ est la hauteur de l'arbre. Mesure : sur les expressions de profondeur $6$ , la plus grande hauteur de pile observée est $7$ , ce qui sature la borne.

Le fait remarquable qu'on peut en tirer. La formule $H (a ⋆ b) = max (H (a), 1 + H (b))$ n'est pas symétrique : évaluer d'abord le sous-arbre le plus profond économise de la pile. C'est le nombre d'Ershov, et c'est ce qu'un vrai compilateur calcule pour allouer ses registres : évaluer le sous-arbre le plus exigeant en premier minimise le nombre de registres occupés simultanément.

Ce que ce problème boucle. Un arbre, sa forme aplatie, une pile, et le tout qui redonne la même valeur : c'est le lien annoncé par le cours entre les parcours et l'empilement des blocs d'activation. La pile de evalue_postfixe est, à peu de chose près, celle qu'aurait construite la récursion de evalue.

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.