TP6 : retour vers les arbres

Où l'on retrouve nos arbres, pour évaluer des expressions

Principe du TP

Nous allons maintenant revenir sur nos arbres, du TP4, afin de représenter les expressions RPN sous forme d’arbres.

Exercice 1, arbres simples


  1. Reprendre les arbres du TP4, mais ce coup-ci, ajouter sur les noeuds intérieurs un champ opérateur. Modifier le constructeur pour qu’il considère ce paramètre. Pour simplifier la suite.

  2. Écrire la fonction eval sur la classe arbre modifiée, qui évalue l’expression (l’arbre vide renvoyant None).


Exercice 2, les arbres en version POO


L’utilisation d’une variable “type”, et d’une seule classe pour tous les types d’arbre, est assez peu élégante. Dans un langage objet, on devrait utiliser l’héritage à la place. Nous allons donc créer quatre classes:


  • une classe TreeBase, qui contient des squelettes de fonctions, qui peuvent être virtuelles, comme :
       def eval(self):
       raise NotImplementedError


  • une classe TreeEmpty, qui hérite de TreeBase, et implémente le comportement d’un arbre vide ;

  • une classe TreeLeaf, qui hérite de TreeBase, et implémente le comportement d’une feuille ;

  • une classe TreeNode, qui hérite de TreeBase, et implémente le comportement d’un noeud intérieur.


Pour simplifier, on pourra se limiter aux fonctions suivantes: eval, height et leafcount. Réimplémenter les autres fonctions est laissé en exercice.


Exercice 3, la classe Stack2Tree


Le but va être de construire une classe, qui se comporte comme une pile, mais qui au lieu d’effectuer les calculs, va créer un arbre représentant l’expression, lorsqu’on appelle ses méthodes “op_”.


  1. Créer une classe Stack2Tree qui hérite de Stack.

  2. Réimplémenter la méthode push pour mettre des TreeLeaf au lieu des simples entiers dans la pile.

  3. Réimplémenter la méthode apply_op pour que, au lieu d’appliquer l’opérateur, on construise un arbre correspondant.

  4. La fonction rpn devrait, toute seule, créer des arbres, sans avoir à la modifier.

  5. Écrire une fonction eval qui appelle eval sur l’arbre contenu au sommet de la pile.


Exercice 4, ajout de l’aléatoire


  1. Ajouter un opérateur rand qui choisit un nombre aléatoire (1 6 rand étant un dé classique, 1 20 rand un d20 de rôliste).

  2. Écrire une méthode simplify sur les arbres, qui va simplifier l’arbre, en transformant en feuille toutes les sous-expressions qui ne contiennent pas d’aléatoire. Par exemple, l’arbre de l’expression 1 6 rand 2 3 + * devra être converti en l’arbre de l’expression 1 6 rand 5 *.