Algorithme de résolution d'équations

[_SamSoft_]

Bonjour, je suis en première S et je cherche à créer un programme en C permettant de résoudre des équations à une et à deux inconnues.

style : x = x + 23y + 45x ou plus simple x = 2y ...

Je ne vois pas du tout comment démarrer et je cherche des explications accompagnées d'un pseudo code (si possible). Ce n'est pas un devoir, je ne suis pas en S SSI mais S SVT donc pas de programmation.

C'est juste pour moi.

Merci d'avance

[souviron34]

ça s'appelle un interpéteur d'expressions arithmétiques. Il y en a plein.

Tu a même un thread ici-même dédié à ça..

http://www.developpez.net/forums/sho...d.php?t=387473

[_SamSoft_]

Merci Mais je souhaitais avoir les étapes et non pas des codes "tout prêt" de programmeurs profesionnels Des pseudos codes et explications adaptés à un jeune de 15 ans en 1 S SVT

Merci d'avance

[souviron34]

eh bien c'est assez simple.

Tu as 4 types de choses : des opérations à 2 opérandes (a+b par exemple), des opérations à 1 opérande (des fonctions, comme racine carrée, puissance, par exemple x^3), des opérandes, et des parenthèses.

Ces opérandes peuvent être des valeurs utilisateurs, ou bien le résultat d'une autre opération. Par exemple : 2 + (3 * 5 ).

Il faut tout d'abord ordonner les opérations élementaires par ordre de profondeur, afin de commencer par calculer les plus profondes. Puis, on remonte, jusqu'à arriver au niveau 1.

Exemple :

(a * b) + (c * d^3) - e

Il faut identifier que d^3 est une opération nécessitant un niveau de parenthèses.

En fait on aurait dû écrire :

( (a * b) + (c * (d^3) ) ) - e

Dans ce cas, en classant par ordre de profondeur on a :

d^3 profondeur 3 ( = x )
c * x profondeur 2 ( = s )
a * b profondeur 2 ( = u )
s + u profondeur 1 ( = y )
y - e profondeur 1


On fait donc :

x = d^3

puis

s = c * x

puis

u = a * b

puis

y = s + u

et enfin

resultat = y - e




En pratique, en général il suffit d'avoir 2 stockages par partie gauche et partie droite de l'opération élémentaire.

[_SamSoft_]

Tout à fait (visuelement je vois) mais point de vue programmation, je n'ai aucune idée de comment faire pour créer une fonction permettant de résoudre des équations de n'importe quel type

J'ai 15ans vous savez

[souviron34]

Alors je te donne juste un exemple simple :

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
#define ADDITION           0
#define SOUSTRACTION   1
#define DIVISION            2
#define MULTIPLICATION  3

.....

Fonction ( ..... )
{
.....
double Var1, Var2 ;
double Resultat ;


/* Ici tu rentres ta chaine, et tu fais une petite analyse, 
    en faisant une petite structure pour décrire une opération.

     Par exemple :

     typedef struct Poper {

                     int      Type ;

                     int      Ordre ;

                     double Var1 ;
                     double Var2 ;

                } Operation ;
 
     Tu peux faire un tableau de ces structures.
      L'ordre est déterminé par le nombre de parenthèses ouvrantes 
      qu'il t'a fallu traverser pour aller jusque là.

      Par contre, ensuite, il faut les trier.
*/

/ * Et ensuite tu boucles */

for ( i = 0 ; i < NOperations ; i++ )
  { 
      switch ( Operations[i].Type )
        {
           case MULTIPLICATION :
                 Resultat = Operations[i].Var1 * Operations[i].Var2 ;
                 break ;

           .....
        }
  }

Si maintenant tu te retrouves dans le cas à 2 opérandes avec des résultats intermédiaires (y), il te faut 2 résultats intermédiaires..

Je ne t'en dis pas plus..

A toi de fouiller pour trouver ce qu'il faut faire (il y a peut-être quelques compléments à apporter à la structure par exemple)... pour faire quelque chose de complet...

[PRomu@ld]

En fait, il faut procéder en plusieurs étapes. Et il existe plusieurs méthodes de résolutions (suivant la difficulté).

Le plus gros du boulot est en fait l'analyse. C'est une branche de la compilation.

Tu as deux analyses, la première est l'analyse lexicale et la seconde est l'analyse syntaxique.

La première analyse te permet de découper ton entrée en une liste de token. Un token, c'est un type et une valeur (enfin pas toujours mais grosso modo c'est ça).

Prenons ton exemple :

x = x + 23y + 45x

En supposant que les types des tokens peuvent être ceci :
-> variable
-> operateur
-> constante

L'analyse lexicale va te produire la liste de token suivants (type,valeur) :

