Discussion :

[ozone974]

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))))


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.

[dourouc05]

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
    …

[ozone974]

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 çà ?

[dourouc05]

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).

[ozone974]

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.

[dourouc05]

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).

[ozone974]

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

Merci.

[dourouc05]

J'implémente l'évaluation en circuit court des opérateurs booléens. Exemple : https://stackoverflow.com/questions/...amming-in-java

[souviron34]

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

[ozone974]

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.

[tbc92]

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.