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.