(variable , 'x' )
(operateur, '=' )
(variable, 'x' )
(operateur, '+' )
(constante , '23' )
(variable , 'y' )
(operateur , '+' )
(constante , '45' )
(variable , 'x' )

L'analyse lexicale se charge de lire l'entrée, en zappant tout ce qui est espace, tabulation, elle fait aussi les conversions (lecture d'entiers, de réels, ...)

Une fois que tu as ta liste de token, tu peux passer à la deuxième étape : l'analyse syntaxique.

L'analyse syntaxique va prendre ta liste de token pour en construire un arbre (généralement c'est ce qui est fait, ça peut être un graphe quelques fois).

Ici, l'arbre construit sera grosso modo celui-ci (désolé je ne suis pas fort en ascii-art):

Code :

1
2
3
4
5
6
7
8
9
10
11
  =
 / \
x  +
   / \
  x   +
      / \
     *   *
    /    / \
   / \  45 x
 23  y

Ensuite, une fois que tu as ton arbre, les symplifications et les transformations se font en fonction des opérations mathématiques (distributivité, associativité , ...). Par exemple, tu peux distribuer une variable comme ceci :

soit x * ( y + z ) :

Code :

1
2
3
4
5
6
  *
 / \
x  +
   / \
  y   z

Développé ça donne :

Code :

1
2
3
4
5
6
   +
  /  \
 *    *
/ \  / \
x y x z

Ce qui correspond bien à x * y + x * z. Tu peux comme ça, effectuer les transformations en fonction de ce que tu veux (simplifications, développement, factorisations, ...). C'est la partie assez amusante à faire et le processus de transformation est naturellement récursif, d'où l'utilisation de langages fonctionnels comme le proposait la réponse de souviron34. Maintenant, si tu veux le faire en C, c'est tout à fait possible.

Mais je dois t'avouer que les deux analyses sont assez fastidieuses et ennuyeuses (mais ça se fait), tu peux en utilisant des outils comme flex/bison (flex pour le lexical et bison pour le syntaxique) réaliser les deux analyses et uniquement te préoccuper de la partie amusante. Juste pour info, pour un analyseur simple ça se fait extrêmement rapidement

Maintenant, si tu souhaites faire le tout à la main, je peux détailler plus.

[_SamSoft_]

