Les arbres binaires

Évaluation d'une expression arithmétique

Nous convenons d'appeler "expression arithmétique" toute chaîne de caractères construite à partir de la liste des symboles 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, *, /, (, ).

Les expressions considérées ne mettront en jeu que des entiers relatifs.

Certaines expressions sont incorrectes comme "2+" (que nous pouvons toutefois interpréter comme "2+0" ) ou "3x(6+4". Nous supposerons dans ce qui suit que les expressions sont correctes.

Une expression arithmétique peut être représentée par un arbre binaire.

La structure d'arbre binaire

L'arbre est dit binaire car chaque noeud "opérateur" possède deux fils : un fils gauche et un fils droit. Un noeud "opérateur" est un noeud qui contient un des symboles "+, -, * ou / ". Un noeud fils est soit un noeud opérateur, soit un noeud opérande - un entier - (c'est alors une feuille de l'arbre car il n'a pas de fils). La tête de l'arbre est toujours un noeud opérateur sauf dans le cas trivial où l'expression est réduite à un entier.

exemple : 3+(5*((-2)*6*8/4-4/2*6/3/2)*7)

Voici le dessin de l'arbre binaire correspondant à cette expression :

On constate que pour le nombre " - 2 ", tout en bas de l'arbre, à gauche, on n'a pas de fils droit. Dans ce cas on dit que le signe "-" (ce signe "-" bien précis) est un opérateur unaire, puisqu'il n'a qu'un fils. Cette notion d'opérateur unaire est applicable aussi pour les parenthèses, parce qu'elles n'ont qu'un fils au lieu de deux, comme devrait avoir tout noeud d'un arbre binaire. Il faut noter que par rapport au signe "-", la parenthèse ouvrante peut aussi bien avoir un fils gauche avec son contenu, qu'un fils droit. Ici, dans ce dessin, nous avons choisi délibérément le fils gauche, pour la distinguer du signe "-", qui, lui, a obligatoirement le fils à droite.

Ensuite, pour construire l'arbre, il faut faire attention au sens de lecture de l'expression.

ex. 3 : 8-4-4

On voit dans cet exemple que l'expression doit être lue de droite à gauche. Lue de gauche à droite, l'expression conduirait à l'arbre de droite dont le résultat est manifestement faux car égal à 8.

Voici la déclaration sous Delphi (pascal objet) de la structure utilisée :

Noeud = class
private
 op: char; //le genre du noeud : +, -, *, /, ou "c" s'il s'agit d'une feuille
 valeur: integer; //dans le cas d'une feuille, sa valeur entière
 FilsGauche, FilsDroit: Noeud;
public
 constructor create;
 destructor destroy;
end; { Noeud }
 
Arbre = class
private
 tete, courant: noeud;
public
 constructor create;
 destructor destroy; override;
 procedure Remplit(s: string);
 function evalue(n: noeud): integer;
end; {arbre}
 

Vous noterez que la procédure suivante, permettant de détruire un noeud, est récursive :

destructor noeud.destroy;
begin
 if FilsGauche <> nil then FilsGauche.destroy;
 if FilsDroit <> nil then FilsDroit.destroy;
 inherited destroy;
end;
 

En effet, FilsGauche.Destroy provoque un appel à noeud.destroy puisque FilsGauche est un noeud ! D'où le test "if FilsGauche<>nil...".

Comment évaluer un arbre binaire

Pour évaluer le résultat d'un arbre, on applique tout simplement la formule suivante :

- si le noeud à évaluer contient un entier, le résultat est égal à cet entier.

- sinon, le résultat est égal à :

"evalue(FilsGauche) opération evalue(FilsDroit) ", où "opération" désigne l'un des quatre opérateurs usuels.

La procédure permettant d'évaluer le résultat de l'expression est la procédure récursive suivante :

