Discussion :

[Happpy]

Bonjour tout le monde, je travaille sur un évaluateur de formule postfixe, voila le code sur lequel je suis parti :

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
31
32
 
type unaire == float -> float;;
type binaire == float -> float -> float;;
 
type lexem =
|nombre of float
|opUnaire of unaire * lexem
|opBinaire of lexem * binaire * lexem;;
 
type FP =
|formule of lexem list;; 
 
let empile lex refListe = refListe := lex::(!refListe);;
 
let depile refListe =
	match !refListe with
		|[] -> failwith("Pile vide !")
		|t::q -> begin refListe := q ; 
					   t;
				 end;;
 
let additionner a b = a +. b;;
let soustraire a b = a -. b;;
let multiplier a b = a *. b;;
let diviser a b = a /. b;;
let rec factoriel n =
	if n <= 0. then 1. else n *. factoriel(n -. 1.);;
let puissance a b =
	let x = ref a in
	for i = 2 to b do x := (!x) *. a done;
	!x;;
(*Racine carrée définie sur les réel par sqrt(nombre)*)

Où un lexem pouvant être soit un réel, soit un opérateur unaire (exemple : factoriel, cosinus...) ou opérateur binaire (addition, etc.)...

Et des fonctions d'empilage ou de dépilage que j'ai défini pour pouvoir manipuler chaque élément de la formule logique FP à l'aide d'une pile.

Est-ce correcte jusqu'à maintenant ? On nous a demandé de procéder de cette façon de toute manière...

Ainsi, pour définir une opération dans un lexem on aurait :

Code :

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

1
2
3
 
(*(a + b)*)
let F1 = opBinaire(a, additionner, b);;

Mais ce qui me gène c'est que je ne vois pas trop où est la notation postfixe là dedans en fait... car en écrivant a + b comme je l'ai fait au dessus on voit que c'est a + b et non a;b;+ comme ça devrai être en postfixe... à moins que ça soit un problème d'ordre de définition dans le type lexem... ?

Merci d'avance.

[Happpy]

Re bonjour, alors j'ai pensé à ce code :

Déclaration des types :

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
31
32
 
type unaire == float -> float;;
type binaire == float -> float -> float;;
 
type lexem =
	|nombre of float
	|opUnaire of unaire
	|opBinaire of binaire;;
 
type FP =
	|formule of lexem list;; 
 
let empile lex refListe = refListe := lex::(!refListe);;
 
let depile refListe =
	match !refListe with
		|[] -> failwith("Pile vide !")
		|t::q -> begin refListe := q ; 
					   t;
				 end;;
 
let additionner a b = a +. b;;
let soustraire a b = a -. b;;
let multiplier a b = a *. b;;
let diviser a b = a /. b;;
let rec factoriel n =
	if n <= 0. then 1. else n *. factoriel(n -. 1.);;
let puissance a b =
	let x = ref a in
	for i = 2 to b do x := (!x) *. a done;
	!x;;
(*Racine carrée définie sur les réel par sqrt(nombre)*)

Fonction d'évaluation de la formule postfixe :

Code :

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

1
2
3
4
5
6
7
8
9
10
 
let evalFormulePostfixe form =
	let  pile = ref [] in
	let rec lireElement f = 
		let elem = depile f in
		match elem with 
			|nombre a -> empile a pile
			|opUnaire b -> let nomb = depile pile in empile (b nomb) pile
			|opBinaire c -> let nomb1 = depile pile in let nomb2 = depile pile in empile (c nomb1 nomb2) pile
	in if list_length form = 0 then failwith("Formule ?") else lireElement form;;

Evidemment, la fonction d'évaluation n'est pas correcte...
Mais j'ai pensé à ce code globalement...

[gorgonite]

Comme avec l'exercice précédent :

1. supprimer la reférence de liste
2. pas besoin de list_length pour vérifier si la liste est vide

le reste a l'air pas mal (je n'ai pas testé... a priori, ça prend 10 sec à coder )

[Happpy]

Pour la référence de liste, c'est dans la fonction d'évaluation pour "pile" ou bien dans les fonctions empile et depile ?
Car pour empile et depile il faut la référence car on modifie la liste ?

[gorgonite]

Pour la référence de liste, c'est dans la fonction d'évaluation pour "pile" ou bien dans les fonctions empile et depile ?
Car pour empile et depile il faut la référence car on modifie la liste ?