Merci, je verrai ca demain, je dois quitter le pc Mais je veux faire tout à la main (de toute façon, je programme maintenant pour "mon plaisir" donc pas de projets pour mon site, plus rien rien que pour moi xd mais mes logiciels resteront open source) Pouvez vous plus détailler (enfin c'est ce que vous dites à la fin )

[PRomu@ld]

mais mes logiciels resteront open source

flex/bison/yacc le sont, par conséquent ton projet peut le rester.

Pouvez vous plus détailler

En fait, tout dépend de ce que tu veux que je détaille.

Commençons par le commencement :

L'analyse lexicale dans sa forme générale, passe par des automates, tu n'en n'aura peut-être pas besoin ici (l'analyse n'est pas trop complexe). L'idée de base c'est de prendre les caractères de ton flot d'entrée (une chaîne, un fichier, ...) un par un pour les traiter.

Afin de faciliter les choses, tu peux commencer par te fixer les choses en n'aceptant d'une par que les variables à un seul caractère (exit donc le toto), comme ça, dès que tu tombes sur un caractère, tu peux quasiment conclure sur le token :

-> Dès que tu as un opérateur ou un caractère, tu crées ton token. (Tu ne vérifie pas que ton expression est valide ici : par ex un x = + y est valide pour le lexical).
-> Si tu tombes sur un chiffre, tu notes la position du caractère courant (une chaîne simplifie la vie), le tout est de parcourir le reste de ta chaine jusqu'à la prochaine chose qui n'est pas un chiffre (ou un point), une fois trouvé, tu crée ton token avec le bon type (entier/réel) et tu récupère aussi la valeur (comme tu fais ça en C, tu peux utiliser les strto* ). Ici, tu peux trouver les erreur sur les nombres réels (deux points par ex).

L'analyse lexicale est purement séquentielle (bête et méchant)

Pour l'analyse syntaxique c'est beaucoup plus compliqué. Là un automate peut servir, mais on verra ça plus tard.

[Jedai]

Si tu veux te lancer dans le domaine, je te conseille vivement d'utiliser un langage fonctionnel (comme Haskell, OCaml, ...), ils sont beaucoup plus adaptés à l'analyse symbolique et à la manipulation de structures de données récursives, tu as également d'excellents outils pour faire de l'analyse syntaxique (Parsec en Haskell, ocamlyacc en OCaml,...).

Code Haskell :

1
2
3
4
5
6
7
8
data Expr = Var String | Number Int | Add Expr Expr | Mul Expr Expr
          deriving (Show)

derive byV (Var s) | byV == s = Number 1
                   | otherwise = Var s
derive byV (Add e1 e2) = Add (derive byV e1) (derive byV e2)
derive byV (Mul e1 e2) = Add (Mul (derive byV e1) e2) (Mul e1 (derive byV e2))
derive _ (Number n) = Number n

Par exemple ce petit code en Haskell implémente une représentation pour les expressions ne contenant que des additions, des multiplications, des constantes entières et des variables nommées. Ainsi que le calcul de la dérivée d'une telle expression par rapport à une variable donnée.

Ce n'est pas un très bon code, mais tu peux constater qu'il sait déjà dériver "(x^2) + x" en "2x + 1" :

Code :

1
2
f = Add (Mul (Var "x") (Var "x")) (Var "x")
f' = derive "x" f

--
Jedaï

[pseudocode]

Envoyé par _SamSoft_

Bonjour, je suis en première S et je cherche à créer un programme en C permettant de résoudre des équations à une et à deux inconnues.

style : x = x + 23y + 45x ou plus simple x = 2y ...

Au risque de me faire huer par tout le monde ici, si tu cherches a résoudre ce genre d'equation (développé, 1er degré), il suffit juste de recuperer les coefficients.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 x =  x + 23y + 45x

Ce qui est equivalent a:

1x = 1x + 23y + 45x

A droite du signe '=' -> on prend le coefficient
A gauche du signe '=' -> on prend l'opposé du coefficient

Coefficients pour X:  -1 , 1, 45
Coefficients pour Y:  23

On fait la somme des coefficients:

Somme des coefficients pour X:  45
Somme des coefficients pour Y:  23
 
Donc: 45x+23y=0

[_SamSoft_]

Merci pour tout Je commence à comprendre (après une lecture en diagonale et une autre plus profonde )

Alors, j'ai encore quelques questions :

-Où puis-je trouver des tutos pour lex et yacc, enfin j'ai un site :
http://www.linux-france.org/article/devl/lexyacc/

-Dois-je utiliser Lex ou Yacc ?

-J'hésite encore à utiliser OCaml ou Hasckell. Je préfère C

-Pour la création d'arbre, j'ai pas trop compris ?!

Merci d'avance

[PRomu@ld]

Au risque de me faire huer par tout le monde ici, si tu cherches a résoudre ce genre d'equation (développé, 1er degré), il suffit juste de recuperer les coefficients.

Oui, on a tous supposé que ça n'était qu'un cas particulier, on pensait plus compliqué. (Sinon, c'est pas marrant )

-Où puis-je trouver des tutos pour lex et yacc, enfin j'ai un site :

Pour ce qui est des outils gnu, tu peux toujours regarder les manuels en lignes :

http://www.openbsd.org/cgi-bin/man.c...86&format=html

-Dois-je utiliser Lex ou Yacc ?

Lex c'est pour le lexical et Yacc c'est pour le syntaxique, si tu veux faire les deux analyses, il faudra utiliser les deux. Au passage, yacc et bison c'est la même chose (enfin pour les puristes non, mais bon ...)

-J'hésite encore à utiliser OCaml ou Hasckell. Je préfère C

En fait, le tout est de savoir si tu veux utiliser des outils ou pas, si tu veux utiliser flex/bison, il parait naturel de le faire en C (il existe ocamllex comme équivalent de flex pour Ocaml)

-Pour la création d'arbre, j'ai pas trop compris ?!

En fait, le but du jeu, c'est de construire un arbre de ton expression, arbre qui sera ensuite facile à utiliser pour effectuer des opérations.

[_SamSoft_]

Je vais déjà commencer par faire des choses simples en C avec lex et yacc et quand je maitriserai mieux l'outil, je mettrai à créer le logiciel de résolution d'équations

Mais je ne comprend toujours pas comment créer un arbre, un petit exemple

Merci d'avance.

[PRomu@ld]

En fait, la création de l'arbre, c'est la partie dure. (ça regroupe au minimum un semestre de cours donc pour tout t'expliquer ça risque être long)

L'arbre se construit généralement à partir d'une grammaire. Une grammaire, c'est un outil qui te permet de décrire un langage. Ici, le langage, c'est le langage des expressions arithmétiques (à quelque chose près).

Une grammaire se compose de plusieurs choses, des terminaux, des non terminaux, un axiome, des règles.

Pour exemple pour décrire une addition, ça se passe comme ça :

S -> T + T
T -> entier | reel

La grammaire est ici composée de trois règles, la règle S -> T + T , la règle T -> ENTIER et la règle T -> REEL. L'axiome est la première règle, les non terminaux sont les lettres majuscules et les terminaux sont les noms en minuscule. Les terminaux sont en fait des tokens.

La grammaire est vérifiée si tu peux satisfaire l'axiome. En clair ici, l'expression 5*3 n'est pas vérifiée car on ne peut pas écrire l'expression suivant l'axiome.

Alors tout ceci, c'est bien gentil mais comment on construit l'arbre ? Et bien c'est le coté technique, tu as plusieurs méthodes (analyse ascendante, analyse descendante), suivant la forme de la grammaire ( LL, LaLR, SLR, ...)

L'idée de base, c'est de créer un automate qui à chacun des symboles (ie des tokens) que tu va trouver va effectuer une action. (empilement, dépilement).

Ici, pour créer l'automate, on va simplifier les choses, admettons que l'on ait que des entiers, la grammaire est donc :

S -> T + T
T -> entier

L'automate a plusieurs états :

etat 0 :
-> Si on rencontre un entier, on va dans l'état 1.
-> Sinon, erreur.

etat 1 :
-> Si on rencontre un +, on va dans l'état 2
-> Sinon, erreur.

etat 2 :
-> Si on rencontre un entier. on dépile et on a l'arbre. (on a un S -> T + T)
-> Sinon, erreur.

Ici, c'est hyper-simplifié (trop pour justifier l'utilisation de l'automate) mais l'idée est là. Mais prenons un exemple d'analyse d'expression (analyse par un automate à pile) :

entrée : 5+3 ; token courant : 5 ; etat de la pile 0
-> action : empiler 5 et passer à l'état 1
entrée : +3 ; token courant : + ; etat de la pile 1
-> action : empiler + et passer à l'état 2
entrée : 3 ; token courant : 3 ; etat de la pile 2
-> dépiler les trois token et créer l'arbre.

Ce que fait yacc(ou bison), c'est de te créer cet automate (tu lui donne les règles de ta grammaire et lui il crée l'automate d'analyse). Je ne sais pas si tu as compris tout ce que je t'ai dis mais ça n'est pas le cas, tu n'as pas à t'inquiéter, il te manque quelques outils : automate, grammaire ainsi que les propriétés (expression rationnelles, LL(n), LaLR, SLR, ...).

Pour l'instant, je te conseillerai de regarder du coté de flex et bison, ensuite tout ce qui se passe dessous, tu verras ça plus tard.

Tu peux toujours regarder ce ce coté :

http://sjrd.ftp-developpez.com/tutor...yntaxiques.pdf

[_SamSoft_]

Merci. Tout ceci ne me réjouit pas je crois que j'ai pas encore le niveau pour cela

Mais ce sujet peut toujours servir !

[LLB]

Un conseil : dans un premier temps, laisse de côté la gestion des inconnues et essaie juste d'évaluer une expression arithmétique. Je te propose aussi de laisser de côté les aspects théoriques et la notion de grammaire. Tu peux même oublier les arbres (dans un premier temps).


Pour l'histoire, j'avais fait un programme de ce genre, en Delphi, quand j'étais au lycée. Je n'avais jamais ouvert un bouquin d'algo et n'avait presque pas d'accès Internet. Je me suis débrouillé tout seul ; d'un point de vue algo, c'était très sale, mais ça marchait suffisamment bien pour que je puisse tracer des courbes en faisant varier une variable. Je pense donc que tu seras capable de te débrouiller, d'autant plus que des gens sont prêts à t'aider.

Voilà ce que je te conseille :

1/ Écrit d'abord l'analyse lexicale. À partir d'une chaine en entrée, essaie de découper les tokens. Il suffit de reconnaitre les opérateurs et les nombres. Une structure avec juste 2 entiers peut servir pour le stockage (à toi de voir). Soit ta fonction renverra une liste de tokens, soit elle renverra le token suivant, à chaque fois qu'on l'appelle.

2/ Ensuite, essaie d'évaluer des expressions sans te poser la question de la priorité : "1 + 4 - 3 + 6". Ça ne devrait pas être trop compliqué.

3/ Enfin, réfléchit à comment ajouter la priorité. Le mot le plus important, c'est "récursion". Si vraiment tu restes bloquer (après avoir vraiment chercher), tu pourras regarder le code proposé sur le forum (la page du défi n°2). Je ne te parle pas de copier, juste de comprendre comment ça marche et d'être capable d'adapter la logique à ton code.

Si tu arrives à faire ça, repose la question ici. On pourra t'indiquer comment construire un arbre et travailler dessus.


Surtout, essaie de garder ton code simple. Il n'y a rien de compliqué. Il y a quelques années, j'avais écrit un programme de ce type, en C, sans jamais utiliser malloc ou free. Et pourtant, il était capable de travailler sur une expression infinie.