Exercice piles d’entiers – structures de données abstraites

[tab name=’Exercice java’]

Dans cet exercice, vous allez coder des piles d’entiers de deux

Vous utiliserez ensuite cette structure de données pour interpréter des opérations arithmétiques en notation polonaise inverse (c’est-à-dire notation « postfixée »).

Il existe plusieurs façons de coder la structure de données abstraite « pile ». Nous allons en voir deux classiques.

La spécification des fonctionalités associée à cette structure peut en fait se faire indépendamment de la réalisation choisie.

Nous allons utiliser ici la notion d’interface pour décrire ces spécifications (correspondant à la définition formelle d’une pile). Notez que la spécification est partielle ici et peut-être enrichie par d’autres méthodes (pour faire la comparaison ou la copie de piles par exemple).

Spécification d’une pile d’entiers

Dans un fichier Pile.java, codez une interface Pile dont la spécification est la suivante:

• Modificateurs (abstraits):
  • public void effacer(): vide la pile
  • public void empiler(int element): empile element dans la pile.
  • public void depiler() dépile l’élément au sommet de la pile.
• Sélecteurs (abstraits):
  • public boolean isPileVide() testant si la pile est vide
  • public int sommet() retournant la valeur du sommet de la pile

Cette description formelle étant faite, on peut maintenant coder des réalisations de la structure de données « pile » implémentant l’interface précédente. Rappellez-vous que toutes les méthodes définies par l’interface sont forcément abstraites. Les classes implémentant cette interface sont donc dans l’obligation de définir ces méthodes.

Réalisation d’une pile au moyen d’un tableau

Codez une classe PileParTableau implémentant l’interface précédente et réalisant la pile au moyen d’un tableau de taille fixe. Les attributs associés à cette classe seront:

• une taille maximale pour le tableau stockant les éléments de la pile
• un tableau d’entiers destiné à stocker les éléments de la pile
• un entier sommet donnant l’indice du tableau correspondant au sommet de la pile (initialisé à -1 par exemple)

Vous associerez à votre classe un constructeur prenant en paramètre la taille maximale associée à la pile. Puis vous la doterez de l’ensemble des méthodes spécifées par l’interface.

Important: en Java, les méthodes implémentant des méthodes abstraites d’une interface doivent être explicitement déclarées comme étant publiques dans leurs classes. En effet, comme les méthodes abstraites d’une interface sont par définition publiques, le compilateur exige par sécurité de rendre explicitement publiques les méthodes les implémentant.

Par ailleurs, pour traiter proprement les situations de fonctionnement anormal de la pile (débordement, dépilement d’une pile vide etc..) il faudrait en toute rigueur utiliser la notion d’exceptions que vous verrez au semestre d’été. Pour l’instant contentez-vous de signaler ces situations par un message d’erreur et arrêtez l’exécution du programme au moyen de l’instruction System.exit(-1).

Réalisation d’une pile chaînée

En vous inspirant de l’exercide de Niveau 0, implémentez maintenant la pile de façon chainée: vous définirez une classe Noeud (une case de la pile) dont les attributs seront valeur et dessous (le noeud au dessous du noeud courant). En utilisant cette classe Noeud vous définirez la classe PileParChaine implémentant l’interface Pile et fournissant les méthodes nécessaires.

Application: piles et notation polonaise inverse

Description

On veut faire un programme qui interprète les opérations arithmétiques en notation polonaise inverse (c’est-à-dire notation « postfixée »).

Cette notation consiste à donner tous les arguments avant l’opération.

Par exemple : 4+3 s’écrit 4 3 +. De même : (4 * 5) + 3 s’écrit 4 5 * 3 +

Notez qu’avec ce système de notation il n’y a pas besoin de parenthèse. Il suffit d’écrire les opérations dans le bon sens.

Par exemple : (4+3)*(3+2) s’écrit 4 3 + 3 2 + * alors que 4 + (3*3) + 2 s’écrit 4 3 3 * + 2 +

Méthode

L’algorithme pour effectuer des opérations données en notation postfixée est le suivant, où P est une pile :

