Transformer une expression arithmétique bien parenthésée en un arbre binaire [Résolu]

[mohsenuss91]

Salut à tous !

je cherche un algorithme pour transformé
une expression arithmétique bien parenthésée a un arbre binaire


aidez moi svp !

[deathness]

Le but de ce forum est de t'aider pas de faire le travail à ta place.

Un tel algorithme nécessite que tu parses ton expression suivant ses séparateurs, et que tu construises ensuite ton arbre avec ces bouts d'expressions.
Un tel algorithme n'est pas dur à faire, en te faisant des exemples à la main tu arriveras vite à trouver comment faire.

[mohsenuss91]

Envoyé par deathness

Le but de ce forum est de t'aider pas de faire le travail à ta place.

Un tel algorithme nécessite que tu parses ton expression suivant ses séparateurs, et que tu construises ensuite ton arbre avec ces bouts d'expressions.
Un tel algorithme n'est pas dur à faire, en te faisant des exemples à la main tu arriveras vite à trouver comment faire.

merci a vous , je cherche juste l'idée de base
et quelques explication si c'est possible m'aident beaucoup

[deathness]

Et bien je t'ai déjà donnée l'idée de base:

Une première phase ou tu découpes ton expression suivant ses séparateurs (parenthèses par exemple)

Et une deuxième phase ou tu transformes tous ces bouts en arbre

Pour comprendre comment faire le mieux est de faire des exemples à la main:
tu prends un expression et tu réfléchis à ce que tu fais pour la transformer toi en arbre.

[gunnerkeiv]

bonjour à tous, si je ne suis pas trop tard j'ai peut être quelque conseil à te donner.

tout d'abord comme dit précédement tu va devoir parser ton expression en arbre binaire, cependant plusieurs méthode existe et ce que tu dois faire c'est un peu le principe de compilations.

bon passons ces détails et entrons dans le vif du sujet:

imaginons l'expression suivante:

v = A + B + ( C X D ) ;

notre expression est décomposable

en premier on a: v=, ce terme est important car il marque le début de ton expression

ensuite: A + B + ( C X D ), elle c'est ton expression à convertir en ARBIN

pour finir ';' : ce sigle montre la fin de ton expression.

voila la découpe étant faite tu peux maintenant t'orienter vers le parsage de l'expression,
pour construire en arbre binaire on va lire caractère par caractère (logique, non !?)

un arbre binaire c'est bien c'est beau mais il ne faut pas se tromper dans sa création,
un arbre binaire est structuré donc tu dois le structuré par toit mếmé ici imaginons que tu crée une structure de donnée contenant par exemple une terme un pointeur à gauche et un pointeur à droite.

une fois cela fait pense que autant dans l'ajout que dans la lecture tu dois procéder dans un certains ordre pour ne pas perdre le file de ton expression.

plusieurs façon de faire:

G = gauche, R = racine, D = Droite
3 éléments constituant un élément de l'arbre soit 3! possibilitées:

RGD
RDG
GDR
GRD
DRG
DGR

pour applique prenons encore par exemple v = A + B;
avec comme ordre GRD:

l'ajout se fera en commencant par A puis + et pour finir B

Code :

1
2
3
4
             +
           /  \
          A    B

donc ici sur la racine on retrouve un operateur
autre exemple: v = A + B + C

on auras un premier arbre : A + B
ensuute un second arbre: + C

comment savoir lequel mettre ou ?

c'est simple on construit notre arbre avec comme principe GRD

on construit d'abord la gauche qui un arbre à lui tout seul donc:

on lis le premier terme A qui devient la gauche du sous arbre de gauche
ensuite on a + qui lui est la racine et pour finir B qui est à droite:

ce qui donne:

Code :

1
2
3
4
     +
   /  \
  A    B

notre premier arbre
l'arbre ci dessus est la gauche de notre grand arbre
maintenant construisons la racine

on lis le prochain caractère qui est + et on le place sur la racine:

Code :

1
2
3
4
5
6
 
       +
      /
     +
   /  \
  A    B

pour finir il faut faire la droite de notre arbre :

on lis le caractère, C, et on le place:

Code :

1
2
3
4
5
6
        +
      /  \
     +    C
   /  \
  A    B

et voila notre arbre est construit .
je pense que avec ces infos tu devrais facillement t'en sortir.

sur ce bon travail (si celui-ci n'est pas déja fait )

[mohsenuss91]

merci a vous !
j'ai pas encore trouvé la solution pour mon problème et je suis un peu occupé en ce moment ..dés que je le ferais je le posterais pour le voir