Aller au contenu

Expression parenthésée⚓︎

Une expression arithmétique ne comportant que les quatre opérations \(+, - , ×, ÷\) peut être représentée sous forme d'arbre. La disposition des nœuds indique les priorités opératoires.

  • Les feuilles représentent des nombres, elles ne possèdent pas de sous-arbre.
  • Les nœuds internes représentent des opérateurs binaires, ils possèdent exactement deux sous arbres.

Par exemple, avec un parcours en profondeur infixe de l'arbre ci-dessous, on peut retrouver l'expression notée habituellement : \(((3 × (8 + 7)) - (2 + 1))\).

arbre

La classe Noeud ci-après met en œuvre une structure d'arbre adaptée.

Il n'agit pas exactement d'un arbre binaire

Avec un arbre binaire, tous les nœuds ont exactement deux sous-arbres. Un sous arbre peut alors être vide.

Ici, il s'agit d'un arbre d'expression pour opérateurs binaires. C'est un arbre d'arité 2 ; il n'y a pas, ici, de notion d'arbre vide. Ici, chaque nœud possède 0 ou 2 sous-arbre.

Compléter la fonction récursive expression_parenthesee qui prend en paramètre un objet de la classe Noeud qui désigne la racine d'un arbre et qui renvoie l'expression arithmétique représentée par l'arbre passé en paramètre, sous forme d'une chaine de caractères contenant des parenthèses.

Exemple

Résultat attendu avec l'arbre ci-dessus :

🐍 Console Python
>>> somme_1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))
>>> somme_2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))
>>> produit_1 = Noeud(Noeud(None, 3, None), '*', somme_1)
>>> expression = Noeud(produit_1, '-', somme_2)
>>> expression_parenthesee(expression)
'((3*(8+7))-(2+1))'

D'autres exemples

🐍 Console Python
>>> feuille = Noeud(None, 5, None)
>>> expression_parenthesee(feuille)
'5'
🐍 Console Python
>>> somme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))
>>> expression_parenthesee(somme)
'(2+3)'
🐍 Console Python
>>> somme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))
>>> produit = Noeud(Noeud(None, 4, None), '*', somme)
>>> expression_parenthesee(produit)
'(4*(2+3))'
# testsbksl-nlnombre = Noeud(None, 5, None)bksl-nlassert expressionpy-undparenthesee(nombre) == '5'bksl-nlbksl-nlsomme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))bksl-nlassert expressionpy-undparenthesee(somme) == '(2+3)'bksl-nlbksl-nlproduit = Noeud(Noeud(None, 4, None), 'py-str', somme)bksl-nlassert expressionpy-undparenthesee(produit) == '(4py-str(2+3))'bksl-nlbksl-nlsommepy-und1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))bksl-nlsommepy-und2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))bksl-nlproduitpy-und1 = Noeud(Noeud(None, 3, None), 'py-str', sommepy-und1)bksl-nlexpression = Noeud(produitpy-und1, '-', sommepy-und2)bksl-nlbksl-nlassert expressionpy-undparenthesee(expression) == '((3py-str(8+7))-(2+1))'bksl-nlbksl-nlbksl-nlbksl-nl# autres testsbksl-nlbksl-nlnombre = Noeud(None, 42, None)bksl-nlassert expressionpy-undparenthesee(nombre) == '42'bksl-nlbksl-nlsomme = Noeud(Noeud(None, 1, None), '+', Noeud(None, 2, None))bksl-nlassert expressionpy-undparenthesee(somme) == '(1+2)'bksl-nlbksl-nlquotient = Noeud(Noeud(None, 3, None), '/', somme)bksl-nlassert expressionpy-undparenthesee(quotient) == '(3/(1+2))'bksl-nlbksl-nlbksl-nl ∞/∞

