Salut à tous !
je cherche un algorithme pour transformé
une expression arithmétique bien parenthésée a un arbre binaire
aidez moi svp !
Salut à tous !
je cherche un algorithme pour transformé
une expression arithmétique bien parenthésée a un arbre binaire
aidez moi svp !
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.
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.
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
donc ici sur la racine on retrouve un operateur
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 + / \ A B
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:
notre premier arbre
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4 + / \ A B
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:
pour finir il faut faire la droite de notre arbre :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 + / + / \ A B
on lis le caractère, C, et on le place:
et voila notre arbre est construit .
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 + / \ + C / \ A B
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 )
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
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager