Construction d'un arbre binaire associé à un système de parenthèses
(cours du jeudi 18 avril 2013)
On part du parseur ascendant écrit
en cours le 16 avril, et on lui ajoute la construction d'un arbre
binaire.
-
Arbres binaires en C++
La manipulation des arbres par programme fait appel de manière
essentielle à la notion de pointeur :
- chaque sommet se réalise comme un objet ;
- le lien entre un sommet et un de ses fils est réalisé par un
attribut de l'objet-sommet qui contient un pointeur sur l'objet-fils.
Dans cette perspective, les choses sont plus simples si le nombre de
fils est le même pour chaque sommet.
Nous nous bornons ici à 2 fils par sommet : chaque sommet se réalise
donc comme un triplet (étiquette, fils gauche, fils droit).
- l'étiquette représente l'information attachée au sommet - ce
sera pour nous un caractère ;
- les fils gauche et droit contiennent des pointeurs sur
d'autres triplets du même genre, ou bien le pointeur spécial
NULL
qui ne désigne rien.
Tout ceci se traduit dans la classe ArbExp
(ainsi nommée
car à l'origine elle a servi à représenter des arbres d'expression).
-
Arbre binaire associé à un système de parenthèses
L'arbre normalement associé à un système de parenthèses n'est pas en
général un arbre binaire.
Pour exploiter notre grammaire en utilisant notre classe ArbExp
,
nous devrons donc recourir à une autre interprétation.
À chaque paire de parenthèses (ouvrante-fermante) nous associons un
arbre binaire
- dont l'étiquette est P (comme parenthèses rondes) ou C
(crochets) ou A (accolades) ou V (cheVrons), ou encore 0 (signifiant
NULL
)
;
- dont le fils gauche pointe sur le sous-système contenu dans
la paire de parenthèses ;
- dont le fils droit pointe sur le sous-système qui suit la
paire de parenthèses en question.
En somme, l'étiquette de l'arbre déclare la nature du fils gauche du
sommet visé : de même qu'en onomastique arabe un nom comme Abou Zaïd
sgnifie père de Zaïd...
Voici une fonction C++ calculant le système de parenthèses à partir de
l'arbre :
string chpar( ArbExp* a) { // a non vide
switch( a->etiq() ){
case 'P' : return
'('+chpar(a->fg())+')'+chpar(a->fd());
case 'C' : return
'['+chpar(a->fg())+']'+chpar(a->fd());
case 'A' : return
'{'+chpar(a->fg())+'}'+chpar(a->fd());
case 'V' : return
'<'+chpar(a->fg())+'>'+chpar(a->fd());
case '0' : return "";
default :{
cout <<
"erreur " << a->etiq() << endl;
return "";
}
}
}//chpar
-
Construction de l'arbre binaire à partir de la dérivation
droite inversée
Elle se fait très simplement, en gérant une pile de pointeurs sur ArbExp
.
Pour visualiser l'arbre construit, on imprime la chaîne parenthésée.
Exemple :
jfp$ ./da
Donnez une dérivation droite inversée
1112121131415351515
<<<>[(())]<{[]}>>>
jfp$
Programme demoArb.cpp
-
Construction de l'arbre binaire à partir du système de parenthèses
On intègre la gestion de la pile de pointeurs sur ArbExp
avec la production de la dérivation droite par le parseur ascendant.
Pour cela, on réécrit la procédure reduire
, qui prend désormais en charge la construction de l'arbre :
void reduire (pile& p, pilArb& pa, int nr){ // nr = numéro de la règle à réduire
if( nr == 1 ){
pa.push(new ArbExp('0'));
p.push('S');
}else{
ArbExp* d = pa.top();
pa.pop();
ArbExp* g = pa.top();
pa.pop();
switch( nr ){ // attention 'nr' est un entier et non un caractère
case 2 : {
pa.push( new ArbExp('P', g, d));
break;
}
case 3 : {
pa.push( new ArbExp('C', g, d));
break;
}
case 4 : {
pa.push( new ArbExp('A', g, d ));
break;
}
case 5 : {
pa.push( new ArbExp('V', g, d ));
break;
}
default:{
cout << "erreur " << nr << endl;
return;
}
}// switch
int k = 4;
while( k > 0 ){
p.pop();
k--;
}
p.push('S');
}
}// reduire
Les autres modifications sont cosmétiques.
Pour ne pas répéter le système de parenthèses, on imprime de préférence l'arbre construit en notation préfixée.
Programme pb.cpp
.
Exemple :
jfp$ ./pp
Donnez un mot candidat
<<<>[(())]<{[]}>>>
i = 1 carvu = < - <
i = 2 carvu = < - < <
i = 3 carvu = > - < < <
i = 3 carvu = > - S < < <
i = 4 carvu = [ - > S < < <
i = 5 carvu = ( - [ > S < < <
i = 6 carvu = ( - ( [ > S < < <
i = 7 carvu = ) - ( ( [ > S < < <
i = 7 carvu = ) - S ( ( [ > S < < <
i = 8 carvu = ) - ) S ( ( [ > S < < <
i = 8 carvu = ) - S ) S ( ( [ > S < < <
i = 8 carvu = ) - S ( [ > S < < <
i = 9 carvu = ] - ) S ( [ > S < < <
i = 9 carvu = ] - S ) S ( [ > S < < <
i = 9 carvu = ] - S [ > S < < <
i = 10 carvu = < - ] S [ > S < < <
i = 11 carvu = { - < ] S [ > S < < <
i = 12 carvu = [ - { < ] S [ > S < < <
i = 13 carvu = ] - [ { < ] S [ > S < < <
i = 13 carvu = ] - S [ { < ] S [ > S < < <
i = 14 carvu = } - ] S [ { < ] S [ > S < < <
i = 14 carvu = } - S ] S [ { < ] S [ > S < < <
i = 14 carvu = } - S { < ] S [ > S < < <
i = 15 carvu = > - } S { < ] S [ > S < < <
i = 15 carvu = > - S } S { < ] S [ > S < < <
i = 15 carvu = > - S < ] S [ > S < < <
i = 16 carvu = > - > S < ] S [ > S < < <
i = 16 carvu = > - S > S < ] S [ > S < < <
i = 16 carvu = > - S ] S [ > S < < <
i = 16 carvu = > - S > S < < <
i = 16 carvu = > - S < <
i = 17 carvu = > - > S < <
i = 17 carvu = > - S > S < <
i = 17 carvu = > - S <
i = 18 carvu = $ - > S <
i = 18 carvu = $ - S > S <
i = 18 carvu = $ - S
1112121131415351515
VVV0CPP000VAC000000
jfp$