Discussion :

[AliJava]

Bonjour,
Je suis un peu null en modelisation et en algo donc je demande votre aide sur un projet que j'ai eu du mal à commencer:
Ecrire un programme qui calcule les expressiosn sous forme + 3 2 = 5
* + 5 - 6 3 * 8 + 5 6 = (5 + (6-3)) * (8*(5+6)) = 704 et non pas 80

En gros j'ai remarqué que la grammaire est de type :
exp = op nombre nombre
| op exp exp
enfin je suppose que c bon, c moi qui le dit c pas dans le sujet
Donc c une calculatrice polonaise prefixée je souhaite pour cela ecrire :
(le langage c'est le CPP)
1 - une Classe Lexeur
2 - une classe Parseur
3- une classe Arbre et Noeud
4 - et what else ?
je ne sais pas ou commencer pour arriver au resultat voulu? quelqu'un pourrais m'aider avec une bonne doc SVP
rien trouvé sur le net
surtout comment parser recursivement, comment cree l'arbre et comment evaluer (j'imagine que ce dernier c facile c juste un parcours infixée)

Je vous remercie

EDIT:
Je tiens juste a ajouter les contraintes lol
pas d'enum ni de switch
et on doit imperativement profiter des avantages de la prog OO en cpp
d'ou mon appel à l'aide sinon j l'aurai fait à l'arache comme d'hab lol
merci encore

[ToTo13]

Bonjour,

ce genre de notation va permettre de construire un arbre de la façon suivante :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
Fonction ConstruireMonArbre()
Début
	Lire l'élément suivant
	Si élément = Opérateur alors
		début
			Ajouter un noeud avec l'opérateur
			ConstruireMonArbre() // Lire le membre de gauche
			ConstruireMonArbre() // Lire le membre de droite
		Fin
	Sinon
		Ajouter une feuille avec le nombre
Fin

Une fois que tu as l'arbre, ton évaluation sera triviale avec ce même type de fonction pour parcourir l'arbre

[AliJava]

Bjr,
Merci pour ta réponse, mais voilà comment j'ai compris ton algo

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
 
Fonction ConstruireMonArbre(String expr)
Début
	Lire l'élément suivant // Premier token
	Si élément = Opérateur alors
		début
			Ajouter un noeud avec l'opérateur // creer un noeud op
			ConstruireMonArbre(expr.next()) 
// Lire le membre de gauche
			ConstruireMonArbre(expr.next()) 
// Lire le membre de droite
		Fin
	Sinon
		Ajouter une feuille avec le nombre 
// ça sera notre test d'arret non ?
Fin

Mais je me pose la question sur comment l'appel récursif peut savoir si c un membre gauche ou droit, c'est a dire exp = op exp exp | nombre
-C'est vraiment trop c**, mais j'ai du mal avec les structures de données sous forme d'arbre, d'où le fait que j'ai commencé hier à faire avec une pile-
Je ne sais pas si j'etais clair je viens de me reveiller
bonne journée

[alex_pi]

Bjr,

-C'est vraiment trop con, mais j'ai du mal avec les structure de données sous forme d'arbre, d'ou le fait que j'ai commencé hier à faire avec une pile-

La version avec pile sera bien plus adapté à la notation polonaise inverse (c'est à dire postfixe)

[ToTo13]

Bonjour,

- en fait le test d'arret sera sur la lecture. Si tu ne peux plus lire de donnée, tout s'arrêtera.
- pour ce qui est de la récursivité, tu sais que tu parcours un arbre binaire, donc après avoir trouvé un opérateur : lors du premier appel de la fonction tu sais que tu dois commencer par lire le membre de gauche, puis le deuxième appel lis le membre de droite.

[acx01b]

salut je trouve le C pratique pour renvoyer à la fois une valeur et un indice dans un tableau

voici la fonction que j'utiliserais:

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
 
float lire_expression(elem **pe) {
   elem *e = *pe;
   if (e[0].type == OP) {
      e++;
      float a = lire_expression(&e);
      float b = lire_expression(&e);
      *pe = e;
 
      switch(e[0].type) {
         case '+':
            return a+b;
         case '*':
            return a*b;
      }
   }
   else {
      (*pe)++;
      return e[0].value;
   }
}

[Garulfo]

voici la fonction que j'utiliserais:

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
 
float lire_expression(elem **pe) {
   elem *e = *pe;
   if (e[0].type == OP) {
      e++;
      float a = lire_expression(&e);
      float b = lire_expression(&e);
      *pe = e;
 
      switch(e[0].type) {
         case '+':
            return a+b;
         case '*':
            return a*b;
      }
   }
   else {
      (*pe)++;
      return e[0].value;
   }
}

Tu devrais mettre des noms de variables explicites.
Ton code est super pour couler un débutant et ennuyeux (au mieux) à décoder pour un vétéran Entre autre, l'arithmétique sur les pointeurs ça rend un code bien prompt à être rempli de bug.

En tout cas, c'est la partie algo, c'est un algorithme qu'il faut fournir. Passer d'un code à un algorithme fait qu'au mieux, tu ne vas pas l'aider et au pire, tu vas l'emmener sur une mauvaise habitude : penser le code avant l'algo.

[AliJava]

Je suis tout a fait d'accord avec toi, ce que j'ai demandé est un algo et non pas une implemnetation
de plus le langage etant C++ je ne me vois à le faire QU'avec des pointeurs, je prefere les template et les references
il faut profiter des avantages du langage.

merci a toute l'equipe !