Deux usages des arbres

Description

-1-INF 421 — 06 Luc MarangetDeux usages des [e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Deux exemples d’arbres◮ Les arbres-termes :Le calcul propositionnel.◮ Les arbres structurants :Diviser le plan en quatre (et puis enquatre, et puis...)-3-Un grand classiqueUne expression bool´eenne e (ou proposition) est :◮ Vrai ou faux, T ou F,◮ Une variable x ,...x ,0 N−1◮ La n´egation ¬(e),◮ Une conjonction (e ∧e ), une disjonction (e ∨e ).1 2 1 2Note :◮ Conceptuellement c’est aussi simple que les expressionsarithm´etiques.◮ Techniquement, il y a un peu plus de sortes de termes.-4-La classe des propositionsSelon le principe d’un champ ( nature ).class Prop {final static int FALSE=0, TRUE=1, VAR=2, NOT=3, OR=4, AND=5 ;int nature ; int asVar ; Prop left, right ;private Prop (int nature) { this.nature = nature ; }private Prop (int nature, int asVar) {this.nature = nature ; this.asVar = asVar ;}private Prop (int nature, Prop left) {this.nature = nature ; this.left = left ;}private Prop (int nature, Prop left, Prop right) {this.nature = nature ; this.left = left ; this.right = right ;}}-5-Construction des termesIl devient hasardeux de se fier aux constructeurs. Des d´etails, li´es `ala r´ealisation concr`ete prennent trop d’importance.On utilisera plutˆot des m´ethodes statiques bien nomm´ees.static Prop mkTrue() { return new Prop(TRUE) ; }static Prop mkVar(int no) { return new ...

Sujets

• informatique

Informations

• Publié par: Undoe
• Nombre de lectures: 58
• Langue: Catalan

Extrait

-1-

INF 421 —

Deux

06

usages

des

Luc Maranget

arbres

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

-2-

◮

◮

Deux exemples d’arbres

Les arbres-termes:

Le calcul propositionnel.

Les arbres structurants:

Diviser le plan en quatre (et puis

quatre, et puis. . . )

en

-3-

Un grand classique

Uneexpressionboole´ennee(ou proposition) est :

◮Vrai ou faux,TouF,

◮Une variablex 0  . . . x N−1 ,

◮´ngeaLnatio¬(e),

◮Une conjonction (e 1 ∧e 2 ), une disjonction (e 1 ∨e 2 ).

Note:

◮Conceptuellement c’est aussi simple que les expressions arithm´etiques.

◮Techniquement, il y a un peu plus de sortes de termes.

-4-

La classe des propositions Selon le principe d’un champ✭nature✮. classProp{ final static intFALSE=0,TRUE=1,VAR=2,NOT=3,OR=4,AND=5 ; intnature;intasVar;Prop left,right;

privateProp(intnature) {this.nature=nature; }

privateProp(intnature,intasVar) { this.nature=nature;this.asVar=asVar; }

privateProp(intnature,Prop left) { this.nature=nature;this.left=left; }

privateProp(intnature,Prop left,Prop right) { this.nature=nature;this.left=left;this.right=right; }}

-5-

Construction des termes

Ildevienthasardeuxdesefierauxconstructeurs.Desde´tails,lie´s`a lare´alisationconcr`eteprennenttropd’importance.

Onutiliseraplutˆotdesm´ethodesstatiquesbiennomme´es. staticProp mkTrue() {return newProp(TRUE) ; }

staticProp mkVar(intno) {return newProp(VAR,no) ; }

staticProp mkNot(Prop e) {return newProp(NOT,e) ; }

staticProp mkAnd(Prop e1,Prop e2) { return newProp(AND,e1,e2) ; } . . .

C’est la technique ditefactory.

-6-

Bonus

Unecertained´econnexionentre

◮iuicprneosopioit)nt,esc’ueeq(cn,iotacfiice´pS

◮I´lpmnemeitaton(commentc’estfia,tciliceahpm

natureetc.)

On peut d’alleurs exprimer d’autres connecteurs logiques, sans changer les cellules d’arbre, par ex.

staticProp mkImplies(Prop e1,Prop e2) { returnmkOr(mkNot(e1),e2) ; }

-7-

Affichage

Commed’habitude,red´efinirtoString. publicString toString() { switch(nature) { caseTRUE:return"true"; caseFALSE:return"false"; caseVAR:return"x"+asVar; caseNOT:return"!("+left+")"; caseOR:return"("+left+" || "+right+")"; caseAND:return"("+left+" && "+right+")"; default:nworwethError("Prop (toString)") ; } }

B´ene´fice:System.out.println(e)fonctionne.

Parcours ? Infixe en quelque sorte.

-8-

Fonctionnement

∨

∨x 2

x 0 x 1

◮toString()du sous-arbre de gauche :

⊲Deux feuilles"x0"et"x1".

⊲:e´anitnooCcnta"("+"x0"+" || "+"x1"+")".

Soit au final pour ce sous-arbre"(x0 || x1)".

◮toString()du sous-arbre de droite :"x2".

◮Et finalement :"("+"(x0 || x1)"+" || "+"x2"+")"

-9-

CouˆtdetoString()

Consid´ererlasuited’expressions

E 0 =x 0  E k+1 =x k+1 ∨E k

◮L’arbreE k lenuetsi.ssembleplutˆot`aer

∨ x k ∨ x k−1 . . .

∨ x 1 x 0

◮L’arbreE k e2eds`ospk nœuds.+ 1

◮E k .toString()tiquadrastquenetaat´tcsno,eelseuintnsioodpr deschaıˆnesdetailleaumoins3+5+  + (2k+ 1).

-10-

toString✭iren´eail✮

derdehoetm´asteappend(

Avec leStringBuilderdehoetm´asteappend(String s), qui ajoutelachaıˆnes`lafiaundStringBuildertuˆouop,cnur proportionnel`as.length(). private voiderlduigBintrnSi(StringBuilder r) { switch(nature) { caseTRUE: r.append("true") ;break; caseFALSE: r.append("false") ;break; caseVAR: r.append("x"+asVar) ;break; caseNOT: r.append("!(") ; left.liuBredtSnignir(r) ; r.append(")") ; break; . . .

-11-

toString✭ae´nileri✮II

. . . caseAND: r.append("(") ; left.gBuitrinlderiSn(r) ; r.append(" && ") ; right.nSiintruigBdlre(r) ; r.append(")") ; break; } }

publicString toString() { StringBuilder r=newdlregBuitrinS() ; inStringBuilder(r) ; returnr.toString() ; } }