function arbre.evalue(n: noeud): integer; //récursive, évidemment
begin
 if n.op = 'c' then // c'est une feuille "chiffre"
 evalue := n.valeur
 else
 begin // noeud opérateur
 case n.op of
 '+': evalue := evalue(n.FilsGauche) + evalue(n.FilsDroit);
 '-': evalue := evalue(n.FilsGauche) - evalue(n.FilsDroit);
 '*': evalue := evalue(n.FilsGauche) * evalue(n.FilsDroit);
 '/': evalue := evalue(n.FilsGauche) div evalue(n.FilsDroit);
 end;
 end;
end;
 

Un exemple d'appel de cette procédure est : UnArbre.Evalue(UnArbre.tete).

Comment construire l'arbre binaire

Le travail le plus délicat ici n'est pas l'évaluation de l'arbre, mais la façon de le remplir à partir de la chaîne de caractères qui représente l'expression à évaluer.

C'est ce qu'on appelle la construction d'un arbre d'analyse par descente récursive.

Traitons pour commencer le cas où l'expression considérée ne comporte que des additions et des soustractions (et aucune parenthèse).

L'appel initial de la procédure "Remplit" reçoit l'expression entière comme paramètre.

Le principe de la procédure est que eval(a±b±c)=eval(a±b) ± c.

Pour cette expression, « a±b » est appelé "gauche" et "c" est appelé "droite". Nous nous ramenons toujours ainsi à l'évaluation de deux sous-expressions dont l'une est triviale (celle de droite, qui constitue une feuille de l'arbre).

Nous commençons par initialiser gauche à vide car gauche ne sera pas nécessairement affecté par la première partie de la procédure : en effet si on veut construire l'arbre de "-2" la partie gauche n'est pas initialisée.

Ensuite nous cherchons le premier signe "+" ou "-" en lisant l'expression de droite à gauche. Si nous n'en trouvons pas, c'est que l'expression est réduite à un entier et nous avons fini (condition de sortie de la récursion).

Sinon, nous coupons l'expression en deux (gauche et droite, de part et d'autre de l'opérateur trouvé), nous affectons au noeud courant le symbole opérateur trouvé et nous affectons à "droite" la valeur de l'entier isolé à droite, ce qui nous permet de remplir le fils droit du noeud opérateur de l'arbre dont nous étions partis.

Nous créons ensuite le fils gauche à partir de "gauche".

S'il est réduit à un entier, c'est fini (condition de sortie de la récursion).

S'il contient encore au moins un opérateur, il nous suffit de rappeler récursivement la procédure Remplit en lui passant "gauche" comme paramètre. Nous prenons au préalable la précaution de fixer le noeud courant au fils gauche actuel pour que le remplissage de l'arbre se poursuive au bon endroit.

Vous noterez que cette méthode permet d'évaluer certaines expressions "irrégulières" comme : +2+3, vide, 89, 5+97-, 78++5 ou "+".

C'est pour cette raison que nous introduirons la notion d'automate, après la procédure de création de l'arbre binaire, pour vérifier si une expression mathématique est correcte d'un point de vue syntaxique.

Mais voici d'abord une première version de la création d'un arbre :

procedure arbre.Remplit(s: string); //récursive !!!
var p, pp, pm: integer;
 gauche, droite: string;
begin
 //pour une expression du type a ± b ± c
 gauche := '';
 p := length(s);
 while (p > 0) and (s[p] <> '+') and (s[p] <> '-') do dec(p);
 if p > 0 then //il y a bien un "+" ou un "-" donc on a un arbre binaire
 begin
 gauche := copy(s, 1, p - 1);
 droite := copy(s, p + 1, length(s));
 courant.op := s[p]; //la tête, lors du premier appel
 courant.FilsDroit := noeud.create;
 courant.FilsDroit.op := 'c'; // c pour "chiffre"
 if droite <> '' then
 courant.FilsDroit.valeur := StrToInt(droite)
 else
 courant.FilsDroit.valeur := 0;
 end
 else //il n'y a pas/plus de "+" ni de "-", donc il reste un entier
 begin
 courant.op := 'c'; // c pour "chiffre"
 if s <> '' then
 courant.valeur := StrToInt(s)
 else
 courant.valeur := 0;
 exit;
 end;
 //créons le fils gauche
 courant.FilsGauche := noeud.create;
 if gauche <> '' then
 begin
 p := length(s);
 while (p > 0) and (s[p] <> '+') and (s[p] <> '-') do dec(p);
 if p > 0 then
 begin
 courant := courant.FilsGauche;
 Remplit(gauche); //il faut continuer --->>> APPEL RÉCURSIF
 end
 else //c'est fini
 begin
 courant.FilsGauche.op := 'c'; // c pour "chiffre"
 courant.FilsGauche.valeur := StrToInt(gauche);
 exit;
 end;
 end
 else //on met un zéro
 begin
 courant.FilsGauche.op := 'c'; // c pour "chiffre"
 courant.FilsGauche.valeur := 0;
 end;
end;
 

Nous allons maintenant modifier progressivement cette procédure pour arriver à la création d'un arbre binaire d'une expression contenant des parenthèses.

Tout d'abord nous allons créer une fonction "nb_elems" qui va recevoir comme paramètre une expression saisie au clavier, et qui va nous dire si cette expression contient un ou plusieurs éléments; si elle contient plusieurs éléments alors on va renvoyer comme réponse le nombre 2; on utilise cette valeur car un arbre binaire a deux fils au maximum; ainsi, comme nous l'avons vu précédemment, pour l'expression "2+3 - 5" on a l'arbre constitué des branches "2+3" et "5".

Cette fonction renvoie aussi la partie gauche et la partie droite d'une expression, d'où l'utilisation du mot "var g,d : string" dans les paramètres de la fonction.

Et elle renvoie aussi le signe qui est au sommet de l'arbre binaire (dans le cas des branches "2+3" et "5", le signe du sommet sera " - " ).

Nous devons transmettre aussi les séparateurs : " + " et " - " ensemble, ou bien " * " et " / " ensemble, car ce sont eux qui vont nous aider à délimiter la partie gauche de la partie droite.

Sachant que par la suite nous allons avoir des parenthèses, nous allons les prendre en compte dès maintenant en utilisant un compteur "nb" qui sera incrémenté chaque fois qu'on rencontrera une fermante (ne pas oublier que le sens de la lecture se fait de la droite vers la gauche, donc la première parenthèse susceptible d'être rencontrée sera fermante) et décrémenté chaque fois qu'on rencontrera une ouvrante.

