1 pièce(s) jointe(s)
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))))
Pièce jointe 282562
Ainsi que mon algo pour que vous voyiez mon travail :
Code:
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.
