Première partie

Objectifs d'apprentissage

  • Reconnaître les situations où une pile est nécessaire pour la conception d'un algorithme.
  • Décrire l'implémentation d'une pile à l'aide d'un tableau.
  • Implémenter une pile à l'aide d'un tableau dynamique.
  • Implémenter un type interface prédéfini.
  • Appliquer le concept de type générique pour l'implémentation de classes et d'interfaces.

Piles (Stack)

Introduction

Les piles font partie des méthodes de structure de données utilisées couramment en programmation. Il existe plusieurs manières de les implémenter. Pour ce faire, vous devez toutefois bien comprendre leur comportement. Avant tout, les piles respectent le principe de last-in first-out ou LIFO(dernier entré premier sorti). Entre d'autres mots, vous empilez des éléments un par-dessus les autres. Vous ne pouvez uniquement accéder les éléments du dessous si vous retirez tous les éléments du dessus.Au quotidien, vous êtes entourés d'objets et d'évènements qui suivent le principe des piles.

Voici une série d'exemples de la vie courante. Déterminez s'il s'agit d'exemple valable (vrai) où une pile est utilisée ou non (faux).

Question 1.1 :

Les balles de tennis dans leur contenant

Réponse
Question 1.2 :

Les étudiants sur la liste d’attente d’admission en génie

Réponse
Question 1.3 :

Une pile d’assiettes dans votre armoire

Réponse
Question 1.4 :

Les balles dans un fusil

Réponse
Question 1.5 :

L’évaluation d’expressions postfixes

Réponse
Question 1.6 :

Un contenant de chips Pringles

Réponse
Question 1.7 :

Un poste de péage

Réponse
Question 1.8 :

Le bouton «Précédent» dans votre fureteur (« Browser »)

Réponse

Application

Cette partie du laboratoire porte sur deux des trois implémentations de l'interface Stack. Il s'agit de deux implémentations lesquelles vous serez évalués à l'examen de mi-session.

1.1 Modifier l'interface Stack : ajout d'une méthode clear()

Modifiez l'interface Stack ci-bas afin d'y ajouter la méthode abstraite public void clear().

public interface Stack<E> { 
    boolean isEmpty(); 
    E peek(); 
    E pop(); 
    void push(E element); 
}
Fichier :

1.2 Implémenter la méthode clear() de la classe ArrayStack