Tant que lire caractère c
  Si c est un opérande
     empiler c sur P
  Sinon
     Si c est un opérateur
        y <- sommet(P)
        dépiler P
        x <- sommet(P)
        dépiler P
        empiler le resultat de "x c y" sur  P

A la fin de cet algorithme, le résultat est au sommet de P.

A faire

Dans cette série nous allons simplement nous intéresser aux opérations sur les chiffres : les seuls opérandes seront les chiffres de 0 à 9.
Par exemple : 14+ veut dire 1 + 4. On pourra bien entendu aussi noter avec des espaces : 1 4 + si on le souhaite. Dans le fichier PolonaiseInverse.java:

1. Définissez la méthode statique eval qui prend en entrée une chaine de caractères (String) et renvoie un entier, résultat de l’expression postfixée contenue dans la chaine.Cette méthode devra implémenter l’algorithme ci-dessus, et utilisera donc une pile d’entiers (vous pouvez choisir n’importe laquelle des réalisation codées ci-dessus, vous testerez avec les deux).
2. Dans la méthode main, lisez une chaine de caractères au clavier (correspondant à une opération arithmétique en notation postfixée) et évaluez-là à l’aide de la méthode précédente, puis affichez le résultat.La méthode main bouclera tant que la chaine entrée n’est pas vide (voir l’exemple ci-dessous).

Indications

Pour tester qu’un caractère (char) c est un chiffre :

    if ((c >= '0') && (c <= '9'))

Pour convertir un caractère c représentant un chiffre en sa valeur entière (par exemple convertir '3' en 3) :

    (int)(c - '0')

!! Attention !!

Les indications précédentes font l’hypothèse que les chiffres utilisés sont les chiffres arabes tels qu’utilisés en Occident. Il n’y a toutefois aucune garantie que ce soit le cas dans le cas général! Ce sont souvent des petites choses implicites comme ça qui posent le plus de problèmes lorsque ce qui n’était censé être qu’un prototype a plus de succès qu’imaginé initialement.

En empiétant un peu sur le prochain cours, c’est toujours une bonne idée d’utiliser les fonctions fournies, parce qu’elles sont plus susceptibles de tenir compte de ce genre de détails obscurs. Le code recommandé devient donc:

Pour tester qu’un caractère (char) c est un chiffre :

    if (Character.isDigit(c))

Pour convertir un caractère c représentant un chiffre en sa valeur entière (par exemple convertir '3' en 3) :

  Integer.parseInt(Character.toString(c))

Exemple de déroulement

Entrez une expression à évaluer : 8 6 2 - / 3 +
 -> résultat : 5
Entrez une expression à évaluer : 4 3 + 3 2 + *
 -> résultat : 35
Entrez une expression à évaluer : 4 3 3 * + 2 +
 -> résultat : 15
Entrez une expression à évaluer :

[/tab][tab name=’Correction’]

L’ interface « Pile »:

/**
 * Spécification formelle de la SDA au moyen d'une interface
 */
interface Pile {
    // Modificateurs

    /** Effacer tous les éléments */
    public void effacer();

    /** Empiler une valeur au sommet de la pile */
    public void empiler(int element);

    /** Dépiler la valeur du sommet de la pile */
    public void depiler();

    // Sélecteurs

    /** Teste si la pile est vide */
    public boolean isPileVide();

    /** Retourne la valeur du sommet de la pile */
    public int sommet();
}

La solution présentée ici implémente la pile au moyen d’un tableau statique:

/**
 * La classe implémentant la SDA au moyen d'un tableau statique
 */
class PileParTableau implements Pile {
    private int tailleMax = 1000;   // Taille maximale
    private int sommet = -1;        // Sommet du tableau
    private int[] tableau;

    // Constructeur: crée une pile vide de taille maximale donnée
    public PileParTableau(int max) {
        tailleMax = max;
        sommet = -1;
        tableau = new int [tailleMax];
    }

    // Modificateurs

    /** Effacer tous les elements   */
    public void effacer() {
        sommet = -1;
    }

