Discussion :

[Shivaneth]

Bonjour à tous et bonne année :p

Alors voilà, j'aimerai savoir si vous avez une idée du type d'algorithme qui tourne en arrière plan de ce programme : http://www.mathepower.com/english/terme.php parce que c'est exactement ce que je cherche à faire pour un de mes programmes mais niveau algo ça bloque.

Merci d'avance

Shiv@

[PRomu@ld]

En fait, généralement ce qui est fait, c'est une transformation d'arbre.

A partir d'une expression, tu construis un arbre de syntaxe abstraite. Les modifications de l'arbre te permettent de modifier l'expression (factorisation, développement, réduction, ...).

Il y a plusieurs moyens pour construire l'arbre (on en parle dans cette discussion actuellement : http://www.developpez.net/forums/sho...d.php?t=465459 et il y en a d'autres)

Ensuite pour ce qui est des algorithmes, c'est relativement simple. Tu te fixes des règles et tu les appliques sur l'arbre, c'est un processus purement récursif.

Un exemple d'arbre : 3 + 5 * 4

Code :

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

1
2
3
4
5
6
 
    +
   / \
  3   *
     / \
    5   4

Tu peux appliquer une règle de réduction du style suivant :

Code :

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

1
2
3
4
5
6
7
Si noeud courant = opérateur alors
     Si fils gauche = constante numérique et
          fils droit = constante numerique alors 
          reduire 
          Noeud courrant = fils gauche Noeud.opération fils droit. 
     Fin si
Fin si

Il faut appliquer ceci sur un parcours suffixe ( fils gauche, fils droit, noeud courant)

Ainsi ça donne :

Application sur le noeud courant :

Code :

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

1
2
3
4
5
6
 
    +
   / \
  3   *
     / \
    5   4

Il faut donc l'appliquer sur le fils gauche, le fils gauche est une constante numérique, on ne fait rien. On parcours donc le fils droit :

Code :

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

1
2
3
4
 
  *
 / \
5   4

Ici tu appliques la règle et le noeud devient donc une constante numérique (égale à 20).

L'arbre principal est donc :

Code :

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

1
2
3
    +
   / \
  3  20

Dernière étape du parcours suffixe : appliquer la règle sur le noeud courant.

Le résultat est donc 23.

Voilà pour le principe, une fois l'arbre construit, c'est relativement amusant à faire.

[Shivaneth]

Comme tu dis, une fois l'arbre construit ...

merci de ta réponse, je vais creuser de ce côté mais le problème c'est que je n'ai pas beaucoup de temps.

[PRomu@ld]

Si ce qui t'intéresse c'est manipuler l'arbre et pas le construire, comme je l'ai dis dans précédentes discussions, utilises flex/bison pour construire ton arbre.

[Shivaneth]

Le problème c'est que tout ce traitement doit se faire à l'intérieur d'un programme en C et que je ne pense pass qu'ajouter un autre traitement grâce à lex et yacc serait bon pour mon projet.

[PRomu@ld]

flex et bisons te fournissent des analyseurs léxicaux et syntaxiques sous forme de fonctions C.