class Noeud:bksl-nl """bksl-nl Classe pour un nœud d'arbre disposant de 3 attributs :bksl-nl - gauche : le sous-arbre à gauche.bksl-nl - valeur : la valeur portée par le nœud,bksl-nl - droite : le sous-arbre à droite.bksl-nl """bksl-nlbksl-nl def py-undpy-undinitpy-undpy-und(self, gauche, valeur, droite):bksl-nl self.gauche = gauchebksl-nl self.valeur = valeurbksl-nl self.droite = droitebksl-nl bksl-nl def estpy-undfeuille(self):bksl-nl """Renvoie un booléen : le nœud est-il une feuille ?"""bksl-nl return self.gauche is None and self.droite is Nonebksl-nlbksl-nlbksl-nldef expressionpy-undparenthesee(e):bksl-nl if e.estpy-undfeuille():bksl-nl return str(...)bksl-nl else:bksl-nl return '(' + expressionpy-undparenthesee(...) + ...bksl-nlbksl-nlbksl-nlbksl-nl# testsbksl-nlfeuille = Noeud(None, 5, None)bksl-nlassert expressionpy-undparenthesee(feuille) == '5'bksl-nlbksl-nlsomme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))bksl-nlassert expressionpy-undparenthesee(somme) == '(2+3)'bksl-nlbksl-nlproduit = Noeud(Noeud(None, 4, None), 'py-str', somme)bksl-nlassert expressionpy-undparenthesee(produit) == '(4py-str(2+3))'bksl-nlbksl-nlsommepy-und1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))bksl-nlsommepy-und2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))bksl-nlproduitpy-und1 = Noeud(Noeud(None, 3, None), 'py-str', sommepy-und1)bksl-nlexpression = Noeud(produitpy-und1, '-', sommepy-und2)bksl-nlbksl-nlassert expressionpy-undparenthesee(expression) == '((3py-str(8+7))-(2+1))'bksl-nlbksl-nlclass Noeud:bksl-nl """bksl-nl Classe implémentant un nœud disposant de 3 attributs :bksl-nl - valeur : la valeur de l'étiquette,bksl-nl - gauche : le sous-arbre à gauche.bksl-nl - droite : le sous-arbre à droite.bksl-nl bksl-nl Ce n'est pas, ici, pour un arbre binaire, mais pour un arbre d'arité 2.bksl-nl """bksl-nl def py-undpy-undinitpy-undpy-und(self, gauche, valeur, droite):bksl-nl self.gauche = gauchebksl-nl self.valeur = valeurbksl-nl self.droite = droitebksl-nl bksl-nl def estpy-undfeuille(self):bksl-nl "Renvoie un booléen, la réponse à : le nœud est-il une feuille ?"bksl-nl return self.gauche is None and self.droite is Nonebksl-nlbksl-nlbksl-nldef expressionpy-undparenthesee(e):bksl-nl if e.estpy-undfeuille():bksl-nl return str(e.valeur)bksl-nl else:bksl-nl return (bksl-nl '('bksl-nl + expressionpy-undparenthesee(e.gauche)bksl-nl + e.valeurbksl-nl + expressionpy-undparenthesee(e.droite)bksl-nl + ')'bksl-nl )bksl-nlbksl-nlbksl-nl# testsbksl-nlbksl-nlfeuille = Noeud(None, 5, None)bksl-nlassert expressionpy-undparenthesee(feuille) == '5'bksl-nlbksl-nlsomme = Noeud(Noeud(None, 2, None), '+', Noeud(None, 3, None))bksl-nlassert expressionpy-undparenthesee(somme) == '(2+3)'bksl-nlbksl-nlproduit = Noeud(Noeud(None, 4, None), 'py-str', somme)bksl-nlassert expressionpy-undparenthesee(produit) == '(4py-str(2+3))'bksl-nlbksl-nlsommepy-und1 = Noeud(Noeud(None, 8, None), '+', Noeud(None, 7, None))bksl-nlsommepy-und2 = Noeud(Noeud(None, 2, None), '+', Noeud(None, 1, None))bksl-nlproduitpy-und1 = Noeud(Noeud(None, 3, None), 'py-str', sommepy-und1)bksl-nlexpression = Noeud(produitpy-und1, '-', sommepy-und2)bksl-nlbksl-nlassert expressionpy-undparenthesee(expression) == '((3py-str(8+7))-(2+1))'bksl-nlbksl-nlbksl-nl

A

Commentaires⚓︎

{{ IDE('exo_corr') }}

Si e est une feuille, on souhaite renvoyer la valeur sans parenthèse, donc on renvoie str(e.valeur) une chaine de caractères.

Sinon, on concatène du texte avec l'opérateur + :

  • Une parenthèse ouvrante.
  • L'expression parenthésée du sous-arbre à gauche : e.gauche
  • L'opérateur sous forme de texte.
  • L'expression parenthésée du sous-arbre à droite : e.droite
  • Une parenthèse fermante.

Z

Retour en haut de la page