Arbres et fonctions

**azalara** · 18/01/2007, 01h11

Bonjour,

J'ai beaucoup de mal à implémenter les structures de données que je souhaite en java. Je ne sais pas si le problème vient de moi où du langage, mais je me sens beaucoup plus à l'aise dans d'autres langages.

Ma structure de donnée est celle-là (en Caml / F#) :

Code :

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

1
2
3
type 'a ast =
  | Op of ('a -> 'a -> 'a) * 'a ast * 'a ast
  | Val of 'a

En clair, c'est un arbre binaire où les nœuds sont des fonctions (à 2 arguments) et les feuilles des valeurs. Je souhaite que mon type reste générique, de sorte que les feuilles puissent être des entiers, des flottants, des strings ou autres.

Par la suite, je souhaite pouvoir évaluer l'arbre. Code en ml/F# :

Code :

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

1
2
3
let rec eval = function
  | Op (f, x, y) -> f (eval x) (eval y)
  | Val n -> n

Et pour tester, j'aimerais pouvoir entrer en arbre en dur, de façon assez claire et lisible. J'avais écrit ça en Caml :

Code :

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

1
2
3
4
5
6
7
let make v1 f v2 = Op (f, v1, v2)
and (!) n = Val n
 
let my_ast = make
    (make !3 (+) !2)
    (-)
    (make !40 (/) !10)

Bien sûr, j'ai cherché sur google et lu la faq. J'ai quand même plusieurs questions :

. quelle est la solution la plus simple pour modéliser l'arbre ? De ce que j'ai lu, il faudrait faire une classe abstraite et deux classes qui en héritent.

. a priori, je devrais utiliser une interface pour les fonctions de l'arbre (pour remplacer les pointeurs sur fonction). C'est bien ça ? Et c'est possible de faire ça en mélangeant avec les generics ? (j'avoue que je ne vois pas trop comment faire)

. enfin, je dois vraiment créer un objet pour chaque fonction que je veux ajouter ? Je trouve ça excessivement lourd, surtout quand c'est une simple addition ou une soustraction.

Question subsidiaire : vous pensez que c'est possible de convertir mes 10 lignes de ml en moins de 50 lignes de java ?

Par avance, merci de vos réponses.

**eclesia** · 18/01/2007, 09h52

...
J'avous avoir du mal a comprendre tes exemples.
je n'avais jamais entendu parlé de ce langage.

si tu avais moyen de le rediger autrement peut etre?

**Alec6** · 18/01/2007, 10h29

Le caml, on a pas entendu parler de ca depuis l'INRIA

Non on peut pas faire mieux que avec ton caml, (ca rappel de lambda calcul).

Il faut pas partir si loin dans la modélisation avec des interfaces, générics, abstract etc... Rien empeche de faire ca après une implémentation de classes concretes.

Ta modélisation est un vieux problèmes pour résoudre des formules du genres (2+4)*6/2 etc, qui est de lordre du design pattern interpretor (à lire mais pas simple à comprendre).

Commence par faire une classe OperationNode qui peut contenir d'autres OperationsNode (une arrayList c'est bien), ou alors deux champs puisque c'est binaire, et pas forcément commutatif. Ensuite tu assignes à chaque noeuds un type (genre +, - ou autre) ou opérateur=true ou false (si un nombre) et une valeur (valeur de l'opérateur +/- etc ou le nombre 23, 141 etc).

Chaque classe comporte une méthode récursive qui renvoi la valeur de l'opération effectuée sur ces fils...

bon courage. Tu peux nous présenter ton code si tu veux.

**®om** · 18/01/2007, 10h37

Je dirais:

Code :

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

1
2
3
Interface Fonction<A> {
    A f(A v1, A v2);
}

Si tu veux faire une addition d'entiers :

Code :

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

1
2
3
4
5
6
Fonction<Integer> maFonction = new Fonction<Integer>() {
    public Integer f(Integer v1, Integer v2) {
        return v1 + v2;
    }
}
int result = maFonction.f(5,3);

EDIT: Selon les besoins que tu sembles indiquer (appeler une fonction avec des paramètres comme dans ton make), en java tu ne devrais pas avoir besoin d'une structure d'arbre... Après, tu as peut-être des besoins plus complexes que ton exemple donné...

**azalara** · 18/01/2007, 22h09

Il faut pas partir si loin dans la modélisation avec des interfaces, générics, abstract etc... Rien empeche de faire ca après une implémentation de classes concretes.

Oui, d'accord. C'est cette vilaine habitude de vouloir faire des choses propres et extensibles.

Commence par faire une classe OperationNode qui peut contenir d'autres OperationsNode (une arrayList c'est bien), ou alors deux champs puisque c'est binaire, et pas forcément commutatif. Ensuite tu assignes à chaque noeuds un type (genre +, - ou autre) ou opérateur=true ou false (si un nombre) et une valeur (valeur de l'opérateur +/- etc ou le nombre 23, 141 etc).

Oui, c'est pas mal. Mais on perd un peu en sûreté : si le booléen est modifié par mégarde, le programme risque de planter à l'exécution (oui, j'ai cette manie de vouloir que le compilateur vérifie tout ce que je tape). Et on gaspille de la place inutilement (d'accord, on s'en fiche).
Je viens de trouver par hasard ce document (http://denis.monasse.free.fr/denis/a.../javatypes.pdf) qui explique bien la chose et présente une manière plus sûre et plus extensible. C'est en passant, comme je le pensais, par une classe abstraite et deux classes implémentées. Mais c'est vrai que c'est plus de code.

Selon les besoins que tu sembles indiquer (appeler une fonction avec des paramètres comme dans ton make), en java tu ne devrais pas avoir besoin d'une structure d'arbre... Après, tu as peut-être des besoins plus complexes que ton exemple donné...

Le make sert juste à construire mon arbre. Si le but était juste de calculer la valeur, j'aurais directement écrit "5 + 3".

Mais oui, je passerai par l'interface que tu donnes pour mettre des fonctions dans mon arbre.

Ce qui est vraiment dommage, c'est que je serai obligé d'écrire une classe pour chaque feuille de mon arbre (si ce sont des fonctions différentes).

Merci pour vos pistes.
Il manque plus que l'aspect générics pour avoir une conversion fidèle des 3 lignes de Caml.