IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Java Discussion :

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


Sujet :

Java

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre éclairé Avatar de Razgriz
    Profil pro
    Professeur / chercheur en informatique / mathématiques
    Inscrit en
    Avril 2006
    Messages
    391
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Professeur / chercheur en informatique / mathématiques

    Informations forums :
    Inscription : Avril 2006
    Messages : 391
    Par défaut 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.

  2. #2
    Membre Expert Avatar de herve91
    Profil pro
    Inscrit en
    Novembre 2004
    Messages
    1 282
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Novembre 2004
    Messages : 1 282
    Par défaut
    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.

  3. #3
    Membre expérimenté
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    194
    Détails du profil
    Informations personnelles :
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations forums :
    Inscription : Juin 2006
    Messages : 194
    Par défaut
    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.

  4. #4
    Membre éclairé Avatar de Razgriz
    Profil pro
    Professeur / chercheur en informatique / mathématiques
    Inscrit en
    Avril 2006
    Messages
    391
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Professeur / chercheur en informatique / mathématiques

    Informations forums :
    Inscription : Avril 2006
    Messages : 391
    Par défaut
    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?

  5. #5
    Membre expérimenté
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    194
    Détails du profil
    Informations personnelles :
    Localisation : France, Ille et Vilaine (Bretagne)

    Informations forums :
    Inscription : Juin 2006
    Messages : 194
    Par défaut
    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 : Sélectionner tout - Visualiser dans une fenêtre à part
    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 : 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
     
    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()] );
    }

  6. #6
    Membre éclairé Avatar de Razgriz
    Profil pro
    Professeur / chercheur en informatique / mathématiques
    Inscrit en
    Avril 2006
    Messages
    391
    Détails du profil
    Informations personnelles :
    Localisation : Belgique

    Informations professionnelles :
    Activité : Professeur / chercheur en informatique / mathématiques

    Informations forums :
    Inscription : Avril 2006
    Messages : 391
    Par défaut
    Mouais, je sais pas trop.
    Sinon je viens de penser à un truc :
    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
    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?

Discussions similaires

  1. Réponses: 2
    Dernier message: 29/06/2007, 10h27
  2. Garder une trace d'enregistrement suprimé
    Par Renardo dans le forum Access
    Réponses: 4
    Dernier message: 12/03/2007, 08h23
  3. Copier un fichier mais garder sa trace VBS
    Par Macandre dans le forum VBScript
    Réponses: 1
    Dernier message: 27/02/2007, 18h22
  4. Garder une trace écrite du stack
    Par Boubou Balrog dans le forum Prolog
    Réponses: 11
    Dernier message: 06/02/2007, 22h03
  5. Garder une trace des fichiers log
    Par Krispy dans le forum Administration système
    Réponses: 2
    Dernier message: 10/05/2006, 19h20

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo