Exercice 3 - Arbres · Bac Numérique et Sciences Informatiques Liban 2023 (jour 1)

Cet exercice traite des piles, des arbres et de l'algorithmique.

Dans cet exercice, on s'intéresse à la notation polonaise inversée (NPI) d'une expression mathématique. Dans cette notation, l'opérateur est placé après les nombres sur lesquels il s'applique. On se limitera aux expressions faisant intervenir des nombres entiers et les quatre opérateurs: $+$, $-$, $\times$, $/$.

Par exemple, l'expression $4 \times (5 + 7)$ s'écrit, en NPI: $4\ 5\ 7\ +\ \times$

L'évaluation de l'expression $12 / 2 - 4 + 5 \times 3$, écrite en NPI: $12\ 2\ /\ 4\ -\ 5\ 3\ \times\ +$ est détaillée ci-dessous. Cette expression s'évalue à $17$ de la manière suivante:

lorsqu'on rencontre un premier opérateur ($+$, $-$, $/$, $\times$), on évalue l'opération avec les deux nombres situés juste avant cet opérateur:$$\underbrace{12\quad 2\quad /}_{12/2 = 6}\quad 4\quad -\quad 5\quad 3\quad \times\quad +$$

on remplace cette opération par le résultat:$$6\quad 4\quad -\quad 5\quad 3\quad \times\quad +$$

on continue la lecture de l'expression:$$\underbrace{6\quad 4\quad -}_{6-4=2}\quad 5\quad 3\quad \times\quad + \quad\text{devient}\quad 2\quad \underbrace{5\quad 3\quad \times}_{5\times 3=15}\quad + \quad\text{devient } 2\quad 15\quad + \text{ qui vaut } 17.$$

On utilisera une liste de symboles pour écrire la notation polonaise inversée d'une expression mathématique. Par exemple, $6\ 2\ 3\ +\ \times\ 94\ 1\ -\ +$ sera représentée par la liste: [6, 2, 3, +, x, 94, 1, -, +].

On considère à présent l'algorithme ci-dessous, écrit en pseudo-code, qui reçoit une liste de symboles correspondant à la notation polonaise inversée d'une expression et renvoie l'arbre binaire associé.

Algorithme créer_arbre(liste_symboles)

P ← créer une pile vide

pour chaque élément de liste_symboles:

si élément est un entier:

a ← construire l'arbre de racine élément et n'ayant pas de sous-arbre droit ni gauche

sinon: # élément est le symbole d'un opérateur

a_droit ← dépiler P

a_gauche ← dépiler P

a ← construire l'arbre de racine élément,

ayant pour sous-arbre gauche a_gauche et pour sous-arbre droit a_droit

empiler a dans P.

a ← dépiler P

renvoyer a

L'algorithme précédent nécessite l'utilisation d'une pile, dont les éléments sont des arbres.

On précise que:

l'action empiler a dans P insère l'élément a en haut de la pile P;

l'action dépiler P renvoie la valeur de l'élément en haut de la pile P et le supprime de la pile.

2.

On donne l'arbre binaire suivant:

Indiquer, parmi les quatre différents parcours d'arbre ci-dessous celui qui permet d'obtenir la succession des symboles correspondant à la notation NPI suivante:

20 11 3 + 5 2 + / −

3.c.

Dessiner l'arbre binaire représentant l'expression mathématique dont la notation polonaise inversée est la liste [6, 2, 3, +, x, 94, 1, -, +].

4.

On souhaite écrire une fonction en langage Python qui permet d'évaluer une expression mathématique écrite avec la notation polonaise inversée NPI. On suppose qu'une telle expression est représentée par un arbre binaire obtenu à l'aide de l'algorithme précédent.

On dispose pour cela de quatre fonctions:

est_vide(arb) qui renvoie True si l'arbre binaire arb est vide, False sinon;

racine(arb) qui renvoie la valeur de la racine de l'arbre binaire arb;

gauche(arb) qui renvoie le sous-arbre gauche de l'arbre binaire arb;

droit(arb) qui renvoie le sous-arbre droit de l'arbre binaire arb.

La fonction evaluer donnée ci-dessous est écrite en Python. Cette fonction prend en paramètre un arbre binaire arb représentant une expression mathématique écrite en NPI et renvoie la valeur de cette expression.

def evaluer(arb):

if est_vide(gauche(arb)) and à compléter (instruction 1):

res = à compléter (instruction 2)

elif à compléter (instruction 2) == "+":

res = evaluer(à compléter (instruction 3)) + à compléter (instruction 4)

elif à compléter (instruction 2) == "-":

res = evaluer(à compléter (instruction 3)) - à compléter (instruction 4)

elif à compléter (instruction 2) == "*":

res = evaluer(à compléter (instruction 3)) * à compléter (instruction 4)

else:

res = evaluer(à compléter (instruction 3)) / à compléter (instruction 4)

return res

Quatre instructions seulement permettent de compléter ce code: instruction 1, instruction 2, instruction 3 et instruction 4.

Écrire le code de chacune de ces quatre instructions.