Table des matières
Arbre de calcul
Lorsque l'on écrit un calcul comme $7 \times 6 + 4 \times (15 + 2)$, l'exécution des différents opérateurs se fait dans un ordre bien déterminé qui n'est pas a priori évident.
Arbre représentant l'expression
On peut créer un arbre dont les nœuds sont les nombres ou les opérateurs.
Notre but est de produire cet arbre.
Découpage avec une expression régulière
On souhaite découper l'expression de départ en ses constituants de base.
"7 * 6 + 4 *(15+2)" → [7, '*', 6, '+', 4, '*', '(', 15, '+', 2, ')'].
Ce travail est très rapide si on connaît les expressions régulières, ce qui (normalement) n'est pas votre cas. Je vous présente donc un exemple.
Exemple
Supposons que je veuille reconnaître les morceaux de l'écriture d'une formule chimique. L'écriture sera de la forme, par exemple H2O ou H3O+ ou CuB7C15Na3 ou encore – formule qui n'existe pas – ABe4K8. Imaginons que l'on puisse aussi écrire molécule:432 et qu'il faille pouvoir le reconnaître.
Pour le premier cas, il s'agit de découper en morceaux qui :
- commencent par exactement une lettre majuscule :
[A-Z] - suivis de lettres en minuscules :
[a-z]*–*signifie de 0 à plusieurs - suivis de chiffres :
[0-9]* - éventuellement suivi de
+:\+?–?signifie 0 ou 1 fois, comme+a un usage spécial dans les expressions régulières;\+permet de signaler que l'on veut+en tant que caractère.
Ce qui donne [A-Z][a-z]*[0-9]*\+?
Pour le second cas, il s'agit de reconnaître :
- l'apparition du mot “molécule:” :
molécule: - suivi d'un nombre :
[0-9]+–+signifie au moins 1 fois.
Le second cas donne molécule:[0-9]+
Puisque c'est soit l'un, soit l'autre, on ajoute entre les deux un symbole de OU : |.
Et voilà notre expression régulière complète : r"([A-Z][a-z]*[0-9]*\+?)|(molécule:[0-9]+)"
>>> import re # module d'expression régulière
>>> regex = r"([A-Z][a-z]*[0-9]*\+?)|(molécule:[0-9]+)"
>>> re.findall(regex, "CuB7C15Na3")
[('Cu', ''), ('B7', ''), ('C15', ''), ('Na3', '')]
>>> re.findall(regex, "molécule:723")
[('', 'molécule:723')]
Il est possible de faire un peu mieux en faisant bonne usage des parenthèses :
>>> import re # module d'expression régulière
>>> regex = r"(([A-Z][a-z]*)([0-9]*)\+?)|(molécule:([0-9]+))"
>>> re.findall(regex, "CuB7C15Na3")
[('Cu', 'Cu', '', '', ''), ('B7', 'B', '7', '', ''), ('C15', 'C', '15', '', ''), ('Na3', 'Na', '3', '', '')]
>>> re.findall(regex, "molécule:723")
[('', '', '', 'molécule:723', '723')]
Pour chaque tuple réponse, on trouve un item correspondant à une paire de parenthèse. Le découpage est ensuite très simple.
Produire l'arbre
Je vous propose une méthode pour produire l'arbre à partir de la liste représentant l'expression. Cette méthode n'est pas très performante. Elle a l'avantage d'être simple à comprendre. Je vous en donnerai une autre plus loin, plus efficace mais moins simple.
Construction par ordre de priorité
Partons du découpage : [7, '*', 6, '+', 4, '*', '(', 15, '+', 2, ')'].
Transformation sous une autre forme
Un premier traitement consisterait à parcourir cette liste et à en transformer chaque élément en un nœud d'arbre. Je vais le noter ainsi : [<7>, <*>, <6>, <+>, <4>, <*>, <(>, <15>, <+>, <2>, <)>]
Prise en compte des parenthèses
La présence de parenthèses indiquent un niveau de priorité augmenté. Les parenthèse ne servent qu'à cela. On pourrait donc transformer notre tableau sous cette forme [<7>, <*>, <6>, <+>, <4>, <*>, <15>, <+>+, <2>], les + représentent le surcroît de priorité accordé par les ( ). Les parenthèses ayant été pris en compte, on a pu les supprimer.
Notez que seuls les opérateurs ont une priorité, les nombres n'ont pas à être priorisés.
Sélection de l'opérateur de priorité maximale
- L'opérateur de priorité maximale, tenant compte du surcroît accordé par les parenthèses, est le
<+>+en avant dernière position. - Puisqu'il est prioritaire, on l'exécute en premier en le faisant agir sur ses deux voisins.
- On obtient donc un nœud que l'on pourrait écrire
<+, <15>, <2». - Le tableau devient :
[<7>, <*>, <6>, <+>, <4>, <*>, <+, <15>, <2>>]
Notez que maintenant <+, 15, 2> est un simple nombre. Ce n'est plus un opérateur.
Répétition...
Si on répète l'opération on obtient :
- sélection du premier
<*>:[<*, <7>, <6>>, <+>, <4>, <*>, <+, <15>, <2>>] - sélection du second
<*>:[<*, <7>, <6>>, <+>, <*, <4>, <+, <15>, <2>>>] - sélection du
<+>:[<+, <*, <7>, <6>>, <*, <4>, <+, <15>, <2>>>>]
Fin de la boucle
Quand il ne reste plus qu'un élément dans la liste, c'est que la construction de l'arbre est terminée. Il suffit de récupérer le dernier élément de la liste.
Dans l'exemple : <+, <*, <7>, <6>>, <*, <4>, <+, <15>, <2>>>>
Évaluer l'expression
On souhaite pouvoir évaluer une expression transformée en arbre.
Exemple : évaluation de <+, <*, <7>, <6>>, <*, <4>, <+, <15>, <2>>>>.
- Le nœud racine est un
+. - Il faut évaluer le sous arbre gauche :
<*, <7>, <6>> - évaluer le sous arbre droite :
<*, <4>, <+, <15>, <2>>> - faire la somme.
Une approche récursive semble convenir parfaitement.
Test
Vérifiez que l'évaluation de :
- “7 * 6 + 4 *(15+2)” renvoie bien 110
- “(12 - 6) * 3 - 4 + 2 *(2 + 3 *(5 - 1)*6 - 8) - 2 * 11” renvoie bien 124
Aller plus loin
- Ajouter des opérateurs
- Permettre des calculs sur les flottants
- Reconnaître des constantes comme $\pi$
- Autoriser l'écriture d'un symbole comme $x$ qu'il faudrait fournir au moment de l'évaluation.
- Prendre en charge correctement d'éventuelles erreurs d'expression