TP5 - Collections

Calculatrice polonaise inversée

On veut utiliser la ligne de commande pour faire une calculatrice en ordre inversée. Comme on ne veut pas utiliser de structure de données compliquée, on décide de fonctionner en notation polonaise inverse.

Par exemple, pour ajouter 5 à 12 on écrira:

java Calculatrice 5 12 +

 Que fait l'opération suivante ?

java Calculatrice 5 12 4 + 3 - *

Est-ce différent de :

java Calculatrice 12 4 + 5 3 - *

Ecrire la classe Calculatrice correspondante !

Il y a plusieurs façons de réaliser cette calculatrice. La structure de contrôle la mieux adaptée est la pile. Une pile P a deux opérations, une opération push(int) qui empile un entier [en sommet de pile] et une opération pop():int qui prend l'élément en sommet de pile, le dépile et le rend à l'utilisateur. Cette dernière opération provoque une erreur si la pile est vide.

L'algorithme suivant est proposé :

Pour chaque argument arg

1. Si arg un nombre, on l'empile
2. Si arg un opérateur unaire
   • On dépile une valeur,
   • On applique l'opérateur,
   • On empile le résultat
3. Si arg un opérateur binaire
   • On dépile deux valeurs ,
   • On applique l'opérateur,
   • On empile le résultat

On peut réaliser facilement une pile avec une ArrayList. L'interface Queue est le type abstrait le plus naturel.

1. Quel type concret choisirez-vous ? Justifier votre choix !
2. Pourquoi est-ce qu'un tableau n'est a priori pas la bonne structure de données ? 

Recherche

Proposer une méthode rechercheDichotomique qui permet de trouver un Point dans un tableau supposé ordonné. On pourra utiliser la méthode Arrays.sort pour trier le tableau de points selon un ordre (par exemple, l'ordre lexicographique). Par contre, il est INTERDIT d'utiliser la méthode Arrays.binarySearch vue en cours et il faudra ré-implanter cette méthode. On rappelle pour cela le principe de la recherche dichotomique. 

Je cherche l'indice de l'élément e dans t du début à la fin :

1. Je compare e à l'élément qui se trouve au milieu t[milieu]  
2. Si t[milieu]==e, j'ai terminé et je renvoie l'indice milieu
3. Si t[milieu]<e, je cherche l'élément e entre le début et le milieu  
4. Si t[milieu]>e, je cherche l'élément e entre le milieu et la fin
5. Je recommence en 1.