1. #1
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    juin 2013
    Messages
    15
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : juin 2013
    Messages : 15
    Points : 11
    Points
    11

    Par défaut Construction d'un arbre syntaxique après la lecture d'une expression et retour d'une valeur logique

    Bonjour à tous,

    Voilà je suis actuellement en train de faire un algorithme (en quelque sorte un interpréteur) qui premièrement doit parcourir une chaîne d'expression donnée pour construire un arbre et deuxièmement dois parcourir l'arbre pour donner la valeur logique (vrai ou faux) de l'expression. Par contre voilà je bloque à la deuxième étape.

    Voici comme exemple une expression donnée avec l'arbre construit :
    (((a = b) OU (nbtours < (c + 2))) ET ((non ok) ET (( a > 0 ) OU ( x < (y + 5))))
    Nom : Arbre.png
Affichages : 178
Taille : 75,1 Ko

    Ainsi que mon algo pour que vous voyiez mon travail :
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    Opérateur --> Noeud
    Feuille --> Chiffre ou lettre
    Racine --> Opérateur pivot
    
    Explication Française :
    	1) Détecter l'opérateur central --> Création noeud racine
    	2) Extraire la chaîne précédente : Du début de la chaîne à noeud racine - 1 --> Noeud gauche
    	3) Extraire la chaîne suivante : De noeud racine + 1 à Fin Chaîne --> Noeud Droit
    	4) Se déplacer sur noeud gauche
    	5) Réexécuter les étapes 1 - 4 jusqu'à descendre sur des chiffres ou des lettres
    
    
    Langage Algorithmique :
    
    classe Noeud
    	chaine libelle
    	Noeud NG
    	Noeud ND
    
    	Méthode RechercheOpPivot (chaine expression) : entier		//Recherche de l'opérateur racine en haut de l'arbre
    	Var
    		compteur_parenthese = 0
    		i = 0
    		ch = expression
    		chbis
    		operateur
    	Début
    		Tant que (i =< ch.length) :
    			Si (ch[i] == '(' )
    				compteur_parenthese++
    			Si (ch[i] == ')' )
    				compteur_parenthese--
    			finnsi
    			i++
    			si (testoperateur(ch[i]) && compteur_parenthese == 0)
    				// c'est un pivot
    				retour i
    		FinTantQue
    		retour 0
    	Fin
    	
    
    	Methode testoperateur (chaine expression) : booleen		//Recherche des opérateurs dans une chaine de caractère
    	Var
    		ope[] == "ET,OU,NON,*,-,+,/,=,<,>";
    		nb == 0;
    	Debut
    		Tant que (nb < 10) Faire
    			Si (c == ope[nb]) alors
    				retour vrai
    			Sinon
    				retour faux
    			FinSi
    		FinTantQue
    	Fin
    
    	
    	Constructeur Noeud (chaine expression)
    	Var
    		entier
    		resultat_operateur
    	Début
    		Si (testoperateur(expression) == vrai)
    			Tant que (RechercheOpPivot(expression) == 0)
    				expression <- extractchaine(expression,1,expression.length-1)
    			FinTantQue	
    			resultat_operateur = RechercheOpPivot(expression)
    			NG = nouveau Noeud (extractchaine(expression,0,resultat_operateur-1)			// Création Noeud Gauche (1ère partie de l'expression)
    			ND = nouveau Noeud (extractchaine(expression,resultat_operateur+1,expression.length)	// Création Noeud Droite (2ème partie de l'expression)
    			libelle = expression[resultat_operateur]						// Création Noeud Parent (Opérateur)
    		Sinon
    			libelle = expression
    		FinSi
    	Fin
    Merci d'avance pour m'aider à trouver une solution pour le parcours de l'arbre.

  2. #2
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 321
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 321
    Points : 121 654
    Points
    121 654

    Par défaut



    Pour moi, il s'agit d'un "simple" parcours en profondeur : pour évaluer la valeur associée à un nœud, tu dois évaluer ses deux enfants, puis combiner leurs valeurs par l'opérateur contenu à ce nœud. Quand un nœud a déjà une valeur, tu as un cas de base et tu peux déjà associer une valeur.

    Dans ton exemple :
    • tu cherches à évaluer le premier nœud, ET : pour ça, tu évalues les deux enfants ;
    • tu cherches d'abord à évaluer celui de gauche (arbitrairement) : pour ça, tu dois évaluer au moins un des deux enfants (c'est un OU) ;
    • tu commences par l'enfant de gauche, qui est une égalité : tu évalues chacun des enfants pour avoir les valeurs correspondantes, tu peux savoir si elles sont égales, ce nœud a une valeur ;
    • tu retournes alors au nœud OU (par récursivité) : si le premier enfant a une valeur positive, tu a déjà la valeur de ton nœud, sinon, tu explores à droite ;
    • etc.


    En termes de pseudo-Python (sans la petite optimisation pour le OU pour garder le code plus lisible) :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    def evaluate(node): 
        if node is value: 
            return value of node
     
        valueLeft = evaluate(node.left)
        valueRight = evaluate(node.right)
        return node.operator(valueLeft, valueRight)

    Peut-être plus concret, y compris avec des optimisations pour les ET et OU logiques :

    Code python : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    def evaluate(node): 
        if node is value: 
            return value of node
     
        valueLeft = evaluate(node.left)
     
        if node.operator == OU && valueLeft == True: 
            return evaluate(node.right)
        elif node.operator == ET: 
            if valueLeft == False: 
                return False
            else: 
                return evaluate(node.right)
        elif node.operator == +:
            valueRight = evaluate(node.right)
            return valueLeft + valueRight
        …
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  3. #3
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    juin 2013
    Messages
    15
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : juin 2013
    Messages : 15
    Points : 11
    Points
    11

    Par défaut

    Salut dourouc05,

    Tout d'abord je tiens à te remercier pour ta réponse. Si j'ai bien compris je dois mettre en place un parcours en profondeur, mais je me suis renseigné un peu sur les parcours d'arbres et il s'avère qu'il y en ait plusieurs. Le parcours en profondeur préfixé (préordonné), infixe (symétrique) et postfixé (postordonné).
    Apparemment dans ton pseudo-code, tu utilises le parcours préfixé c'est bien çà ?

  4. #4
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 321
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 321
    Points : 121 654
    Points
    121 654

    Par défaut

    En fait, ça n'influence pas tellement . La distinction la plus importante, c'est un parcours en longueur ou en largeur — après, c'est plus pour les théoriciens . En réalité, c'est plutôt symétrique : j'ai commencé par la gauche parce que c'était plus sympa, mais j'aurais pu commencer par le fils à droite (sur ton schéma) sans aucun problème (ou tirer celui qu'on explore au hasard, après tout, pourquoi pas).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  5. #5
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    juin 2013
    Messages
    15
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : juin 2013
    Messages : 15
    Points : 11
    Points
    11

    Par défaut

    Je pense que je vais me simplifier la vie et prendre le parcours symétrique
    Par contre pour ton deuxième morceau de pseudo-code, je n'arrive pas à comprendre les différents tests qu'il effectue. Que fait-il exactement ?
    Peux-tu m'expliquer ?

    Merci d'avance.

  6. #6
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 321
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 321
    Points : 121 654
    Points
    121 654

    Par défaut

    Je détaille le premier code : pour chaque nœud, je vérifie l'opérateur qui correspond, puis j'applique un traitement qui correspond à l'opérateur (et adapté à l'opérateur).
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  7. #7
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    juin 2013
    Messages
    15
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : juin 2013
    Messages : 15
    Points : 11
    Points
    11

    Par défaut

    Oui ça j'ai bien compris, mais dans ton deuxième code j'aimerais comprendre le traitement que tu fais.

    Merci.

  8. #8
    Responsable Qt


    Avatar de dourouc05
    Homme Profil pro
    Ingénieur de recherches
    Inscrit en
    août 2008
    Messages
    22 321
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Ingénieur de recherches
    Secteur : Enseignement

    Informations forums :
    Inscription : août 2008
    Messages : 22 321
    Points : 121 654
    Points
    121 654

    Par défaut

    J'implémente l'évaluation en circuit court des opérateurs booléens. Exemple : https://stackoverflow.com/questions/...amming-in-java
    Vous souhaitez participer aux rubriques Qt ou PyQt (tutoriels, FAQ, traductions) ? Contactez-moi par MP.

    Nouveau ! Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  9. #9
    Expert éminent sénior

    Profil pro
    Inscrit en
    janvier 2007
    Messages
    10 542
    Détails du profil
    Informations personnelles :
    Âge : 60
    Localisation : France

    Informations forums :
    Inscription : janvier 2007
    Messages : 10 542
    Points : 17 022
    Points
    17 022
    Billets dans le blog
    2

    Par défaut

    Bonjour

    Si je peux me permettre, pourquoi utiliser un arbre ??



    Une analyse syntaxique, si les parenthèses sont bien mises, suffit à faire simplement une liste d'opérations..

    En effet, toutes les opérations sont soit à 1 opérande (log(x)) soit à 2 (x+y, a==b)..

    Toute opération se classe dans l'une ou l'autre des catégories.

    On peut donc analyser le nombre de parenthèses dans l'expression et classer dans l'ordre celles à faire en premier en les classant par niveau de profondeur de parenthèses, puis partir du niveau le plus profond et remonter... en effectuant les opérations à 1 seul opérande avant les autres

    J'avais fait un interpréteur d'expression mathématique comme ça.. Ca marche très bien et c'est "objet"...


    Ca ressemble fortement à ton arbre, mais on le traite comme un tableau, Il me semble que c'est plus simple et direct... Le tri par la profondeur permet d'avoir juste une série linéaire d'étapes où on a 2 opérandes à chaque fois et dont le résultat sert pour l'étage au dessus....

    (((a = b) OU (nbtours < (c + 2))) ET ((non ok) ET (( a > 0 ) OU ( x < (y + 5))))

    s1 = c+2
    e1 = y+5

    nbtours < s1 ? => s2 = 1 / 0
    x < e1 ? => e2 = 1 / 0

    a = b ? => s3 = 1 / 0
    a > 0 ? => e3 = 1 / 0

    s3 & s2 => s4 = 1 / 0
    e3 & e2 => e4 = 1 / 0

    e4 & nok => e5 = 1 / 0

    e5 & s4 => resultat = 1 / 0
    "Un homme sage ne croit que la moitié de ce qu’il lit. Plus sage encore, il sait laquelle".

    Consultant indépendant.
    Architecture systèmes complexes. Programmation grosses applications critiques. Ergonomie.
    C, Fortran, XWindow/Motif, Java

    Je ne réponds pas aux MP techniques

  10. #10
    Membre à l'essai
    Homme Profil pro
    Inscrit en
    juin 2013
    Messages
    15
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations forums :
    Inscription : juin 2013
    Messages : 15
    Points : 11
    Points
    11

    Par défaut

    Bonjour

    Désolé pour ce long retard. En tout cas merci à vous pour vos réponses.

    Tout d'abord dourouc05, j'aimerais connaitre quel traitement faire à chaque opérateur, j'ai suivi ton lien qui explique la fonction de court circuit des opérateurs booléens, mais ... Je n'arrive toujours pas à comprendre ta logique pour faire le traitement que tu as fait à chaque opérateur, avec le "OU" et le "ET".
    Si tu pouvais m'expliquer tout ça plus en détail, ça serait parfait !

    Souviron34, j'ai choisi de prendre l'arbre, car je m’entraîne à le manipuler pour des projets futurs.

  11. #11
    Rédacteur/Modérateur

    Homme Profil pro
    Ingénieur qualité méthodes
    Inscrit en
    décembre 2013
    Messages
    1 455
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur qualité méthodes
    Secteur : Conseil

    Informations forums :
    Inscription : décembre 2013
    Messages : 1 455
    Points : 3 039
    Points
    3 039

    Par défaut

    Je ne sais pas si ça répond à la question, ou si je suis totalement hors-sujet, mais je vois des choses comme ça.
    Je dois évaluer une expression comme xxxxx ET yyyyy
    xxxxx est un truc éventuellement complexe, et yyyyy aussi. Par exemple xxxxx, c'est ( x ET y ) OU z et yyyyy c'est ( (a OU b) OU (c ET d) )

    J'évalue xxxxx. Si xxxxx vaux FALSE, je n'ai même pas besoin d'évaluer yyyyy, parce que FALSE ET yyyyy, ça donne FALSE, peu importe la valeur de yyyyy.

    Et pour l'opérateur OU, on a aussi des simplification possibles.
    Si je dois évaluer xxxxx OU yyyyy, et si xxxxx vaut TRUE, alors inutile d'évaluer yyyyy, le résultat sera toujours TRUE.
    N'oubliez pas le bouton Résolu si vous avez obtenu une réponse à votre question.

Discussions similaires

  1. Construction d'un arbre syntaxique abstrait
    Par Lithrein dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 14/09/2010, 23h18
  2. Lecture de l'arbre syntaxique
    Par glayag dans le forum Eclipse Java
    Réponses: 0
    Dernier message: 19/01/2008, 20h22
  3. Réponses: 1
    Dernier message: 03/01/2007, 15h07
  4. Réponses: 1
    Dernier message: 02/01/2007, 11h22
  5. [Conception] Arbre syntaxique
    Par dessinateurttuyen dans le forum Général Java
    Réponses: 6
    Dernier message: 02/01/2006, 22h42

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