    /** Empiler */
    public void empiler(int element) {
        if (sommet == tailleMax - 1) {
            System.out.println("Impossible d'empiler: la pile est pleine");
            System.exit(-1); // A remplacer impérativement par un traitement
                             // d'exceptions, dès que vous connaitrez cette notion!!
        }

        sommet++;
        tableau[sommet] = element;
    }

    /** Dépiler */
    public void depiler() {
        if (isPileVide()) {
            System.out.println("Impossible de desempiler: la pile est vide");
            System.exit(-1); // A remplacer impérativement par un traitement
                             // d'exceptions, dès que vous connaitrez cette notion!!
        }

        sommet--;
    }

    // Sélecteurs

    /** Teste si une pile est vide */
    public boolean isPileVide() {
        return (sommet == -1);
    }

    /** Retourne la valeur du sommet */
    public int sommet() {
        if (isPileVide()) {
            System.out.println("Impossible de donner la valeur du sommet: la pile est vide");
            System.exit(-1); // A remplacer impérativement par un traitement
                             // d'exceptions, dès que vous connaitrez cette notion!!
        }

        return tableau[sommet];
    }

}

Et par une chaine:

class PileParChaine implements Pile {

    /** Base de la pile */
    private Node root = new Node(null, 0);

    /** Sommet de la pile */
    private Node sommet = root;

    /**
     * Effacer tous les éléments
     */
    public void effacer() {
        sommet = root;
    }

    /**
     * Empiler une valeur au sommet de la pile
     */
    public void empiler(int element) {
        Node newTop = new Node(sommet, element);
        sommet = newTop;
    }

    /**
     * Dépiler la valeur du sommet de la pile
     */
    public void depiler() {
        if (sommet == root) {
            System.out.println("La pile est vide");
            System.exit(-1);
        } else

        sommet = sommet.getPreviousElement();
    }

    /**
     * Teste si la pile est vide
     */
    public boolean isPileVide() {
        return (sommet == root);
    }

    /**
     * Retourne la valeur du sommet de la pile
     */
    public int sommet() {
        return sommet.getValue();
    }

}

/**
 * Cette classe implémente un noeud dans la liste chainee de la classe PileParChaine.
 * Chaque noeud contient un entier comme donnée utile.
 */
class Node {

    private int value;

    private Node previousElement;

    public Node(Node previousElement, int value) {
        this.previousElement = previousElement;
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public Node getPreviousElement() {
        return previousElement;
    }

}

Application: piles et notation polonaise inverse

import java.util.Scanner;
class PolonaiseInverse {
    private static Scanner scanner = new Scanner(System.in);
    public static void main(String[] args) {
        String s;

        do {
            System.out.print("Entrez une expression à évaluer : ");
            s = scanner.nextLine();
            if (!(s.length() == 0)) {
                System.out.println(" -> résultat : " + eval(s));
            }
        } while (!(s.length() == 0));
    }

    static int eval(String s) {
        Pile p = new PileParTableau(100);

        // Recopie dans la pile
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if ((c >= '0') && (c <= '9')) {
                // On a lu un opérande
                p.empiler((int) (c - '0'));
            } else if ((c == '+') || (c == '-') || (c == '*') || (c == '/')) {
                // On a lu un opérateur

                // Récupère le second argument
                int y = 0;
                int x = 0;
                if (!p.isPileVide()) {
                    y = p.sommet();
                    p.depiler();
                } else {
                    System.out.println("Expression incomplète");
                    return 0;
                }

                // Récupère le premier argument
                if (!p.isPileVide()) {
                    x = p.sommet();
                    p.depiler();
                } else {
                    System.out.println("Expression incomplète");
                    return 0;
                }

                // Calcule et empile le résultat
                int n = 0;
                switch (c) {
                case '+':
                    n = x + y;
                    break;
                case '-':
                    n = x - y;
                    break;
                case '*':
                    n = x * y;
                    break;
                case '/':
                    n = x / y;
                    break;
                }
                p.empiler(n);
            }
        }

        return p.sommet();
    }

}

[/tab][end_tabset skin= »ginger » ]