Garder la trace d'un abre appelé récursivement

Version imprimable

19/09/2006, 19h15
Razgriz

Garder la trace d'un abre appelé récursivement

Bonjour,
voilà, j'ai fait un parser qui calcule des expressions du type :

sin(x+2)+e^x*x-7 ...

Ca marche, j'ai un appel résursif fonctionnant comme ceci :
Une expression (cf exemple) est une SOMME de termes, qui sont eux-mêmes un PRODUIT de facteurs, qui sont soit des fonctions de base (réel, sinus(x),...), soit des expressions, et on continue la récursion.

Ca fonctionne bien, mais l'ennui c'est que si je veux par exemple tracer une fonction , je n'ai pas envie de relancer l'appel récursif à partir de l'expression originale, mais plutôt remplacer directement les valeurs des variables dans l'arbre et le remonter en effectuantles opérations décrites par les noeuds, réduisant ainsi nettement la complexité globale du tracage.

Seulement voilà, comment enregistrer l'arbre? Si je veux faire un fichier, je n'ai aucune idée de la manière donc je vais écrire dedans, enfin bref, je suis bloqué là.

Merci d'avance pour votre aide.
19/09/2006, 19h49
herve91

Bonjour,

Citation:

Envoyé par Razgriz

Seulement voilà, comment enregistrer l'arbre? Si je veux faire un fichier, je n'ai aucune idée de la manière donc je vais écrire dedans, enfin bref, je suis bloqué là.

Une idée... Si ton arbre implémente l'interface Serializable, tu peux l'enregistrer avec ObjectOutputStream.writeObject() et le relire avec ObjectInputStream.readObject()
Je ne sais pas si cela répond à ta question.
20/09/2006, 10h44
had35

Si j'ai bien compris, le parcours de ton arbre permet d'identifier les opérations à effectuer. Je ne sais pas sous quelle forme ces opérations sont représentées ni de quelle façon cette représentation est exploitée, mais normalement le résultat de la récursion doit pouvoir se présenter sous la forme d'un tableau unique pour ta fonction.
20/09/2006, 11h30
Razgriz

Ben ouais je sais qu'on peut écrire l'arbre si c'est Serializable, mais comment implémenter ledit arbre? C'était ma véritable question...

Sinon pour le si c'est représentable sous forme d'un tableau unique, comment je fais pour l'obtenir?

Citation:

Envoyé par Razgriz

Sinon pour le si c'est représentable sous forme d'un tableau unique, comment je fais pour l'obtenir?

Ton arbre devrait être constitué de noeuds et de feuilles (éléments finaux). Le tableau représentant le résultat d'une récursion est un tableau de feuilles.

Méthode récursive
Code:

1 2 3 4 5 6 7 8 9 10 11 ArrayList<Node> fonction; public Node parcourir(Node nod) { Node[] tab = nod.getChildren(); for(Node current : tab) { if( current.isLeaf() ) fonction.add(current); else parcourir(current); } }
Méthode itérative (permet de mieux contrôler l'ordre d'ajout)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 public Node[] parcourir(Node nod) { ArrayList<Node> fonction; ArrayList<Node> composites; composites.add(nod); while( composites.size() > 0) { Node[] children = composites.get(composites.size()-1).getChildren(); for(Node current : children) { if( current.isLeaf() ) fonction.add(current); else composites.add(current); } composites.remove(composites.size()-1); } return fonction.toArray( new Node[fonction.size()] ); }

Mouais, je sais pas trop.
Sinon je viens de penser à un truc :

Code:

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
 
/*
 * Tree.java
 *
 * Created on 20 septembre 2006, 17:25
 *
 * To change this template, choose Tools | Template Manager
 * and open the template in the editor.
 */
 
package evaluator;
 
import java.io.Serializable;
import java.util.ArrayList;
 
/**
 * This class models a node, component of a tree created by recursive call.
 * A node has a father unless it is the first element of the tree, and some 
 * children unless it is a leaf (one of the lasts elements of the tree). A node 
 * also contains data witch are significative for itself, and and operation to
 * apply between the children, e.g. +,* ,^, &&, and so on.
 * @see evaluator.Evaluator
 * @see evaluator.Expression
 * @see evaluator.Term
 * @see evaluator.Factor
 * @author Absil Romain
 */
public class Node implements Serializable
{
 
    private String operation;
    private Node father;
    private ArrayList<Node> children;
    private Object data;
 
    /**
     * Creates an instance of Node.
     * @param operation the operation associated to the node.
     * @param father the father of the node, enter null if it id the root of 
     * the tree.
     * @param data the significative contained data.
     **/
    public Node(String operation, Node father, Object data)
    {
        this.operation = operation;
        this.father = father;
        children = new ArrayList<Node>();
        this.data = data;
    }
 
    /**
     * Returns the operation asociated to the node.
     * @return the operation asociated to the node.
     **/
    public String getOperation()
    {
        return operation;
    }
 
