Arbres d'expression arithmétique
Un arbre d'expression est un arbre binaire qui représente une expression arithmétique :
- les feuilles contiennent des nombres entiers,
- les nœuds internes contiennent des opérateurs :
'+','-','*','/'.
Représentation Python : identique à la convention habituelle.
# Arbre vide : None
# Nœud : [val, g, d]
# val = entier ou opérateur (str)
# g = sous-arbre gauche
# d = sous-arbre droit
Exemple — l'expression $(3 + 5) \times (8 - 2)$ :
expr1 = ['*',
['+', [3, None, None], [5, None, None]],
['-', [8, None, None], [2, None, None]]]
Écrire une fonction est_feuille(a) qui retourne True si le nœud a (non vide) est une feuille, False sinon.
def est_feuille(a):
return a[1] is None and a[2] is None
Écrire une fonction nb_noeuds(a) qui retourne le nombre total de nœuds de l'arbre a.
Exemple
nb_noeuds(expr1)
7
def nb_noeuds(a):
if a is None:
return 0
return 1 + nb_noeuds(a[1]) + nb_noeuds(a[2])
Écrire une fonction nb_feuilles(a) qui retourne le nombre de feuilles de l'arbre a.
Exemple
nb_feuilles(expr1)
4
def nb_feuilles(a):
if a is None:
return 0
if est_feuille(a):
return 1
return nb_feuilles(a[1]) + nb_feuilles(a[2])
On admet que dans tout arbre d'expression bien formé, chaque nœud interne possède exactement deux enfants. Démontrer par récurrence sur la hauteur $h$ que le nombre de feuilles $f$ et le nombre de nœuds internes $n_i$ vérifient toujours : $$f = n_i + 1$$ Vérifier cette relation sur expr1.
Démonstration par récurrence sur la hauteur $h$ :
- Cas de base ($h = 0$) : L'arbre est une feuille unique. Alors $f = 1$ et $n_i = 0$, donc $f = n_i + 1$.
- Hypothèse de récurrence : Supposons que la propriété est vraie pour tout arbre de hauteur $h$.
- Hérédité : Soit un arbre de hauteur $h+1$ dont la racine est un nœud interne avec deux sous-arbres $G$ et $D$ (chacun de hauteur ≤ $h$).
Par hypothèse, pour $G$ : $f_G = n_{i_G} + 1$
Pour $D$ : $f_D = n_{i_D} + 1$
Pour l'arbre complet : $f = f_G + f_D$ et $n_i = 1 + n_{i_G} + n_{i_D}$
Donc $f = (n_{i_G} + 1) + (n_{i_D} + 1) = (n_{i_G} + n_{i_D} + 1) + 1 = n_i + 1$.
Vérification sur expr1 : $f = 4$, $n_i = 3$, donc $4 = 3 + 1$.
Écrire une fonction evaluer(a) qui calcule la valeur numérique de l'expression représentée par l'arbre a. On supposera qu'aucune division par zéro n'a lieu.
Exemple
evaluer(expr1)
48
def evaluer(a):
if a is None:
return None
val = a[0]
if isinstance(val, (int, float)):
return val
gauche = evaluer(a[1])
droite = evaluer(a[2])
if val == '+':
return gauche + droite
elif val == '-':
return gauche - droite
elif val == '*':
return gauche * droite
elif val == '/':
return gauche / droite
Le parcours infixe d'un arbre d'expression produit l'expression arithmétique dans sa forme habituelle (avec parenthèses). Écrire une fonction infixe(a) qui retourne une chaîne de caractères représentant l'expression complètement parenthésée.
Exemple
infixe(expr1)
"((3+5)*(8-2))"
def infixe(a):
if a is None:
return ""
if est_feuille(a):
return str(a[0])
return "(" + infixe(a[1]) + str(a[0]) + infixe(a[2]) + ")"
Le parcours préfixe (notation polonaise) place l'opérateur avant ses opérandes. Écrire une fonction prefixe(a) qui retourne la représentation préfixe de l'expression, les éléments étant séparés par des espaces.
Exemple
prefixe(expr1)
"* + 3 5 - 8 2"
def prefixe(a):
if a is None:
return ""
if est_feuille(a):
return str(a[0])
return str(a[0]) + " " + prefixe(a[1]) + " " + prefixe(a[2])
On dispose d'une expression en notation préfixe représentée par une liste de tokens :
tokens = ['*', '+', 3, 5, '-', 8, 2]
Écrire une fonction récursive construire(tokens, i) qui prend la liste tokens et un indice i (position courante de lecture), et retourne le couple (arbre, j) où arbre est le sous-arbre construit à partir de la position i, et j est l'indice suivant la dernière position consommée.
Exemple
arbre, _ = construire(tokens, 0)
evaluer(arbre)
48
def construire(tokens, i):
token = tokens[i]
# Si le token est un nombre (feuille)
if isinstance(token, (int, float)):
return [token, None, None], i + 1
# Sinon, c'est un opérateur
gauche, j = construire(tokens, i + 1)
droite, k = construire(tokens, j)
return [token, gauche, droite], k
En déduire une fonction depuis_prefixe(tokens) qui retourne directement l'arbre construit depuis la liste complète.
def depuis_prefixe(tokens):
arbre, _ = construire(tokens, 0)
return arbre
Écrire une fonction profondeur_noeud(a, val) qui retourne la profondeur du premier nœud contenant la valeur val dans l'arbre a, ou -1 si cette valeur est absente.
Exemple
profondeur_noeud(expr1, 8)
2
profondeur_noeud(expr1, 9)
-1
def profondeur_noeud(a, val, prof=0):
if a is None:
return -1
if a[0] == val:
return prof
prof_gauche = profondeur_noeud(a[1], val, prof + 1)
if prof_gauche != -1:
return prof_gauche
return profondeur_noeud(a[2], val, prof + 1)
On appelle arbre filiforme un arbre binaire dans lequel chaque nœud interne possède au moins un enfant None (c'est-à-dire qu'il n'a jamais deux enfants non vides simultanément). Écrire une fonction est_filiforme(a) qui retourne True si l'arbre est filiforme, False sinon.
def est_filiforme(a):
if a is None:
return True
gauche = a[1]
droite = a[2]
# Si c'est une feuille, c'est filiforme
if gauche is None and droite is None:
return True
# Un nœud interne doit avoir au moins un enfant None
if gauche is None or droite is None:
# Récursivité sur l'enfant non vide
if gauche is not None:
return est_filiforme(gauche)
else:
return est_filiforme(droite)
# Si les deux enfants sont non vides, ce n'est pas filiforme
return False
Écrire une fonction miroir(a) qui retourne un nouvel arbre obtenu en échangeant récursivement les sous-arbres gauche et droit à chaque nœud.
Exemple
infixe(miroir(expr1))
"((2-8)*(5+3))"
def miroir(a):
if a is None:
return None
# Copier la valeur et échanger récursivement les enfants
return [a[0], miroir(a[2]), miroir(a[1])]
On souhaite simplifier l'arbre en appliquant deux règles :
- tout sous-arbre dont les deux enfants sont des feuilles numériques peut être remplacé par sa valeur calculée ;
- on n'applique cette règle qu'une seule fois, en remontant (parcours post-ordre).
Écrire une fonction simplifier(a) qui retourne l'arbre simplifié.
Exemple
expr2 = ['*', ['+', [3,None,None],[5,None,None]], ['-', [8,None,None],['x',None,None]]]
infixe(simplifier(expr2))
"(8*(8-x))"
def simplifier(a):
if a is None:
return None
# Simplifier récursivement les enfants
gauche = simplifier(a[1])
droite = simplifier(a[2])
# Vérifier si les deux enfants sont des feuilles numériques
if (gauche is not None and droite is not None and
isinstance(gauche[0], (int, float)) and est_feuille(gauche) and
isinstance(droite[0], (int, float)) and est_feuille(droite)):
# Remplacer par la valeur calculée
resultat = evaluer([a[0], gauche, droite])
return [resultat, None, None]
return [a[0], gauche, droite]
Écrire une fonction egaux_structure(a, b) qui retourne True si les deux arbres a et b ont exactement la même structure et les mêmes valeurs à chaque nœud.
def egaux_structure(a, b):
if a is None and b is None:
return True
if a is None or b is None:
return False
return (a[0] == b[0] and
egaux_structure(a[1], b[1]) and
egaux_structure(a[2], b[2]))
Deux expressions sont sémantiquement équivalentes si elles produisent la même valeur pour toute affectation de variables. Dans le cas simplifié où les arbres ne contiennent que des constantes (pas de variables), cela revient à comparer leur évaluation.
Écrire une fonction egaux_semantique(a, b) qui retourne True si evaluer(a) == evaluer(b), en gérant le cas où l'un des arbres est vide (retourner False).
Exemple
expr3 = ['+', ['*', [2,None,None],[4,None,None]], ['-', [10,None,None],[2,None,None]]]
# expr3 vaut 2*4 + (10-2) = 8+8 = 16
egaux_semantique(expr1, expr3)
False
expr4 = ['*', [6,None,None],[8,None,None]] # 48
egaux_semantique(expr1, expr4)
True
def egaux_semantique(a, b):
if a is None or b is None:
return False
return evaluer(a) == evaluer(b)
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.