function nb_elems(s: string; var g, d: string; s1, s2: char; var sig: char): integer;
var trouve: boolean;
 p, nb: integer;
begin // on extrait la partie gauche et droite, séparées par s1 ou s2
 p := length(s) + 1; nb := 0; // en faisant attention aux parenthèses, s'il y en a
 repeat
 dec(p);
 if s[p] = '(' then dec(nb);
 if s[p] = ')' then inc(nb);
 trouve := (nb = 0) and ((s[p] = s1) or (s[p] = s2));
 until (p = 1) or (trouve);
 if p > 1 then // deux ou plusieurs elements; mais dans un arbre binaire il y en a 2
 begin
 d := copy(s, p + 1, length(s));
 g := copy(s, 1, p - 1);
 sig := s[p];
 nb_elems := 2;
 end
 else // un seul élément
 begin
 d := s;
 g := '';
 sig := #0;
 nb_elems := 1;
 end;
end;

Notre procédure initiale devient donc la procédure "traiter_sans_parentheses" qui va recevoir comme paramètres un noeud, l'expression saisie et les deux signes séparateurs (" +, - " ou bien " *, / ").

Supposons que notre expression contient une expression avec les quatre signes; au début les séparateurs sont les signes " + " et " - ".

Nous allons distinguer les deux cas, celui où on a deux éléments et celui où on n'en a qu'un :

- si on a deux fils, alors :

- on crée le fils droit, on fait un appel récursif avec la nouvelle expression constitué de la partie droite et les deux nouveaux séparateurs " * " et " / ".

- on met le signe qui séparait la partie droite de la gauche dans le nœud

- on crée le fils gauche et on fait un appel récursif avec la nouvelle expression constituée de la partie gauche

