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

{{ :nsi:tds:arbre_calcul.png?direct&200 |}}

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.

<WRAP box>**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]+)"%%''

<code python>
>>> 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')]
</code>

Il est possible de faire un peu mieux en faisant bonne usage des parenthèses :

<code python>
>>> 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')]
</code>
Pour chaque tuple réponse, on trouve un item correspondant à une paire de parenthèse. Le découpage est ensuite très simple.
</WRAP>

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

<wrap tip>Notez que seuls les opérateurs ont une priorité, les nombres n'ont pas à être priorisés.</wrap>

=== 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>>]%%''

<wrap tip>Notez que maintenant ''<+, 15, 2>'' est un simple nombre. Ce n'est plus un opérateur.</wrap>

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