Discussion :

[z980x]

Bonjour à tous,

je dois faire un truc pour un projet, mais je ne sais pas trop par où commencer... Je ne sais pas trop trop quoi faire en premier, quoi vérifier ni rien...
Je dois le faire en C++, c'est la raison pour laquelle je poste ici, mais s'il y a un forum plus adapté, n'hésitez pas à m'en informer.

En fait, on doit écrire un programme qui convertira une opération arithmétique en LISP.
Seules 3 variables existent, X, Y et Z.
Les opérations sont +, -, * et /
Il peut y avoir des parenthèses pour spécifier une priorité.

Voici des exemples qu'il donne:

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
􀂾 X = 12
􀂾 (SETQ X 12)
􀂾 Y = 10
􀂾 (SETQ Y 10)
􀂾 Z = 30
􀂾 (SETQ Z 30)

􀂾 X + 10
􀂾 (+ X 10)
􀂾 X + (Z – Y)
􀂾 (+ X (- Z Y))
􀂾 X
􀂾 12
􀂾 X = 10
􀂾 (SETQ X 10)
􀂾 Y = Z / X
􀂾 (SETQ Y (/ Z X))
􀂾 Y
􀂾 3
􀂾 X + Y
􀂾 (+ X Y)
􀂾 X + (Y – 100) * Z
􀂾 (+ X (* (- Y 100) Z))
􀂾 A = 10
􀂾 Unrecognized variable name A
􀂾 X = Y ++ 10
􀂾 Unrecognized operator ++
􀂾 Z = Y Z
􀂾 Illegal arithmetic expression

En rouge, c'est ce que le programme doit afficher, après la saisie de l'utilisateur. (En noir)

Je ne sais pas du tout par où commencer... quelqu'un pourrait t-il m'aiguiller?

Merci !

[Nogane]

Bonjour,
Je pense que l'idée de base est de définir une grammaire qui te permette de créer un arbre a partir de tes formule.
A partir de cette arbre tu pourra ensuite générer le code LISP.

A tu le droit d'utiliser une librairie pour faire ça? (Si c'est un exercice je suppose que non...). boost::spirit peut peut-être t'aider, mais ne l'ayant jamais utilisé, je ne suis sur de rien.

Pour rentrer plus dans les détail, l'idée c'est que tes opérateurs deviennes des nœud de ton arbre, et les variables et valeurs numériques deviennent des feuilles. Bien sur il faut traiter les instruction entre parenthèse en premier, et respecter la priorité des opérateurs mathématique.

Par exemple:
X + (Z – Y)

Devient:
...+
./...\
X.....-
...../...\
....Z.....Y

Après il n'y a plus qu'a faire l'opération inverse pour reconstruire l'équivalent en LISP. Je pense que pour cette étape il vaux mieux mètre un maximum de parenthèse, pour de pas avoir a s'inquiéter de la priorité des opérateur en LISP.(Mais on as peut être pas le choix? J'ai jamais codé en LISP...)

Voila, j'espère que ça te mettra un peu sur la voie.

[loufoque]

Je ne sais pas du tout par où commencer...

Par le lexer. Ensuite tu fais le parser, puis tu affiches ton arbre.
C'est simple comme bonjour.

[z980x]

Merci à vous deux.

Il n'est écrit nulle part que je ne dois pas utiliser de librairie, donc je regarderai du côté de boost::spirit.

Je vous tiendrai au courant.

Merci

[nikko34]

Merci à vous deux.

Il n'est écrit nulle part que je ne dois pas utiliser de librairie, donc je regarderai du côté de boost::spirit.

Je vous tiendrai au courant.

Merci

à mon avis ton prof veux vérifier ton algo d'arbre, pas l'utilisation d'une lib de boost.

[loufoque]

On t'a pas plutôt appris à utiliser lex/yacc en cours ?

[jack-ft]

Par le lexer. Ensuite tu fais le parser, puis tu affiches ton arbre.
C'est simple comme bonjour.

Je dirais même plus: élémentaire !

Bonjour,
Je pense que l'idée de base est de définir une grammaire qui te permette de créer un arbre a partir de tes formule.
A partir de cette arbre tu pourra ensuite générer le code LISP.

Pour rentrer plus dans les détail, l'idée c'est que tes opérateurs deviennes des nœud de ton arbre, et les variables et valeurs numériques deviennent des feuilles. Bien sur il faut traiter les instruction entre parenthèse en premier, et respecter la priorité des opérateurs mathématique.

Par exemple:
X + (Z – Y)

Devient:
...+
./...\
X.....-
...../...\
....Z.....Y

Après il n'y a plus qu'a faire l'opération inverse pour reconstruire l'équivalent en LISP.

Jusque là, je suis complètement d'accord (lexer pour reconnaître les tokens (nombres, variables, opérateurs), puis parser pour créer l'arbre).

Je pense que pour cette étape il vaux mieux mètre un maximum de parenthèse, pour de pas avoir a s'inquiéter de la priorité des opérateur en LISP.(Mais on as peut être pas le choix? J'ai jamais codé en LISP...)

Effectivement, on n'a pas le choix!

Comme il n'existe pas de notion de priorité en lisp, il n'y a pas besoin de mettre le maximum de parenthèses (comme en C, par exemple), mais juste celles qu'il faut!

Chaque fois que tu as un sous-arbre avec un opérateur / une fonction en racine et une liste ordonnée d'arguments (qui sont eux-mêmes des sous-arbres ou des feuilles (c'est-à-dire des variables ou des nombres)), pour le transformer en lisp, il suffit de mettre une parenthèse ouvrante, le nom de la fonction, puis, séparés par des espaces, les arguments (selon un processus évidemment récursif) et une parenthèse fermante. C'est un genre de notation polonaise ou préfixée.

En résumé:
expr ::= (fonction arg1 ... argn)
fonction ::= symbole
arg ::= nombre | variable | expr

Voila, j'espère que ça te mettra un peu sur la voie.

Bis !

)jack(