La classe ArrayStack utilise un tableau de taille fixe et réalise l'interface Stack. Puisque l'interface Stack a été modifiée afin d'y ajouter la méthode clear(), l'implémentation de la classe ArrayStack est défectueuse (essayez d'abord de la compiler sans y apporter de changement, quel message d'erreur est affiché à l'écran ?).

Puisque la classe ArrayStack réalise l'interface Stack, elle doit fournir une implémentation pour toutes les méthodes de l'interface. Ainsi, vous devez écrire une méthode void clear(). Cette dernière retire tous les éléments de cette pile (ArrayStack). La pile sera vide suite à cet appel. Utilisez la classe L6Q1 pour tester votre implémentation de la méthode clear.

Fichiers :

1.3 Créer une nouvelle classe DynamicArrayStack

Modifier la classe ArrayStack afin qu'elle utilise le principe de tableau dynamique. Cette nouvelle classe DynamicArrayStack possède une constante DEFAULT_INC de valeur 25. Lorsque votre tableau est plein, un nouveau tableau avec DEFAULT_INC plus d'éléments sera créé et rempli avec les éléments du tableau précédent. Par ailleurs, à l'inverse, lorsqu'un tableau possède DEFAULT_INC éléments de moins que sa taille, ce dernier doit automatiquement être rapetissé. Faites les ajustements nécessaires, notamment dans peek, push, clear et les constructeurs (la taille minimale d'un tableau est de DEFAULT_INC).s

 

Deuxième partie

Les expressions postfixes

Introduction

Les expressions postfixes sont un exemple d'application des piles. Tel que vu en classe, il s'agit d'une méthode où l'on empile (push) les opérandes de l'expression jusqu'à ce que l'on rencontre un opérateur. À ce moment, on retire (pop) les deux éléments précédents, des opérandes. On effectue l'opération et on empile ensuite le résultat dans la pile avec les autres opérandes. À la fin de la lecture de l'expression, il ne devrait nous rester qu'un élément, soit un nombre dans notre pile.

Prenons l'expression postfixe: 5 2 - 4 *

  1. D'abord, on lit l'expression de gauche à droite. Il s'agit de nombres qui serviront d'opérandes, donc on les empile: Bottom [5 2
  2. À la rencontre d'un opérateur, ici « - », on retire 2 opérandes de la pile 2 et 5 respectivement. On effectue l'opération. Notez que l'ordre est important, le second élément retiré « 5 » moins « - » le premier élément retiré « 2 ». On empile ensuite le résultat « 3 » à la pile (n'oubliez pas que 5 et 2 ont été retirés). Bottom [3
  3. Le prochain élément est « 4 ». Comme il s'agit d'un nombre, on l'empile: Bottom [3 4
  4. Enfin, on lit « * ». Comme il s'agit d'un opérateur (multiplication), on retire les deux éléments du dessus, 4 et 3 respectivement. On effectue l'opération « 3 * 4 » et on empile le résultat. Bottom [12
  5. Nous avons utilisé tous les éléments de notre expression postfixe et il ne nous reste qu'une valeur dans notre pile. « 12 » est donc le résultat de notre expression!

Note: Si vous rencontrez un opérateur dans votre expression et qu'il n'y a pas 2 nombres (opérandes) sur le dessus de votre pile, l'expression postfixe est invalide. Il va de même si vous avez plus d'un nombre dans votre pile à la fin de la lecture de votre expression!

Pratiquez-vous! Ce concept peut faire partie de votre examen de mi-session!

Voici une série d'exercices simples. Assurez-vous de bien comprendre comment lire des expressions postfixes et aussi de convertir une expression arithmétique en expression postfixe.

Question 2.1 :

Convertissez l'expression suivante en expression postfixe: 5 * 3 + 5

Réponse
Question 2.2 :

Convertissez l'expression suivante en expression postfixe: 4 - 6 / 3 * 2

Réponse
Question 2.3 :

Évaluez l'expression postfixe suivante (trouvez le résultat): 9 2 * 6 / 2 3 * +

Réponse
Question 2.4 :

Évaluez l'expression postfixe suivante (trouvez le résultat): 4 2 8 * - + 7 +

Réponse

Application

2.1 Algo1

Pour cette partie du laboratoire, il y a deux algorithmes pour la validation d'expressions contenant des parenthèses (rondes, frisées et carrées).

La classe Balanced ci-dessous présente le premier algorithme algo1, une version simple pour valider des expressions. On remarque qu'une expression bien formée est telle que pour chaque type de parenthèses (les rondes, les frisées et les carrées), le nombre de parenthèses ouvrantes est égal au nombre de parenthèses fermantes. D'où l'algorithme suivant :

public static boolean algo1(String s) { 
 
	int curly, square, round; 
 
	curly = square = round = 0; 
 
	for (int i=0; i < s.length(); i++) { 
 
		char c; 
		c = s.charAt(i); 
 
		switch (c) { 
			case ’{’: 
				curly++; 
				break; 
			case ’}’: 
				curly--; 
				break; 
			case ’[’: 
				square++; 
				break; 
			case ’]’: 
				square--; 
				break; 
			case ’(’: 
				round++; 
				break; 
			case ’)’: 
				round--; 
		} 
	} 
 
	return curly == 0 && square == 0 && round == 0; 
}

Compilez ce programme et expérimentez. D'abord, assurez-vous qu'il fonctionne pour des expressions valides, telles que “()[]()”, “([][()])”. Vous remarquerez que l'algorithme fonctionne aussi pour des expressions qui contiennent des opérandes et des opérateurs : “(4 * (7 - 2))”.

Ensuite, vous devez trouvez des expressions pour lesquelles l'algorithme retourne true bien que ces expressions ne sont pas bien formées.

Fichier

5. Algo2

Vous avez trouvé des expressions qui font échec à cet algorithme. Très bien ! En effet, une expression bien formée est une expression telle que le nombre de parenthèses ouvrantes et fermantes est le même, et ce, pour chaque type de parenthèses. Mais aussi, lorsqu’on lit une telle expression de gauche à droite et que l’on rencontre une parenthèse fermante alors son type doit être le même que celui de la dernière parenthèse ouvrante rencontrée qui n’a pas encore été traitée (associée). Par exemple, « (4 + [2 - 1)] » n'est pas valide!

Vous devez implémenter un algorithme à base de pile afin de valider des expressions : retourne true si l’expression est bien formée et false sinon. De plus, l’analyse ne devrait parcourir la chaîne qu’une seule fois. Vous devez créer votre implémentation dans la class Balanced, nommez cette méthode algo2. (La solution modèle a 15 lignes !)

Faites plusieurs tests à l’aide d’expressions valides et non valides. Assurez-vous que votre algorithme traite ce cas-ci : “((())” ? Comment traitez-vous ce cas-ci ?

 

Troisième partie

Structures de données génériques

Il est possible d'utiliser des types génériques afin d'implémenter des classes ou des interfaces. Ces dernières pourront être réutilisées dans plusieurs contextes, soit avec des types paramétrés (le type réel). Rappelez-vous de l'interface Comparable! En utilisant le principe de type générique, on s'assure aussi de conserver une validation par le compilateur.

3.1 Implémenter l'interface Map

Définir l'interface Map. Une classe qui réalise Map doit sauvegarder des associations clé-valeur (key-value). Dans notre cas, nous souhaitons qu’une Map puisse contenir des clés (key) identiques, dans lequel cas les méthodes get, put, replace et remove feront référence à la l’association contenant cette clé se trouvant la plus à gauche (la dernière). Map est une classe générique avec deux types de paramètres, K et V, où K est le type des clés (keys) et V le type des valeurs (values). Une Map possède les méthodes suivantes :

  1. V get(K key) : retourne la valeur la plus à gauche (lefmost value) associée avec la clé spécifiée en paramètre.
  2. boolean contains(K key) : retourne true s’il existe une association pour la clé spécifiée en paramètre.
  3. void put(K key, V value) : crée une nouvelle association key-value.
  4. void replace(K key, V value) : remplace la valeur associée à l’association la plus à gauche possédant la clé spécifiée en paramètre (replaces the value of the leftmost occurrence of the association for the specified key)
  5. V remove(K key) : retire l’association la plus à gauche possédant la clé spécifiée et retourne la valeur qui était associée à cette clé.

Notez qu’aucun paramètre ne peut être null dans chacune de ces méthodes.

3.2 Implémenter la classe Dictionary

Dictionary garde la trace des associations String-Integer (key-value).

  • La classe Dictionary réalise (implements) l’interface Map <String,Integer >.
  • Elle utilise un tableau (première variable d'instance) pour stocker chaque association. Les éléments de ce tableau sont de type Pair, une classe imbriquée qui sera privée et statique (private static). Un objet de type Pair doit stocker une association, « key » et « value », de type String et Integer respectivement.
  • Vous devez traiter votre tableau d'éléments comme une pile. Ainsi, le bas de votre pile sera l'élément 0, tandis que le dessus de la pile sera l'élément non-null à la position la plus élevée. Utilisez un compteur (seconde variable d'instance) qui vous indiquera combien d'éléments sont dans votre tableau.
  • Finalement, comme la classe Dictionary stocke une quantité arbitrairement large d’associations, vous devrez utiliser la technique de tableau dynamique (comme présenté dans la partie 1). La taille initiale du tableau sera de 10, tandis que son incrément sera de 5 à chaque fois que le tableau est plein. Ces deux valeurs seront traitées comme des constantes.
  • Vous devez évidemment implémenter toutes les méthodes de l'interface. N'oubliez pas de considérer que l'association (élément de type Pair) la plus à gauche sera toujours celle qui est la plus au dessus de la pile! Vous devrez donc parcourir votre tableau en sens inverse.
  • Ajoutez une méthode toString qui imprime les éléments de votre tableau du dernier au premier (haut de la pile au bas de la pile).
  • DictionaryTest.java comprend une série de tests pour votre implémentation.

 

Quatrième partie

Questions de revue

Voici quelques questions qui peuvent vous aider à vous préparer pour votre examen de mi- sessions

  1. Vrai ou Faux

    1. Dans les énoncés si dessous, indiquez si Vrai ou Faux, la conversion (cast) de ces types primitifs peut se faire sans possibilité de perte d’information.
      1. De int à double
      2. De int à short
      3. De byte à int
      4. De long à int
    2. Une classe en Java ne peut implémenter qu’une interface
    3. Les opérations arithmétiques *, /, % , + et – ont la même ordre de priorité.
    4. Les noms de variables en Java sont sensibles à la casse (case-sensitive)
    5. Une classe a toujours un constructeur (possiblement fournie automatiquement par le compilateur Java)
    6. Le nom d’une variable d’instance ne peut avoir que des chiffres et des lettres.
  2. Quelle est la sortie du programme suivant:
    public class TestMeth {
    
        private static int i = 1;
    
        public static void main(String args[]) {
            System.out.println(i+” , “);
            m(i);
            System.out.println(i);
        }
        
        public void m(int i) {
            i += 2;                              
        }
    }
    1. 1,3
    2. 3, 1
    3. 1, ,
    4. 1, 0
    5. Aucune de ces réponses
  3. Quelle de ces assertions est fausse ?
    1. Une interface peut étendre (extends) une autre interface.
    2. Une classe qui réalise une interface doit implémenter toutes les méthodes de l’interface.
    3. Une interface peut implémenter une autre interface
    4. Une interface est une solution pour l’héritage multiple en Java
    5. Aucune de ces réponses
  4. Parmi ces expressions, quelle(s) est(sont) de type String?
    1. "0"
    2. "ab" + "cd"
    3. '0'
    4. (a) et(b)
    5. (a), (b) et (c) .
  5. Considérer :
    public class MyClass
    {
    	public MyClass(){/*code*/}
    	// more code...
    }
      
    Pour instancier MyClass, que faut-il écrire?
    1. MyClass mc = new MyClass();
    2. MyClass mc = MyClass();
    3. MyClass mc = MyClass;
    4. MyClass mc = new MyClass;
    5. Le constructeur de MyClass devrait être défini comme suit : public void MyClass(){/*code*/}.
Réponse :

Référence: http://mcqquestion.blogspot.ca/2012/08/java-programming.html

Cinquième partie

Quiz (1 point)

  • Donnez l'ordre des éléments de la pile désignée par la référence s suite à l'exécution de ces énoncés. Assurez-vous de clairement identifier l'élément du dessus.
    s.push(new Integer(8)); 
    s.push(new Integer(6)); 
    num = s.pop(); 
    s.push(new Integer(3)); 
    s.push(new Integer(4)); 
    s.push(new Integer(15)); 
    s.push(new Integer(12)); 
    s.pop(); 
    s.pop(); 
    s.pop(); 
    s.push(new Integer(19));
    Réponse:
      
    

Soumettez la réponse sur Brightspace.

 

Table of Contents