IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Transformer une expression arithmétique bien parenthésée en un arbre binaire


Sujet :

Algorithmes et structures de données

  1. #1
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut Transformer une expression arithmétique bien parenthésée en un arbre binaire
    Salut à tous !

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


    aidez moi svp !

  2. #2
    Membre émérite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    septembre 2008
    Messages
    1 190
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2008
    Messages : 1 190
    Points : 2 675
    Points
    2 675
    Par défaut
    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.

  3. #3
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut
    Citation Envoyé par deathness Voir le message
    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

  4. #4
    Membre émérite
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    septembre 2008
    Messages
    1 190
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : septembre 2008
    Messages : 1 190
    Points : 2 675
    Points
    2 675
    Par défaut
    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.

  5. #5
    Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    janvier 2012
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : janvier 2012
    Messages : 2
    Points : 3
    Points
    3
    Par défaut
    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
    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
    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 :

    on lis le caractère, C, et on le place:
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    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 )

  6. #6
    Nouveau Candidat au Club
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2011
    Messages
    338
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2011
    Messages : 338
    Points : 0
    Points
    0
    Par défaut
    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

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Évaluer une expression arithmétique
    Par frucot dans le forum Débuter
    Réponses: 8
    Dernier message: 10/05/2010, 00h04
  2. Réponses: 9
    Dernier message: 21/01/2009, 08h54
  3. Réponses: 8
    Dernier message: 15/05/2007, 12h02
  4. Réponses: 1
    Dernier message: 09/12/2006, 11h13
  5. Evaluation d'une expression arithmétique
    Par MysticKhal_0 dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 10/03/2006, 19h25

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo