Bonjour,
Codant actuellement un programme en caml permettant de faire du calcul formel, je bloque au niveau de la simplification des expressions.
Tout d’abord, j’ai créer un parser et un lexer afin de transformé les saisies utilisateurs en tokens. Voici le code du parser :
%{
open Function
%}
%token <float> FLOAT
%token <string> VAR
%token COS SIN SQRT EXP LN PUIS
%token PLUS MINUS TIMES DIV
%token LPAR RPAR
%token EOL
%left PLUS MINUS
%left TIMES DIV
%left COS SIN SQRT EXP LN
%type <Function.formel> main
%start main
%%
main:
expr EOL { $1 }
;
expr:
| FLOAT { flt $1 }
| VAR { puis (var $1) (flt 1.) }
| FLOAT VAR { var $2 }
| LPAR expr RPAR { $2 }
| expr PLUS expr { add $1 $3 }
| PLUS expr { pos $2 }
| MINUS expr { neg $2 }
| expr MINUS expr { sub $1 $3 }
| expr TIMES expr { mul $1 $3 }
| expr DIV expr { div $1 $3 }
| COS expr { cos $2 }
| FLOAT COS expr { mul (flt $1) (cos $3) }
| SIN expr { sin $2 }
| FLOAT SIN expr { mul (flt $1) (sin $3) }
| SQRT expr { sqrt $2 }
| LN expr { lnp $2 }
| EXP expr { exp $2 }
;
Et celui du lexer :
{
open Parser
exception Eof
}
rule token = parse
| [' ' '\t'] { token lexbuf }
| ['\n'] { EOL }
| ['0'-'9']+ as lxm { FLOAT (float_of_string lxm) }
| '+' { PLUS }
| '-' { MINUS }
| '*' { TIMES }
| '/' { DIV }
| '(' { LPAR }
| ')' { RPAR }
| "cos" { COS }
| "sin" { SIN }
| "sqrt" { SQRT }
| "ln" { LN }
| "exp" { EXP }
| ['a'-'z']+ as lxm { VAR (lxm) }
| eof { raise Eof }
Les fonctions saisies par l’utilisateurs sont stockées sous forme d’arbre, dans le type formel, dont voici la définition :
type formel =
| Float of float
| Var of string
| Add of formel * formel
| Sub of formel * formel
| Mul of formel * formel
| Div of formel * formel
| Ln of formel
| Cos of formel
| Sin of formel
| Puis of formel * formel
| Sqrt of formel
| Exp of formel
Par exemple, la fonction : f(x) = x*x*x sera stockés sous la forme : Mul (Puis (Var "x", Float 1.), Mul (Puis (Var "x", Float 1.), Puis (Var "x", Float 1.)))
Mon objectif, et là où je bloque, serais de transformer cette fonction de manière à ce qu’elle soit représentée de la manière suivante : Puis (Var "x", Float 3.)
let rec simplify f =
let rec is_zero f =
match f with
| Float f when f = 0. -> true
| Float f -> false
| Var x -> false
| Add (f, g) -> is_zero f && is_zero g
| Sub (f, g) -> is_zero f && is_zero g
| Mul (f, g) -> is_zero f || is_zero g
| Div (f, g) -> is_zero f
| _ -> false
in
let rec simplify_zero f =
match f with
| Float f -> Float f
| Var x -> Var x
| Add (f, g) -> begin
if is_zero f && is_zero g
then Float 0.
else if is_zero f && is_zero g == false
then simplify_zero g
else if is_zero f == false && is_zero g
then simplify_zero f
else Add (simplify_zero f, simplify_zero g)
end
| Sub (f, g) -> begin
if is_zero f && is_zero g
then Float 0.
else if is_zero f && is_zero g == false
then simplify_zero g
else if is_zero f == false && is_zero g
then simplify_zero f
else Sub (simplify_zero f, simplify_zero g)
end
| Mul (f, g) -> begin
if is_zero f || is_zero g
then Float 0.
else Mul (simplify_zero f, simplify_zero g)
end
| Div (f, g) -> begin
if is_zero f
then Float 0.
else Div (simplify_zero f, simplify_zero g)
end
| Puis (f, g) -> begin
if is_zero f
then Float 0.
else if is_zero g
then Float 1.
else Puis (simplify_zero f, simplify_zero g)
end
| Cos f -> Cos (simplify_zero f)
| Sin f -> Sin (simplify_zero f)
in
let rec exist_var f =
match f with
| Float f -> false
| Var x -> true
| Mul (f, g) -> exist_var f || exist_var g
| Add (f, g) -> exist_var f || exist_var g
in
let rec simplify_op f =
match f with
| Float f -> Float f
| Var x -> Var x
| Mul (f, g) -> simplify_mul (Mul (simplify_op f, simplify_op g))
| Add (f, g) -> simplify_add (Add (simplify_op f, simplify_op g))
| Sub (f, g) -> simplify_sub (Sub (simplify_op f, simplify_op g))
| Puis (f, g) -> simplify_puis (Puis (simplify_op f, simplify_op g))
| Cos f -> Cos (simplify_op f)
| Sin f -> Sin (simplify_op f)
and
simplify_add f =
match f with
| Add (Float f, Float g) -> Float (f +. g)
| Add (Var x, Var y) -> Mul (Float 2., Var x)
| Add (f, g) -> Add (simplify_op f, simplify_op g)
and
simplify_sub f =
match f with
| Sub (Float f, Float g) -> Float (f -. g)
| Sub (Var x, Var y) -> Float 0.
| Sub (f, g) -> Sub (simplify_op f, simplify_op g)
and
simplify_mul f =
match f with
| Mul (Float f, Float g) -> Float (f *. g)
| Mul (f, g) -> Mul (simplify_op f, simplify_op g)
and
simplify_puis f =
match f with
| Puis (Float f, g) -> Puis (Float f, simplify_op g)
| Puis (f, g) -> Puis (simplify_op f, simplify_op g)
in
simplify_zero (simplify_op f)
La fonction simplify permet de 1) faire les opération +, - et *, et 2) permet de supprimer les 0 en trop (comme 0+3 ou 0*x). Les pattern matching de cette fonction ne sont pas encore exhaustif. J’aimerais améliorer cette fonction afin qu’elle puisse puisse factoriser les puissance ensemble, comme j’ai indiqué dans l’exemple au dessus.
Cela fait 2 jours que je bloque sur ce problème. J’ai fait plusieurs tests en vain, mais je tourne toujours entre appel récursif infini et résultat non voulu.
Bonne journée !
