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).
- interface ArbExp.h
- implémentation ArbExp.cpp
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 = < - - < < - S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < S < < - } S { < ] S [ > S < < - S } S { < ] S [ > S < < - S < ] S [ > S < < - > S < ] S [ > S < < - S > S < ] S [ > S < < - S ] S [ > S < < - S > S < < - S < - > S < - S > S < - S S S < i = 18 carvu = $ - S 1112121131415351515 VVV0CPP000VAC000000 jfp$

Construction d'un arbre binaire associé à un système de parenthèses

Arbres binaires en C++

Arbre binaire associé à un système de parenthèses

Construction de l'arbre binaire à partir de la dérivation droite inversée

Construction de l'arbre binaire à partir du système de parenthèses