Discussion :

[mobisky]

Bonjour , je suis actuellement un graduat en informatique et je recherche pour mon cours d'algorithmique ceci...

Evaluation d’expression:

-quelle stratégie emploie t on pour définir une expression de manière à obtenir des algos simples de traitements et d’évaluations
-respecter les ordres de priorité entre opérateurs
-respecter les emparenthésages

Est ce que qqn pourrait m'aider car la je suis littéralement pomer...


Merci pour toute aide

[Ol']

Salut,

Là, j'ai rien compris mais il y a peut-être une piste du côté de la logique polonaise inversée qui selon moi, vérifie tes critères.

(c'est ce qu'il y a sur les calculatrices HP-48 )

Ol'

[mio]

J'ai pas tout compris mais apparemment tu veux faire de l'analyse syntaxique. Si tu veux

-respecter les ordres de priorité entre opérateurs
-respecter les emparenthésages

Je te propose cette grammaire

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
    expression -> expression + expression
    expression -> expression - expression
    expression -> produit
    produit    -> facteur * produit
    produit    -> facteur / produit
    produit    -> facteur
    facteur    -> Nombre
    facteur    -> ( expression )

Ensuite tu construits ton arbre avec un analyseur de ce qui est fourni en entree.
Tu peux rajouter d'autres operateurs mais un des problemes qu'il faut bien prendre en compte c'est les problemes d'associativite qui normalement est bien inclus dans la grammaire.
Apres il suffit de lire l'arbre pour faire l'evaluation de ton expression ce qui n'est pas difficile une fois que tu sais construire ton arbre

Si vraiment tu n'y arrives pas regarde plus bas.



















































Voici une solution pour la construction de l'arbre ecrite en java pour la grammaire suivante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
    expression -> produit + expression
    expression -> produit - expression
    expression -> produit
    produit    -> facteur * produit
    produit    -> facteur / produit
    produit    -> facteur
    facteur    -> Nombre
    facteur    -> ( expression )

Bien evidemment ce serait pas mal que tu le fasses toi-meme.

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
 
import java.io.* ;
 
class Terme
{
    final static int NOMBRE=Lexeme.NOMBRE, PLUS=Lexeme.PLUS, MOINS=Lexeme.MOINS, MULT=Lexeme.MULT, DIV=Lexeme.DIV ;
 
    int nature ;
    double valeur ;
    Terme filsG, filsD ;
 
    Terme (int nat, double val, Terme fg, Terme fd) {
	nature = nat ; valeur = val ; filsG = fg ; filsD = fd ;
    }
 
    Terme (double val) {
	nature = NOMBRE ; valeur = val ; filsG = null ; filsD = null ;
    }
 
    Terme (int nat, Terme fg, Terme fd) {
	nature = nat ; filsG = fg ; filsD = fd ;
    }
 
    static double calcul (Terme t) {
	if (t == null) throw new Error ("Terme null.") ;
	if (t.nature == NOMBRE) return t.valeur ;
	double vG = calcul (t.filsG) ;
	double vD = calcul (t.filsD) ;
	switch (t.nature) {
	case PLUS: return vG + vD ;
	case MOINS: return vG - vD ;
	case MULT: return vG * vD ;
	case DIV: return vG / vD ;
	}
	throw new Error ("Terme inconnu de nature : " + t.nature) ;
    }
 
    public static void main (String[] args) {
	Terme inter = new Terme (MOINS, new Terme (2.0), new Terme (3.0)) ;
	Terme test = new Terme (PLUS, new Terme (1.0), new Terme (MULT, inter, new Terme (4.0))) ;
	System.out.println (calcul (test)) ;
    }
 
}
 
class Analyseur
{
    static Lexeme lexemeCourant ;
 
    static void lireLexemeSuivant () {
	lexemeCourant = Lexeur.lireLexeme () ;
    }
 
    static Terme lireExpression () {
	Terme p = lireProduit () ;
	switch (lexemeCourant.nature) {
	case Lexeme.PLUS: 
	    lireLexemeSuivant () ;
	    Terme q = lireExpression () ;
	    return new Terme (Terme.PLUS, p, q) ;
	case Lexeme.MOINS: 
	    lireLexemeSuivant () ;
	    Terme q2 = lireExpression () ;
	    return new Terme (Terme.MOINS, p, q2) ;
	default:
	    return p ;
	}
    }
 
    static Terme lireProduit () {
	Terme f = lireFacteur () ;
	switch (lexemeCourant.nature) {
	case Lexeme.MULT: 
	    lireLexemeSuivant () ;
	    Terme g = lireProduit () ;
	    return new Terme (Terme.MULT, f, g) ;
	case Lexeme.DIV: 
	    lireLexemeSuivant () ;
	    Terme g2 = lireProduit () ;
	    return new Terme (Terme.DIV, f, g2) ;
	default:
	    return f ;
	}	
    }
 
    static Terme lireFacteur () {
	switch (lexemeCourant.nature) {
	case Lexeme.NOMBRE:
	    double val = lexemeCourant.valeurNombre ;
	    lireLexemeSuivant () ;
	    return new Terme (val) ;
	case Lexeme.PARG:
	    lireLexemeSuivant () ;
	    Terme e = lireExpression () ;
	    if (lexemeCourant.nature == Lexeme.PARD) 
		lireLexemeSuivant () ;
	    else
		throw Lexeme.lexemeInattendu (lexemeCourant) ;
	    return e ;
	default:
	    throw Lexeme.lexemeInattendu (lexemeCourant) ;
	}
    }
 
    public static void main (String[] args) {
        Lexeur.in = new BufferedReader (new InputStreamReader (System.in)) ;
        Lexeur.lireCaractereSuivant () ;
	lireLexemeSuivant () ;
        do {
            Terme t = lireExpression () ;
	    System.out.println ("resultat: " + Terme.calcul(t)) ;
	    while (lexemeCourant.nature == Lexeme.POINT_VIRGULE)
		lireLexemeSuivant () ;
        } while (lexemeCourant.nature != Lexeme.FIN_FICHIER) ;
    }
 
}
 
class Lexeme
{
    int nature ;
    double valeurNombre ;
 
    final static int NOMBRE=0, PLUS=1, MOINS=2, MULT=3, DIV=4, PARG=5, PARD=6, POINT_VIRGULE=7, FIN_FICHIER = -1 ;
 
    Lexeme (double nombre) { // Constructeur pour les nombres
	nature = NOMBRE ;
	valeurNombre = nombre ;
    }
 
    Lexeme (int nat) { // Pour les autres types
	nature = nat ;
    }
 
    static Error lexemeInattendu (Lexeme l) {
	return new Error ("Lexeme inattendu : " + l.nature) ;
    }
 
    static void afficher (Lexeme l) {
	switch (l.nature) {
	case NOMBRE: System.out.println ("Nombre(" + l.valeurNombre +")") ; break ;
	case PLUS: System.out.println ("+") ; break ;
	case MOINS: System.out.println ("-") ; break ;
	case MULT: System.out.println ("*") ; break ;
	case DIV: System.out.println ("/") ; break ;
	case PARG: System.out.println ("(") ; break ;
	case PARD: System.out.println (")") ; break ;
	case POINT_VIRGULE: System.out.println (";") ; break ;
	case FIN_FICHIER: System.out.println ("FinDeFichier") ; break ;
	default: throw lexemeInattendu (l) ;
	}
    }
}
 
class Lexeur
{
    static char charCourant ;
    static boolean finAtteinte ;
    static BufferedReader in ;
 
    static void lireCaractereSuivant () {
	int caractereCourant ;
	try {
	    caractereCourant = in.read () ;
	} catch (IOException e) {
	    caractereCourant = -1 ; /* Equivalent a fin de fichier */
	}
	if (caractereCourant == -1) finAtteinte = true ;
	charCourant = (char) caractereCourant ;
    }
 
    static Lexeme lireLexeme () {
	lireLesBlancs () ;
	if (finAtteinte) 
	    return new Lexeme (Lexeme.FIN_FICHIER) ;
	if (Character.isDigit (charCourant)) 
	    return lireNombre () ;
	if (charCourant == '+' || charCourant == '-' 
	    || charCourant == '*' || charCourant == '/')
	    return lireOperation () ;
	if (charCourant == '(' || charCourant == ')')
	   return lireParenthese () ;
	if (charCourant == ';')
	    return lirePointVirgule () ;
	throw caractereInattendu () ;
    }
 
    static Error caractereInattendu () {
	return new Error ("Caractere inattendu : `" + charCourant + "'") ;
    }
 
   static Lexeme lirePointVirgule () {
       if (charCourant != ';')
	   throw caractereInattendu () ;
       lireCaractereSuivant () ;
       return new Lexeme (Lexeme.POINT_VIRGULE) ;
   }
 
   static Lexeme lireParenthese () {
      char c = charCourant ;
      lireCaractereSuivant () ;
      switch (c) {
	 case '(': return new Lexeme (Lexeme.PARG) ;
	 case ')': return new Lexeme (Lexeme.PARD) ;
      }
      throw caractereInattendu () ;
   }
 
    static Lexeme lireOperation () {
	char c = charCourant ;
	lireCaractereSuivant () ;
	switch (c) {
	case '+': return new Lexeme (Lexeme.PLUS) ;
	case '-': return new Lexeme (Lexeme.MOINS) ;
	case '*': return new Lexeme (Lexeme.MULT) ;
	case '/': return new Lexeme (Lexeme.DIV) ;
	}
	throw caractereInattendu () ;
    }
 
    static Lexeme lireNombre () {
	int res = 0 ;
	while (Character.isDigit (charCourant)) {
	    int chiffre = charCourant - '0' ;
	    res = 10 * res + chiffre ;
	    lireCaractereSuivant () ;
	}
	return new Lexeme ((double)res) ;
    }
 
    static void lireLesBlancs () {
	while (Character.isWhitespace (charCourant)) {
	    lireCaractereSuivant () ;
	}	
    }
 
    public static void main (String[] args) {
	in = new BufferedReader (new InputStreamReader (System.in)) ;
	lireCaractereSuivant () ;
	Lexeme l ;
	do {
	    l = lireLexeme () ;
	    Lexeme.afficher (l) ;
	} while (l.nature != Lexeme.FIN_FICHIER) ;
    }
}

En esperant t'avoir aide...

[Pazz]

> clement : le polonais inversé c simplement que l'expression a déjà une structure d'arbre à l'envers, mais les algos sont les mêmes.

[haypo]

Un p'tit lien vers ma page : http://www.haypocalc.com/dev/interpreteur.php
Stockage des expressions : http://www.haypocalc.com/dev/expression.php

J'utilse la notation pré-fixée, dans le style de LISP : chaque parenthèse est une nouvelle expression.
[list]"1+2" -> (+ 1 2) = expression, "+" = opérateur, "1" et "2" = nombre entier.

• "1+2*3" -> (+ 1 (* 2 3)), (* 2 3)=sous-expression=expression

@+ Haypo