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

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 :

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>>>>.

Une approche récursive semble convenir parfaitement.

Test

Vérifiez que l'évaluation de :

Aller plus loin