IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

Simplifier une expréssion arithmétique


Sujet :

Caml

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Inscrit en
    Septembre 2010
    Messages
    78
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 78
    Par défaut Simplifier une expréssion arithmétique
    Bonjour,

    Voilà j'essaye de faire une fonction "simplifier" qui avec une expression arithmétique contenant des variables, rend une simplification où tous les calculs ( d'entiers donc ) sont effectués

    Voici mes déclarations:

    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
    (* Definition d'un arbre binaire *)
    type ('a,'b) arbre_bin = Feuille of 'b
    			 | Noeud of ('a,'b) noeud
     
    and ('a,'b) noeud = { gauche : ('a,'b) arbre_bin;
    		      op : 'a;
    		      droite : ('a,'b) arbre_bin };;
     
    (* Operateur arithmétique *)
    type operateur = Plus | Moins | Mul | Div;; 
     
    (* Type de valeur dans l'expression *)
    type primaire = Variable of string | Entier of int;;
     
    (* Expression arithmétique *)
    type expr = (operateur, primaire) arbre_bin;;
     
    (* Exemple d'expression *)
    let e2 = Noeud({gauche = Feuille (Variable  "x"); op=Mul; droite =
    		   Noeud({gauche = Feuille (Variable "y"); op = Moins ; droite = 
    			     Noeud({gauche = Feuille (Entier 5); op = Div; droite = Feuille (Entier 4)})
    			 })
    	       });;
    Et voici où je me suis arrêté. Je pense que mon problème est que je n'arrive pas à faire l'addition de 2 feuilles. Enfin bon je bloque

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    let evalOp = function 
        Plus -> (+)
      | Moins -> (-)
      | Mul -> fun x y -> x * y
      | Div -> (/);;
     
    let rec simpl = function e -> match e with
        Feuille f -> f
      | Noeud n -> match (simpl(n.gauche),simpl(n.droite)) with 
    	(Feuille (Entier i), Feuille (Entier j)) -> Feuille (Entier (evalOp (n.op) i j));;
    Tout aide ou remarque sont le bienvenues ! Et merci à vous

  2. #2
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Par défaut
    peux-tu détailler ce que tu souhaites réellement faire ?
    histoire qu'on t'indique des algos adaptés ?


    connais-tu le Global Value Numbering ou le Partial Expression Reduction, voire un mixte des deux appelé VNGPRE ?
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  3. #3
    Membre averti
    Inscrit en
    Septembre 2010
    Messages
    78
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 78
    Par défaut
    Non du tout. Sinon j'avais trouvé 2 ou 3 TDs sur les expressions arithmétiques en ocaml, mais l'approche est très différente de la mienne

    Sinon pour donner un exemple, je prends cette expression:

    e = x * ( y - ( 5 / 4 ))

    Après simplification
    e simplifié = x * ( y - 1 ))

  4. #4
    Membre émérite
    Profil pro
    Inscrit en
    Avril 2007
    Messages
    832
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Avril 2007
    Messages : 832
    Par défaut
    Voici la façon dont je procèderais, style "normalisation par évaluation":

    1. Définir une "forme normale" pour tes expressions, c'est à dire la structure de ce que tu espères obtenir une fois que tu as simplifié au maximum; ici, il me semble que ce sont des polynomes multi-variables, donc par exemple une liste de couples (entier, liste de variables) interprétée comme une somme de produits : [(2, ["x"; "y"]); (3, ["z"]); (5, [])] pour 2*X*y+3*Z=5. Mais d'autres formes sont possibles (par exemple utiliser un (string set, int) map pour des raisons d'efficacité algorithmique).

    2. Écrire une fonction d'évaluation qui évalue tout terme vers une forme normale (donc tu définis comment transformer un entier ou une variable en polynôme, et l'effet des opérations sur les polynomes, puis tu évalues récursivement ton arbre).

    3. Ensuite si tu veux récupérer un arbre en sortie, écrire une fonction qui va dans l'autre sens, qui te redonne un arbre à partir d'une forme normale (donc ici qui "décompose" un polynôme en somme de produits).

    La fonction de simplification est alors la composée des fonctions des étapes 2. et 3.

  5. #5
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Par défaut
    ta fonction simpl compile ?


    avec cela plutôt ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
     
    let rec simpl e = 
     match e with
       Feuille f -> Feuille f
     | Noeud n -> 
        match (simpl(n.gauche),simpl(n.droite)) with
         (Feuille (Entier i), Feuille (Entier j)) -> Feuille (Entier (evalOp (n.op
    ) i j))
       | (g,d) -> Noeud({gauche=g; op=n.op ; droite=d}) ;;

    après clairement ce n'est pas satisfaisant... parcourir systématiquement l'arbre, ne pas y éliminer les redondances, etc

    peux-tu définir le type d'expressions à gérer ?
    resteras-tu sur des opérations linéaires ? as-tu besoin de polynômes ? as-tu besoin d'expressions quelconques ?
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  6. #6
    Membre averti
    Inscrit en
    Septembre 2010
    Messages
    78
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 78
    Par défaut
    A vrai dire, je n'ai pas vraiment de consignes supplémentaires.

    Ma fonction simpl ne marche pas ( sinon je ne serais pas ici ). Ma fonction devait normalement évaluer si les feuilles sont des entiers, et dans ce cas effecuter l'opération.

  7. #7
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Par défaut
    Citation Envoyé par Nollo Voir le message
    A vrai dire, je n'ai pas vraiment de consignes supplémentaires.

    alors, à quoi souhaites-tu te limiter ?


    Citation Envoyé par Nollo Voir le message
    Ma fonction simpl ne marche pas ( sinon je ne serais pas ici ). Ma fonction devait normalement évaluer si les feuilles sont des entiers, et dans ce cas effecuter l'opération.
    j'ai remarqué ^^ la mienne passe en ne modifiant pas trop la tienne, et fait ce que tu souhaitais

    mais il aurait été bon que tu regardes l'erreur, et tente de mieux voir pourquoi ça foirait... et clairement une énorme erreur de typage (et un filtrage non exhaustif)
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  8. #8
    Membre chevronné
    Profil pro
    Inscrit en
    Mars 2010
    Messages
    309
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2010
    Messages : 309
    Par défaut
    Citation Envoyé par gorgonite Voir le message
    connais-tu le Global Value Numbering ou le Partial Expression Reduction, voire un mixte des deux appelé VNGPRE ?
    Ah ouais, violent :p Il n'a pas d'affectation, le global value numbering ne s'applique pas du tout

  9. #9
    Rédacteur/Modérateur

    Avatar de gorgonite
    Homme Profil pro
    Ingénieur d'études
    Inscrit en
    Décembre 2005
    Messages
    10 322
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur d'études
    Secteur : Transports

    Informations forums :
    Inscription : Décembre 2005
    Messages : 10 322
    Par défaut
    Citation Envoyé par TropMDR Voir le message
    Ah ouais, violent :p Il n'a pas d'affectation, le global value numbering ne s'applique pas du tout
    il pourrait en vouloir à terme... (en tout cas, j'aime bien VNGPRE dans les premières phases du middle-end d'un compilo )
    Evitez les MP pour les questions techniques... il y a des forums
    Contributions sur DVP : Mes Tutos | Mon Blog

  10. #10
    Membre averti
    Inscrit en
    Septembre 2010
    Messages
    78
    Détails du profil
    Informations forums :
    Inscription : Septembre 2010
    Messages : 78
    Par défaut
    Nan du tout.

    C'est vraiment un truc bête et méchant, c'est la dernière question d'un TP d'ocaml, et étant donné qu'on a pas de correction, je voulais de mon côté trouver une solution. J'ai fais le reste du TP sans grosse difficulté et je trouvais bizarre de coincer à la dernière question comme ça.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. simplifier une expression math ?
    Par kanzarih dans le forum Delphi
    Réponses: 7
    Dernier message: 23/05/2006, 23h31
  2. [SQL] Simplifier une requête SQL ?
    Par renaud26 dans le forum PHP & Base de données
    Réponses: 5
    Dernier message: 29/04/2006, 13h50
  3. Simplifier une formule excel
    Par beegees dans le forum Macros et VBA Excel
    Réponses: 12
    Dernier message: 24/04/2006, 09h10
  4. Evaluation d'une expression arithmétique
    Par MysticKhal_0 dans le forum Algorithmes et structures de données
    Réponses: 9
    Dernier message: 10/03/2006, 18h25
  5. transformation d'une expréssion arithmétique
    Par extradamus dans le forum C
    Réponses: 2
    Dernier message: 02/12/2005, 16h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo