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 - x

Est-ce différent de :

java Calculatrice 12 4 + 5 3 - x

Ecrire la classe Calculatrice correspondante !

Il y a plusieurs façons de réaliser cette calculatrice. La structure de donnée 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 mais l'interface Deque⁵ 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 ? 

Supplément

Quelles structures de données faut-il utiliser pour une calculatrice avec des entrées entre notation infixe ou préfixe ? Voir la discussion⁶.

Pour réviser, vous pouvez essayer d'implanter ces deux autres solutions !

Recherche

Proposer une méthode rechercheDichotomique qui permet de trouver un entier dans une List⁷ supposée ordonnée. On pourra utiliser la méthode Collections.sort8 pour trier la collection. Par contre, il est INTERDIT d'utiliser une des deux méthodes Collections.binarySearch9 vues 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.