Solution du TD d'informatique No. 6 : arbres et expressions

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 18 décembre 1999

1   Le fichier Arbre.java

public class Arbre {
    String element ;
    Arbre gauche, droit ;
    
    Arbre(String elt) {
        element = elt ;
        droit = gauche = null ;
    }

    Arbre(String elt, Arbre fils) {
        element = elt ;
        gauche = fils ;
        droit = null ;
    }

    Arbre(String elt, Arbre fg, Arbre fd) {
        element = elt ;
        gauche = fg ;
        droit = fd ;
    }
}

2   Le fichier Pile.java

public class Pile {
    Arbre arbre ;
    Pile suivant ;

    Pile(Arbre a, Pile p) {
        arbre = a ;
        suivant = p ;
    }
}

3   Le fichier principal

import java.io.* ;
import java.lang.* ;
import java.util.* ;

public class expressions {
    // Interaction avec l'utilisateur
    /////////////////////////////////
    // Une variable globale pour les entrees/sorties
    static StringTokenizer st ;
    
    // Lire une ligne de texte au clavier
    static void Lire_Ligne(String question) {
        System.out.println(question) ;
        try {
            BufferedReader entree = new BufferedReader(new InputStreamReader(System.in)) ;
            st = new StringTokenizer(entree.readLine()) ;
        }
        catch(java.io.IOException e) {
            System.out.println("Erreur de lecture") ;
            System.exit(0) ;
        }
    }
    
    // Mot suivant de la ligne qui a ete lue
    static String Mot_Suivant() {
        if (st.hasMoreTokens())
            return st.nextToken() ;
        else
            return "" ;    
    }
    
    static boolean Chaines_Egales(String chaine1, String chaine2) {
        return chaine1.compareTo(chaine2) == 0 ;
    }
    
    // Fonction d'erreur
    ////////////////////
    static void Test_Erreur(Boolean b) {
        if (b) {
            System.out.println("Arbre malforme") ;
            System.exit(1) ;
        }
    }
    
    // Lecture des entrees en ordre prefixe et construction de l'arbre
    //////////////////////////////////////////////////////////////////
    static Arbre Lire_Prefixe() {
        String mot = Mot_Suivant() ;
        if (Chaines_Egales(mot, "+") || Chaines_Egales(mot, "-") ||
            Chaines_Egales(mot, "*") || Chaines_Egales(mot, "/") || Chaines_Egales(mot, "^"))
            return new Arbre(mot, Lire_Prefixe(), Lire_Prefixe()) ;
        else if (Chaines_Egales(mot, "sin") || Chaines_Egales(mot, "cos"))
            return new Arbre(mot, Lire_Prefixe()) ;
        else 
            return new Arbre(mot) ;
    }
    
    // Lecture des entrees en ordre postfixe et construction de l'arbre
    ///////////////////////////////////////////////////////////////////
    static Arbre Lire_Postfixe() {
        Pile pile = null ;
        String mot = Mot_Suivant() ;
        while (!Chaines_Egales(mot, "")) {
            if (Chaines_Egales(mot, "+") || Chaines_Egales(mot, "-") ||
                Chaines_Egales(mot, "*") || Chaines_Egales(mot, "/") || Chaines_Egales(mot, "^")) {
                Test_Erreur(pile == null || pile.suivant == null) ;
                pile = new Pile(new Arbre(mot, pile.arbre, pile.suivant.arbre), pile.suivant.suivant) ;
            }
            else if (Chaines_Egales(mot, "sin") || Chaines_Egales(mot, "cos")) {
                Test_Erreur(pile == null) ;
                pile = new Pile(new Arbre(mot, pile.arbre), pile.suivant) ;
            }
            else if (!Chaines_Egales(mot, ""))
                pile = new Pile(new Arbre(mot), pile) ;
            mot = Mot_Suivant() ;
        }
        Test_Erreur(pile == null) ;
        return pile.arbre ;
    }
    
    // Execution du code correspondant a un arbre
    /////////////////////////////////////////////
    static double Executer_Arbre(Arbre arbre) {
        if (Chaines_Egales(arbre.element, "sin"))
            return Math.sin(Executer_Arbre(arbre.gauche)) ;
        if (Chaines_Egales(arbre.element, "cos"))
            return Math.cos(Executer_Arbre(arbre.gauche)) ;
        if (Chaines_Egales(arbre.element, "+"))
            return Executer_Arbre(arbre.gauche) + Executer_Arbre(arbre.droit) ;
        if (Chaines_Egales(arbre.element, "-"))
            return Executer_Arbre(arbre.gauche) - Executer_Arbre(arbre.droit) ;
        if (Chaines_Egales(arbre.element, "*"))
            return Executer_Arbre(arbre.gauche) * Executer_Arbre(arbre.droit) ;
        if (Chaines_Egales(arbre.element, "/"))
            return Executer_Arbre(arbre.gauche) / Executer_Arbre(arbre.droit) ;
        if (Chaines_Egales(arbre.element, "^"))
            return Math.pow(Executer_Arbre(arbre.gauche), Executer_Arbre(arbre.droit)) ;
        return Double.valueOf(arbre.element).doubleValue() ;
    }
    
    // Programme principal
    //////////////////////
    public static void main(String[] args) {
        // Lire une chaine de caracteres et la transformer en un arbre
        Lire_Ligne("Entrer une expression prefixe :") ;
        System.out.println("Le resultat est : " + Executer_Arbre(Lire_Prefixe())) ;
        
        // Lire une chaine de caracteres et la transformer en un arbre
        Lire_Ligne("Entrer une expression postfixe :") ;
        System.out.println("Le resultat est : " + Executer_Arbre(Lire_Postfixe())) ;
    }
}

This document was translated from L^AT_EX by H^EV^EA.