    /**
     * Returns the father of the node, return null if it is the root of the tree.
     * @return the father of the node, return null if it is the root of the tree.
     **/
    public Node getFather()
    {
        return father;
    }
 
    /**
     * Returns the children of the node; a void {@link java.util.ArrayList} if 
     * it is a leaf.
     * @return the children of the node; a void {@link java.util.ArrayList} if 
     * it is a leaf.
     **/
    public ArrayList<Node> getChildren()
    {
        return children;
    }
 
    /**
     * Returns the data of the node.
     * @return the data of the node.
     **/
    public Object getData()
    {
        return data;
    }
 
    /**
     * Sets the data of the node.
     * @param data the new data.
     **/
    public void setData(Object data)
    {
        this.data = data;
    }
 
    /**
     * Returns true if the node is the root, i.e. if its father is null, returns 
     * false otherwise.
     * @return true if the node is the root, i.e. if its father is null, returns 
     * false otherwise.
     **/ 
    public boolean isRoot()
    {
        return father == null;
    }
 
    /**
     * Returns true if the node is a leaf, i.e. if it has no children.
     * @return true if the node is a leaf, i.e. if it has no children.
     **/
    public boolean isLeaf()
    {
        return children.size() == 0;
    }
}

Ca me semble plus simple, de là il est facile d'à partir des feuilles de remonter jusqu'en haut de l'arbe et de faire ce qu'on voulait.
Est-ce une bonne approche néanmoins?

20/09/2006, 18h22
Razgriz

Ca fait fort liste chainée ma décomposition d'arbe, et du point de vue consomation de mémoire ça doit faire mal sur une grosse expression, je me demande à partir de quand ça fait planter la machine virtuelle...
20/09/2006, 18h26
Razgriz

Pour être clair par rapport aux questions de had35, j'ai par exemple une expression du type 3+2*cosh(sin(e^x+2*y))+9/arctg(z^2) et je voudrais calsuler sa valeur. Les opérations sont donc +,-,*,/ (autant d'entrées que l'on veut), les fonctions de base (e.g. sin) à une seule entrée, et les feuilles sont les doubles et les variables.

On sait calculer directement l'expression sans arbre, je l'ai fait, mais je me rends compte que dans mon cas, càd pour un traceur de fonctions de R -> R, je fais des trucs inutiles.
Je m'explique, je mets un repère sur ma fonction, et je prend je premier pixel à gauche de l'écran. Je trouve sa véritable abscisse sur le repère, j'en calsule l'ordonnée par la fonction. Ensuite j'obtiens l'ordonnée sur la fenêtre (en pixel) et je met un point. Ensuite je fais de même pour le point suivant, et je traceune ligne droite entre les deux points, et ainsi de suite. Ca fonctionne bien entendu sans l'arbre avec le parseur "tout bête" qui calcule directement les images.
MAIS si j'ai une fenêtre de 1024 pixels en large, je vais devoir faire 1024 appels récursifs, à chaque fois que je change la valeur de la variable (i.e. quand je passe au pixel suivant), et ça c'est pas cool.
L'astuce était donc de garder une empreinte de mon arbre, par exemple en le sérialisant, et de ne remplacer les variables par leur valeur que dans les feuilles, on limite ainsi la complexité car on parcourt l'arbre une fois en descente, lors de sa création, au lieu de 1024 fois avec le parseur. Pour la remontée de l'arbre ça on a pas le choix c'est 1024 tous les deux.

Voilà donc tout mon problème, mais je pense que avec la petite classe que j'ai posté ça devrait aller beaucoup mieux pour implémenter l'arbre.
20/09/2006, 21h29
herve91

La classe que tu proposes me semble tout à fait appropriée pour modéliser un arbre. Maintenant, si cela t'ennuie d'avoir à parcourir ton arbre 1024 fois, il existe d'autres représentations internes moins coûteuse en mémoire, par exemple tu peux représenter ta fonction en notation post-fixée :

Citation:

3+2*cosh(sin(e^x+2*y))+9/arctg(z^2)

devient

Citation:

(3) (2) (x) [exp] (2) (y)[*] [+] [sin] [cosh][*] [+] (9) (z) [sqr] [arctg] [/] [+]

entre parenthèses se trouvent les opérandes, entre crochets les opérateurs.
Une liste devrait suffire pour contenir les opérandes et opérateurs. Pour l'évaluation d'une expression post-fixée, il faut utiliser une pile.
20/09/2006, 23h53
Razgriz

Je suis de toute façon obligé de remonter mon arbre 1024 fois, simplemetn parce que je dois calculer 1024 images de pixels. On ne peut pas y échapper.

Citation:

Envoyé par Razgriz

Je suis de toute façon obligé de remonter mon arbre 1024 fois, simplemetn parce que je dois calculer 1024 images de pixels. On ne peut pas y échapper.

Oui, c'est sûr, tu devras en effet recalculer ton expression 1024 fois ;)
Le mode de représentation que te propose herve91 te permet d'utiliser une pile.

Dans le même ordre d'idée, le tableau que je te proposais de créer repose sur le même principe, mais on garde l'avantage d'avoir déjà identifié les éléments de ta fonction (opération, constantes, variables, marquage de début et de fin). C'est un peu différent de ce que tu as fais car si j'ai bien compris, les opérations sont représentés par les noeuds de ton arbre. Mais ça ne devrais pas poser de problème, il faudrait ajouter des éléments aussi pour les composites.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 public enum ElementType { DEBUT, OPERATION, VARIABLE, CONSTANTE, FIN } public interface Element { public ElementType getType(); } public class Operation implements Element{ private ElementType type; private int id; public int getId() { } }
Tout n'est pas définit, mais l'idée c'est que tu aurais juste besoin de parcourir ton tableau et d'utiliser une pile pour le calcul du résultat. Le parcours est linéaire, je pense que c'est plus efficace que de parcourir un arbre.

22/09/2006, 10h14
Razgriz

Bon, je vais essayer d'être clair, je comprend rien à ce que tu essaies de me dire had35:oops:
J'suis p'tet tout simlement con:lol:
22/09/2006, 11h20
had35
Citation:

Envoyé par Razgriz

Bon, je vais essayer d'être clair, je comprend rien à ce que tu essaies de me dire had35:oops:
J'suis p'tet tout simlement con:lol:

Non, c'est moi :mouarf:
Je me doutais bien que je n'avais pas été très clair.

L'idée générale, c'est qu'il est possible de réprésenter une fonction quelconque sous la forme d'une séquence d'opérations unique pour la fonction (dixit Turing). Ca c'est pour la théorie. On peut mettre cela en pratique en utilisant une pile (Stack) et en incluant dans la séquence des opérations sur la pile (pick, pop, push) pour tenir compte de la priorité de certaines opérations.

Dans ton cas, comme tu pars d'un arbre, il faut le transformer pour obtenir cette fameuse séquence. En gros :
Code:

1 2 3 4 5 6 R / \ A Z / \ / \ B C Y X
(Je ne suis pas sûr de l'apparence : R est le root, A et B ont R comme parent, B et C ont A comme parent, X et Y ont Z comme parent)

Pour transformer cet arbre en une séquence d'opération, il faut ordonner B, C, Y et X pour tenir compte de l'ordre de priorité des opérations.

On suppose ici que l'arborescence représente justement cette priorité où A est la somme de B et C, Z la somme de Y et X, et R le produit de A et Z.

La séquence se présentera à peu près comme ça :

Citation:

ajouter B à la pile de calcul
remplacer B par la somme de B et C
ajouter Y à la pile
remplacer Y par la somme de Y et X
extraire Y de la pile
remplacer X par le produit de X et Y
...

C'est cette séquence qu'il faut représenter dans un tableau. Chaque instruction de la séquence est un élément du tableau. Les éléments peuvent être des opérations mathématiques, des constantes, des variables ou des opérations sur la pile. Ce sont ces dernières opérations qui sont les moins évidentes à représenter. Je proposais au début de le faire avec un élément de début et de fin pour chaque opération mathématique. On peut aussi le faire de façon plus directe (extraire, lire ou remplacer le dernier élément de la pile, et ajouter un élément).

Pour les variables, il faudra les stocker dans un tableau dédié et les identifier par leur position dans ce tableau de variables.

Enfin, on utilise ensuite une structure switch/case ou if/elseif pour interpréter la séquence.

C'est mieux ? :mouarf:
22/09/2006, 13h18
Razgriz

Ouais ça va j'ai compris ;-).
Je vais implémenter ça et puis je verrai lequel des deux algorithmes va le plus vite.
22/09/2006, 14h28
had35
Citation:

Envoyé par Razgriz

Je vais implémenter ça et puis je verrai lequel des deux algorithmes va le plus vite.

Pour améliorer la performance, le mieux serait d'avoir un tableau de primitives plutôt qu'un tableau d'objets. Il faudrait donc définir un code avec par exemple :

opérations arithmétiques
addition : '+'
soustraction : '-'
etc...

opérations sur la pile
remove : 256
push : 257
etc...

nombres
1. bourrin
chiffre 0 : 0
chiffre 1 : 1
etc...
chiffre 9 : 9
virgule : 10
1. mieux (on suppose ici que les éléments sont des char)
élément<2^16 : (int)élément
2^16<élément<2^32 : (int)élément*2^16+(int)élément_suivant

Pour le dernier cas, je fais ça de tête, c'est à vérifier. L'idée est qu'on représenterait les nombres supérieurs à Character.MAX_VALUE sur trois char. Un pour préciser qu'il s'agit d'un int, les deux suivant pour coder. Et on concatène les deux derniers char (2*16bits) pour former un int (32bits)

Bien entendu, tout cela nécessite de définir très rigoureusement la syntaxe.
22/09/2006, 14h50
Razgriz

pas maaaaaaaaaal comme idée...:D
Aves les opérations je vais chier pour toutes les représenter sur un char, et pour m'en souvenir dans l'implémentation avec des fonctions comme sin, arctg, cosec,...