Première partie

Piles (Stack)

Introduction

Les piles sont couramment en programmation. Dan un premier temps, assurez-vous de bien comprendre leur utilisation. Les piles respectent le protocole last-in first-out ou LIFO (dernier entré premier sorti). Cette structure de données empile les éléments les uns par dessus les autres. Vous n'avez accès qu'à l'élément du dessous.

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

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 pourriez être évalué à 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 :

• Stack.java

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 :

• ArrayStack.java
• L6Q1.java

1.3 Créer une nouvelle classe DynamicArrayStack

Modifier la classe ArrayStack afin qu'elle utilise la technique de tableau dynamique. Cette nouvelle classe, DynamicArrayStack, possède une constante nommée DEFAULT_INC dont la valeur est 25. Le constructeur prend un argument, capacity, qui est la taille initiale du tableau (ont dit aussi taille physique de la pile). Cependant, la taille physique (longueur du tableau) n'est jamais moins que DEFAULT_INC (donc 25). Cette classe contient aussi une méthode d'accès (getter), getCapacity(), qui retourne un entier représentant la longueur du tableau (taille physique). Lorsque votre tableau est plein, un nouveau tableau ayant DEFAULT_INC cellules de plus que la taille actuelle du tableau doit être créée. Vous devez y copier les éléments de l'ancien tableau. Par ailleurs, à l'inverse, lorsque la taille logique de la pile (nombre d'éléments) a DEFAULT_INC éléments de moins que la taille physique de la pile (taille du tableau), vous devez automatiquement en diminuer la taille (le nouveau tableau a alors DEFAULT_INC cellules de moins que l'ancien tableau). Faites les ajustements nécessaires, notamment dans pop, push, clear et les constructeurs (rappel, la taille physique (taille du tableau) minimale est DEFAULT_INC).

Fichier :

• Stack.java

 

Deuxième partie

Cette partie est laissée à votre propre discrétion et n’a pas besoin d’être remise. Toutefois, comme cette matière est peut être couverte à l’examen de mi-session, nous vous recommandons fortement de la parcourir.

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ésulat « 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ésulat 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.

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 trouver des expressions pour lesquelles l'algorithme retourne true bien que ces expressions ne sont pas bien formées.

Fichier

• Balanced.java

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

Les interfaces et les classes peuvent avoir un paramètre de type. On parle alors de types génériques. Ces types peuvent être utilisées dans plusieurs contextes. Rappelez-vous de l'interface Comparable! Les types génériques sont à la fois versatiles et sécuritaires.

Fichiers :

• Map.java
• Dictionary.java
• Pair.java

3.1 Implémenter l'interface Map

Définir l'interface Map. Une classe qui réalise l'interface Map doit sauvegarder des associations clé-valeur (key-value). Ici, nous souhaitons qu’un objet Map puisse contenir plusieurs clés (key) identiques, auquel cas les méthodes get, put, replace et remove feront référence à la l’association contenant cette clé se trouvant la plus à droite (la plus récente). Map possède deux paramètres de type, K et V, où K est le type des clés (keys) et V le type des valeurs (values). L'interface Map possède les méthodes suivantes :

1. V get(K key) : retourne la valeur la plus à droite (rightmost 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 à droite possédant la clé spécifiée en paramètre (replaces the value of the rightmost occurrence of the association for the specified key)
5. V remove(K key) : retire l’association la plus à droite 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. Un objet de type Pair doit stocker une association, « key » et « value », de type String et Integer respectivement. Etudiez le fichier fournit et déjà complété.
• 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 à droite 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).
• Il contient des getters, getCount () qui renvoie le nombre actuel d'éléments dans le dictionnaire et getCapacity () qui renvoie la longueur actuelle du tableau.
• DictionaryTest.java comprend une série de tests pour votre implémentation.

Notez qu'il n'est pas nécessaire de gérer des entrées exceptionnelles dans votre solution (par exemple, supprimer, obtenir ou remplacer une clé qui n'existe pas.)

 

Quatrième partie

Créer et soumettre un fichier zip (1 point)

Directives

• Créez un répertoire que vous nommerez lab6_123456, où vous remplacerez 123456 par votre numéro d'étudiant. Notez que le nom du répertoire est en minuscules, incluant la lettre «l».
• Dans ce répertoire, placer les fichiers pour les exercices du laboratoire. N'y ajoutez que le code source, les fichiers .java. En particulier, ne soumettez pas les fichiers .class.
• Dans ce répertoire, créez aussi un fichier texte nommé README.txt, qui devra contenir votre nom, numéro d'étudiant, ainsi qu'une brève description du contenu (en français ou en anglais, c'est votre choix) :

  
  Nom de l'étudiante ou de l'étudiant: Paidge Beaulieu
  Numéro d'étudiant: 123456
  Code du cours: ITI1521
  Section de laboratoire: A02
  
  Cette archive contient les 7 fichiers du laboratoire 6.
  
  Spécifiquement, ce fichier (README.txt), ainsi que
  ArrayStack.java, Dictionary.java, DynamicArrayStack.java, Pair.java, Map.java, Stack.java.
  
                      

• Créez un fichier zip lab6_123456.zip à partir du répertoire lab6_123456.
• Assurez-vous que cette archive comprend tous les fichiers nécessaires. Pour ce faire, copiez le fichier zip quelque part, ouvrez-le et assurez-vous que les fichiers et les répertoires espérés s'y trouvent.
• Soumettez l'archive sur le site Web https://uottawa.brightspace.com/.

Remarques importantes!

Nous utilisons des scripts automatisés pour tester et évaluer votre soumission de laboratoire. Par conséquent, vous devez suivre ces instructions à la lettre. En particulier:

• Les noms de tous les fichiers et méthodes doivent être exacts. Utilisez le code de démarrage fourni pour éviter des problèmes.
• Il faut soumettre un fichier .zip; pas de fichiers individuels; pas un .rar, pas un .7z, ni rien d’autre.
• Tous les fichiers de java doivent être présents et compiler avec succès (autrement dit, l’exécution de javac *.java ne doit générer aucune erreur), même si vous n’êtes pas capable de compléter un exercice.
• Notez si le code ne sera pas compilé en raison d'erreurs de syntaxe, vous n'obtiendrez pas de marque. Même si vous ne pouvez pas à résoudre complètement cet exercice, vous devez déposer un fichier contenant les méthodes intactes qui compilent correctement (vous pouvez mettre "return 0" si vous avez abandonné).
• Votre travail doit être soumis au plus tard à 23h30 le mardi de la semaine prochaine.

JUnits

Pour vous assurer que votre code est correct, nous avons préparé quelques tests unitaires.

Resources

• https://docs.oracle.com/javase/tutorial/getStarted/application/index.html
• https://docs.oracle.com/javase/tutorial/getStarted/cupojava/win32.html
• https://docs.oracle.com/javase/tutorial/getStarted/cupojava/unix.html
• https://docs.oracle.com/javase/tutorial/getStarted/problems/index.html