- si on a un seul fils, alors :

- ou bien les séparateurs initiaux étaient "+" et " - ", auquel cas on fait un appel récursif avec les séparateurs "*" et "/".

- ou bien c'est un entier seul et on le met dans le noeud.

Voici donc cette procédure programmée, qu'on peut appeler avec l'instruction suivante :

"traiter_sans_parentheses(noeud1,expression,'+','-',gauche,droite,signe)"

procedure traiter_sans_parentheses(courant: noeud; s: string; signe1, signe2: char);
var g2, d2: string;
 sig2: char;
begin
 if nb_elems(s, g2, d2, signe1, signe2, sig2) = 2 then // deux termes ou plus
 begin
 courant.FilsDroit := noeud.create;
 traiter_sans_parentheses(courant.FilsDroit, d2, '*', '/');
 courant.op := sig2;
 courant.FilsGauche := noeud.create;
 traiter_sans_parentheses(courant.FilsDroit, g2, signe1, signe2);
 end
 else
 if nb_elems(s, g2, d2, '*', '/', sig2) = 2 then
 traiter_sans_parentheses(courant, s, '*', '/')
 else
 begin
 courant.op := 'c'; // c pour "chiffre"
 courant.valeur := strToInt(s);
 end;
end;
 

Les deux procédures ci-dessus vont se trouver dans notre nouvelle procédure "remplit", qui va traiter une expression contenant des parenthèses. Vous remarquerez que le corps de cette procédure est presque identique à celui de la procédure "traiter_sans_parentheses"; en effet on doit distinguer et traiter les deux cas possibles : un terme ou deux termes.

