In [ ]:
Nom = ""
Prénom = ""

DM 9 - Arbres algébriques¶

1 - Présentation¶

Une expression algébrique peut être représentée par un arbre binaire, dont les noeuds sont soit des nombres, soit des opérations.

Par exemple, l'expression :

$$ \frac{2+3}{1+4\times2} $$

peut être représentée par l'arbre :

Le but de ce DM est d'évaluer la valeur d'un tel arbre, celui-ci étant donné.

On utilisera les règles suivantes :

  • seules les trois opérations +, * et / seront utilisées ;
  • les opérations et les variables seront représentées par des chaines de caractères ;
  • les nombres seront représentés par des nombres flottants ;
  • pour un noeud dont la valeur est une opération, le sous-arbre gauche représente l'opérande gauche de l'opération, le sous-arbre droite celle de droite ;

Un arbre binaire est un ensemble de noeuds, ceux-ci étant des objets de la classe Noeud :

In [ ]:
from display import to_string

class Noeud:
    
    __str__ = to_string
    
    def __init__(self, gauche, valeur, droit):
        self.gauche = gauche
        self.v = valeur
        self.droit = droit
        

class TreeError(Exception):
    
    def __init__(self, message):
        self.message = message

L'arbre de l'exemple précédent sera donc implémenté par :

In [ ]:
exemple = Noeud(Noeud(Noeud(None, 2.0, None), '+', Noeud(None, 7.0, None)),
                '/',
                Noeud(Noeud(None, 1.0, None), '+', Noeud(Noeud(None, 4.0, None),'*', Noeud(None, 2.0, None))))

print(exemple)

Les arbres algébriques pourront également contenir des variables, représentées par des chaines de caractères (par exemple 'x' ou 'y'). Les valeurs de ces variables sont données par un dictionnaire. Par exemple :

{'x': 3, 'y': 5}

Ici, la variable $x$ vaut 3 et la variable $y$ vaut 5.

Votre programme doit être capable de gérer n'importe quel nom de variable (pas seulement $x$ et $y$).

2 - Implémentation de l'évaluation¶

Vous allez programmer une fonction eval_arbre qui prend en argument un arbre algébrique et un dictionnaire de constantes et renvoie le nombre obtenu après avoir fait les calculs.

La fonction eval_arbre devra être capable de détecter d'éventuelles malformations de l'arbre algébrique et le cas échéant soulever l'exception TreeError.

In [ ]:
def eval_arbre(racine, vars_d):
    """
    Evalue l'arbre algébrique en utilisant les valeurs du dictionnaire vars_d pour les
    constantes
    :param racine: (objet Noeud) la racine de l'arbre algébrique
    :param vars_d: (dict) le dictionnaire des valeurs des variables
    :return: (float) le nombre obtenu après avoir effectué les opérations
    """
    # Insérez votre code ici
In [ ]:
arbre1 = Noeud(Noeud(Noeud(None, 2.0, None), '+', Noeud(None, 7.0, None)),
                '/',
                Noeud(Noeud(None, 1.0, None), '+', Noeud(Noeud(None, 4.0, None),'*', Noeud(None, 2.0, None))))
assert eval_arbre(arbre1, dict()) == 1.0

arbre2 = Noeud(Noeud(Noeud(Noeud(None, 'x', None) ,'*', Noeud(None, 'x', None)) , '+', Noeud(Noeud(None, 5.0, None), '*', Noeud(None, 'y', None))) , '/', Noeud(None, 12.0, None))
vars1 = {'x': 2.0, 'y': 4.0}
assert eval_arbre(arbre2, vars1) == 2.0

vars2 = {'x': -1.0, 'y': 1.0}
assert eval_arbre(arbre2, vars2) == 0.5

# arbre malformé
arbre3 = Noeud(Noeud(None, 2.3, None), '+', None)
test_arbre3 = False
try:
    eval_arbre(arbre3, dict())
except TreeError:
    test_arbre3 = True
assert test_arbre3, "L'exception TreeError n'est pas levée"

# Mauvaise valeur pour une feuille
arbre4 = Noeud(Noeud(None, 2.3, None), '+', Noeud(None, Noeud, None))
test_arbre4 = False
try:
    eval_arbre(arbre4, dict())
except TreeError:
    test_arbre4 = True
assert test_arbre4, "L'exception TreeError n'est pas levée"