il faut PENSER FONCTIONNEL

Il faut une fonction auxiliaire avec la pile en argument... du coup, tu filtres pour déconstruire les N premiers éléments souhaités et tu accumules le résultat du calcul avec ce qui reste lors de l'appel récursif

[SpiceGuid]

J'ai envie de rebondir sur tes interrogations :

Mais ce qui me gène c'est que je ne vois pas trop où est la notation postfixe là dedans en fait...

Code :

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

1
2
3
4
5
6
7
type lexem =
	| Nombre of float
	| OpUnaire of unaire
	| OpBinaire of binaire
 
type fp =
	| Formule of lexem list

Réponse: le problème de l'ordre postfixe se pose dans le type fp.
Tu ne peux pas le résoudre en Caml-Light.
Il y a également un second problème, celui de la pile vide que tu traites dynamiquement avec failwith.
Et encore une fois tu ne peux pas le résoudre statiquement en Caml-Light.

(désolé pour le hors-sujet, on va passer de Caml-Light à OCaml )

Si tu utilisais uniquement ces 3 constructeurs (number,unary,binary) alors ta liste se terminerait toujours par un opérateur unaire ou binaire, ou bien serait réduite à un nombre.

Code :

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

1
2
3
let number x = [Number x]
let unary x f = x @ [Unary f]
let binary a b f = a @ b @ [Binary f]

En fait, moyennant un supplément de plomberie, ta liste sera toujours en ordre postfixe.
On peut le garantir statiquement.

Code OCaml 3.12.1 :

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
31
32
33
34
35
module PostfixTypes =
struct 
   type unary_f = float -> float
   type binary_f = float -> float -> float
   type number
   type unary
   type binary 
end

module Postfix :
sig
   include module type of PostfixTypes
   type lexem = private
      | Number of float
      | Unary of unary_f
      | Binary of binary_f  
   type 'a postfixed = private
      lexem list  
   val number : float -> number postfixed
   val unary  : 'a postfixed -> unary_f -> unary postfixed         
   val binary : 'a postfixed -> 'b postfixed -> binary_f -> binary postfixed 
end
   =
struct
   include PostfixTypes
   type lexem =
      | Number of float
      | Unary of unary_f
      | Binary of binary_f  
   type 'a postfixed =
      lexem list  
   let number x = [Number x]
   let unary x f = x @ [Unary f]
   let binary a b f = a @ b @ [Binary f]
end

Cette plomberie consiste essentiellement à :

1. ajouter un type fantôme à postfixed pour coder la contrainte d'ordre postfixé au niveau du type de la liste d'opérandes/opérateurs
2. utiliser private pour obliger la construction par number, unary et binary

Et pour la pile ?
Même traitement en codant la taille de la pile au niveau de son type. Toujours à l'aide d'un type fantôme.

Code OCaml 3.12.1 :

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
module LexemStack :
sig
   type zero
   type 'a succ
   type 'a stack
   val empty : zero stack
   val push : Postfix.lexem -> 'a stack -> ('a succ) stack
   val pop  : ('a succ) stack -> 'a stack
   val top  : ('a succ) stack -> Postfix.lexem
end
   =
struct
   type zero
   type 'a succ
   type 'a stack =
      Postfix.lexem list  
   let empty = []
   let push h t = h::t
   let top (h::t) = h
   let pop (h::t) = t
end

Si quelqu'un plus au fait des dernières innovations dans le monde du chameau a une solution plus élégante ou même simplement une alternative (GADTs?) je suis volontiers preneur


EDIT: en renversant une liste postfixée, on obtient une liste préfixée, c'est-à-dire une pile prête à consommer à coups de pop pop pop...

Du coup ça me suggère un encodage plus précis d'un type expression.

D'abord on enfile tout avec les constructeurs d'une Queue :

Code OCaml 3.12.1 :

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

1
2
3
4
val number : float -> number expression
val unary  : 'a expression -> unary_f -> ('a * unary) expression        
val binary : 'a expression -> 'b expression -> binary_f -> ('a * 'b * binary) expression

Ensuite on renverse la queue, elle devient une pile.
Enfin on dépile tout avec les destructeurs d'une Stack :

Code OCaml 3.12.1 :

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

1
2
3
4
val number : number expression -> float 
val unary  : (unary * 'a) expression -> (unary_f * 'a expression)         
val binary : (binary * 'b * 'a) expression -> (binary_f * 'b expression * 'a expression)