Si on a deux termes (par rapport aux signes en cours "+ -" ou " x / ", alors on les sépare et on fait un appel récursif.

Si on n'a qu'un seul terme, on doit distinguer les trois cas suivants :

- ou bien on a un seul terme par rapport à "+ -", auquel cas on fait un appel récursif avec " x / ".

- ou bien on a une seule parenthèse, auquel cas on fait un appel récursif avec l'intérieur de la parenthèse

- ou bien on a un seul nombre

procedure arbre.Remplit(courant: noeud; s: string; signe1, signe2: char);
var g1, d1: string;
 sig1: char;
 
 function nb_elems(s: string; var g, d: string; s1, s2: char;
 var sig: char): integer;
 begin.... end;
 
 procedure traiter_sans_parentheses(courant: noeud; s: string;
 signe1, signe2: char);
 begin.... end;
 
begin
 if nb_elems(s, g1, d1, signe1, signe2, sig1) = 2 then // deux termes ou plus
 begin
 courant.FilsDroit := noeud.create;
 remplit(courant.FilsDroit, d1, '*', '/');
 courant.op := sig1;
 courant.FilsGauche := noeud.create;
 remplit(courant.FilsGauche, g1, signe1, signe2);
 end
 else // un seul terme
 if nb_elems(s, g1, d1, '*', '/', sig1) = 2 then // un terme pour l'addition mais
 remplit(courant, s, '*', '/') // plusieurs pour la multiplication : 2*3*(-5)
 else
 if d1[1] = '(' then // ou bien une seule parenthèse, ex : (2+3)
 begin
 courant.op := '(';
 courant.FilsDroit := noeud.create;
 d1 := copy(d1, 2, length(d1) - 2); // on supprime les parenthèses
 Remplit(courant.FilsDroit, d1, '+', '-')
 end
 else // ou bien un seul nombre
 traiter_sans_parentheses(courant, d1, '+', '-');
end;
 

La fonction d'évaluation de l'arbre binaire devient donc :

function arbre.evalue(n: noeud): integer; //récursive, évidemment ;-)
begin
 if n = nil then evalue := 0 else
 if n.op = 'c' then // c'est une feuille "chiffre"
 evalue := n.valeur
 else begin // noeud opérateur
 case n.op of
 '(': evalue := evalue(n.FilsDroit);
 '+': evalue := evalue(n.FilsGauche) + evalue(n.FilsDroit);
 '-': evalue := evalue(n.FilsGauche) - evalue(n.FilsDroit);
 '*': evalue := evalue(n.FilsGauche) * evalue(n.FilsDroit);
  '/': evalue := evalue(n.FilsGauche) div evalue(n.FilsDroit);
 end;
 end;
end;
 

Nous allons voir maintenant comment on construit un automate permettant de vérifier qu'une expression saisie au clavier est correcte d'un point de vue syntaxique.

Automate de validation d'une expression arithmétique

Avant de soumettre une expression à notre calculette, nous devons en vérifier la validité (parenthèses correctement placées et pas d’erreurs syntaxiques).

Pour cela, nous allons utiliser un automate. En voici le schéma :

On va de l'état "1" à l'état "2" par un signe "+" ou "-".

Ce schéma comporte des cellules circulaires appelées états et des flèches appelées arcs ou transitions. Au dessus de chaque flèche se trouve une étiquette indiquant quels sont les caractères qui provoquent la transition.

L'état 1 est appelé "état initial" et il est identifiable par une flèche entrante.

Les états 3 et 4 sont appelés "états terminaux" et sont identifiables par une croix (ou un "+") placée à côté.

L’automate s’utilise en lui passant un par un, dans le sens de lecture naturel (de gauche à droite), les caractères qui constituent la chaîne à valider.

Certains états présentent des transitions sous forme de boucles, indiquant qu’on peut rester dans le même état en examinant deux caractères consécutifs : on va de l'état "1" à l'état "1" par "(" : cela indique qu'on peut avoir plusieurs parenthèses ouvrantes d'affilée : "((".

Appliquons cet automate pour voir si l’expression « 1+2 » est correcte.

Le premier caractère de l’expression est « 1 ». Nous soumettons ce caractère à l’automate qui se trouve alors dans l’état 1. Le chiffre "1" étant un entier entre 0 et 9, nous suivons la transition correspondante qui amène l’automate dans l’état 3.

Le caractère suivant est « + ». L’automate passe dans l’état 5.

Le dernier caractère est « 2 ». L’automate passe dans l’état 3.

C’est un état terminal, l’expression envisagée était donc correcte.

Si l’expression avait été « 1+ », nous serions resté dans l’état 5, qui n’est pas terminal, et l’expression aurait donc été jugée incorrecte.

Si l’expression avait été « 1+/ », nous n’aurions pu aller nulle part depuis l’état 5 (il n’y a aucune transition possible depuis l’état 5 avec le caractère « / ») et l’expression aurait également été jugée incorrecte.

Une expression est donc incorrecte dans deux cas :

elle laisse finalement l’automate dans un état non terminal

elle comporte un caractère qui, dans un état donné, ne provoque aucune transition.

Pour représenter l’automate, nous utilisons un tableau à deux dimensions :

const etats = 5; // nombre d'états de l'automate
 caracs = 16; // 16 caractères autorisés pour la saisie
 st = '0123456789+-*/()'; // les 16 caractères
 tab: array[1..etats, 1..caracs] of integer =
 //0 1 2 3 4 5 6 7 8 9 + - * / ( )
 ((3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 0, 0, 1, 0), {etat 1}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0), {etat 2}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 0, 4), {etat 3}
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 0, 4), {etat 4}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0)); {etat 5}
 

Chaque case du tableau indique quel état est amené par la transition provoquée par le caractère en cours en partant de l’état courant :

etat :=tableau[etat,caractere];

Si, par exemple, l’automate se trouve dans l'état 2 (ligne 2 du tableau) et qu'on lit une parenthèse ouvrante, alors l’automate passe dans l'état 1 (donc, pour le prochain caractère on lira dans la ligne 1 du tableau). Si l’automate se trouve dans l'état 1 et qu’on lit un « / », alors l’automate passe dans l'état 0 (il y a une erreur) et on s'arrête.

Les zéros indiquent qu’un caractère donné ne provoque aucune transition à partir d’un état donné (impasse).

Il ne nous reste plus qu’à soumettre à notre automate l’expression à valider, caractère par caractère.

