Discussion :

[prgasp77]

Bonjour à tous,

je fais pour l'exercice un petit interpréteur RPN (Reverse Polish Notation). Mon premier brouillon fonctionne, mais je le trouve un peu … brouillon .

Ma pile est une float list reference ; et mes opérateurs des records contenant la commande utilisateur (string), le nombre d'opérandes (int) et l'opérateur (float list -> float list).

Je lis dans ma console une ligne. Si elle est interprétable en float, je l'empile sur ma pile globale ; et sinon je cherche dans la liste des opérateurs celui qui convient et l'applique (j'extrais le bon nombre d'éléments de la pile, les encapsule dans une float list, les passe à l'opérateur et empile le(s) résultat(s)).

Code :

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

1
2
3
4
5
6
let generic_operator op =
	let rec pop_operands acc = function
	| 0 -> acc
	| k -> pop_operands (pop() :: acc) (pred k)
	in
	List.iter push ( op.f (pop_operands [] op.dim) )

Ce n'est pas très élégant, n'est-ce pas ? De plus, si je veux ajouter des fonctionnalités ésotériques (variables, GUI, etc.) je dois bidouiller de manière pas vraiment orthodoxe.

Je viens donc à la pèche aux conseils. Quelles structures de données me conseillez-vous ?

Merci beaucoup.

[SpiceGuid]

Pour ta pile tu peux essayer ça :

Code OCaml :

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 BraunStack =
   struct
      type 'a env =
         | Empty
         | Braun of 'a env * 'a * 'a env
      exception
         IndexOutOfBounds
      let rec push x = function
         | Empty -> Braun(Empty,x,Empty) 
         | Braun(l,y,r) -> Braun(push y r,x,l)        
      let rec pop l r =
         match l with
         | Empty -> r
         | Braun(a,x,b) -> Braun(r,x,pop a b)     
      let rec nth n = function           
         | Empty -> raise IndexOutOfBounds
         | Braun(l,x,r) ->
            if n = 0 then x
            else if n land 1 = 0 then nth (n lsr 1) l            
            else nth (n lsr 1 - 1) r
   end

Avantages

• le pop ne déclenche pas d'exception parce que tu lui passes en argument les branches l et r du Braun à dépiler
• le top ne déclenche pas d'exception non plus car c'est le 'a d'un Braun
• l'accès au n-ième élément se fait en Θ(ln n)

Inconvénients

• le push se fait en Θ(ln n)

[prgasp77]

Merci de ton conseil ; mais la pile que j'emploie est le seul élément qui me convient (si ce n'est qu'elle n'accepte que les flottants). La RPN n'a besoin que des quelques premiers éléments de la pile.

En revanche, comment stocker des objets différents de manière efficace pour mon moteur RPN (peut être plus élégamment qu'un bête Num of float | Var of string | Unk of string) ?

Une autre question : comment gérer de manière générale les opérateurs ? Autrement qu'avec ocamllex ?


Merci.