Label1.Caption:=Automate(Edit1.Text);

Si, à un moment quelconque de l'analyse de notre expression mathématique, etat=0, alors nous sommes dans une impasse, et l’expression est donc incorrecte.

Si, à la fin, l’automate ne se trouve pas dans l’état 3 ou l’état 4 (les seuls états terminaux), l’expression est incorrecte.

Nous avons ajouté une variable « equilibre », chargée de mesurer la différence entre le nombre de parenthèses ouvrantes et le nombre de parenthèses fermantes.

En effet, on démontre mathématiquement qu'un automate du type de celui que nous utilisons n'est pas capable de reconnaître les fautes de parenthésage. Il faut utiliser un automate "à pile" (muni d'un compteur). La variable "equilibre" joue ce rôle de compteur.

Au début equilibre=0 (il y a équilibre, puisqu’il n’y a aucune parenthèse).

Pour chaque parenthèse ouvrante trouvée, nous ajoutons 1 à la variable "equilibre".

Pour chaque parenthèse fermante trouvée, nous retranchons 1 à la variable "equilibre".

Ainsi, trois cas peuvent se présenter :

1. En cours de validation, "equilibre" est strictement négatif : cela signifie que nous avons rencontré plus de fermantes que d’ouvrantes. Inutile d'aller plus loin : l’expression est incorrecte.

2. En fin de validation, "equilibre" est nul : tout s’est bien passé au niveau des parenthèses, il y a autant d’ouvrantes que de fermantes, et elles ne sont pas placées n’importe comment. En effet, comme "equilibre" est évalué dans l’ordre de lecture, une séquence comme "())(" aurait déjà été rejetée - à cause d'un équilibre négatif - au cours de la validation. Si donc "equilibre" est nul, et que l’expression est incorrecte, le problème ne vient pas d’une faute de parenthésage.

3. En fin de validation, "equilibre" est strictement positif : cela signifie que nous avons rencontré plus d’ouvrantes que de fermantes : l’expression est incorrecte.

Voici la fonction "automate" programmée :

function Automate(s: string): string;
const etats = 5;
 caracs = 16; // 16 caractères autorisés pour la saisie
 st = '0123456789+-*/()'; // les 16 caractères
 tab: array[1..etats, 1..caracs] of integer =
 //0 1 2 3 4 5 6 7 8 9 + - * / ( )
 ((3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 2, 2, 0, 0, 1, 0), {etat 1}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0), {etat 2}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 5, 5, 5, 5, 0, 4), {etat 3}
 (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 5, 5, 5, 0, 4), {etat 4}
 (3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 0, 0, 0, 0, 1, 0)); {etat 5}
 
var p, n: integer; car: char; etat, equilibre: integer;
begin
 if s = '' then
 begin
 result := 'Chaîne vide';
 exit;
 end;
 equilibre := 0; //comptage des parenthèses
 p := 0; //position courante dans la chaîne s
 etat := 1;
 repeat
 inc(p);
  car := s[p]; //caractère en cours
 if car = '(' then inc(equilibre);
 if car = ')' then dec(equilibre);
 if equilibre >= 0 then
 begin
 n := pos(car, st);
 // la position du caractère en cours dans la chaîne de caractères autorisés
 if n > 0 then etat := tab[etat, n]; //c'est un caractère autorisé
 end;
 until (p = length(s)) or (equilibre < 0) or (n = 0) or (etat = 0);
 if equilibre < 0 then
 result := 'Il y a une parenthèse fermante en trop à la position ' + inttostr(p)
 else
 if (equilibre > 0) then
 result := 'Il y a une parenthèse ouvrante en trop'
 else
 if n = 0 then
 result := 'Caractère non autorisé à la position ' + inttostr(p)
 else
 if etat = 0 then
 result := 'Expression incorrecte (erreur à la position ' + inttostr(p) + ')'
 else
 if (etat <> 3) and (etat <> 4) then
 result := 'Expression incorrecte (etat final non terminal)'
 else
 result := 'Expression correcte';
end;

Télécharger le code source Delphi