Le but de cet exercice est la construction d'une petite calculette
(entière) dans le style des calculettes Helwet-Packard.
Ces calculettes sont intéressantes informatiquement parlant car elles
exposent leur fonctionnement interne qui utilise une pile.
On convient d'utiliser des objets piles.
C'est à dire que l'on crée une nouvelle pile stack en
invoquant le constructeur de la classe IntStack des piles
d'entiers stack = new IntStack ().
Ensuite on dépilera par stack.pop() et on empilera par
stack.push(i). Par rapport à une solution sans
objets, un avantage est une notation plus compacte et la possiblité de
faire cohabiter plusieurs piles.
Le squelette d'une telle classe est le suivant :
class IntStack {
... // Champs de l'objet pile (cf. plus loin)
IntStack () { // Constructeur des piles
/* Initialisation des champs */
}
int pop () { }
void push (int i) { }
public String toString () { // Renvoie une chaîne qui représente la pile
}
}
Le cours propose une implémentation des piles à l'aide d'un tableau
(les champs des piles sont alors un tableau d'entiers et un compteur).
Or, cela conduit à limiter a priori la taille des piles, ce qui
peut être évité en utilisant des listes chaînées
Les listes seront réalisées très basiquement :
class IntList {
int cont ;
IntList rest ;
IntList (int cont, IntList rest) {
this.cont = cont ;
this.rest = rest ;
}
}
L'usage d'une classe aussi minimale (aucune méthode) est décrit dans
les morceaux de Java.
Il s'agit en fait d'un encodage de la structure
d'enregistrement de Pascal, C ou Caml. C'est un peu sale, mais seule
la classe IntStack utlisera les listes.
La technique de réalisation des piles par les listes
est simple : un objet pile (d'entiers)
contient un champ l qui est une liste d'entiers.
Conventionellement,
un pile vide a le champ l égal à null,
l'opération push se réalise en ajoutant une
nouvelle cellule en tête de la liste l,
tandis que l'opération pop enlève la cellule de tête.
À chaque fois, il faut bien entendu ajuster le champ l, afin
d'enregistrer l'opération.
Il vous est demandé d'écrire la classe IntStack en bouchant
les trous du squelette.
(Les morceaux de java donnent un exemple de classe
IntStack qui réalise la spécification des
piles demandée.) Vous testerez votre classe IntStack à l'aide de la
classe de test Test.java et vous devriez
obtenir ce résultat :
maranget@manche ~/TD/TD-3 > java Test
Push de 0 donne {0}
Push de 1 donne {1, 0}
Push de 2 donne {2, 1, 0}
Pop de 2, reste {1, 0}
Pop de 1, reste {0}
Pop de 0, reste {}
Écrire une classe HP, qui inteprète chaque
argument de la
ligne de commande comme une instruction de calculette.
Soit +, -, x et / sont les quatres
opérations (attention pour la multiplication, * n'est pas
disponible !), réalisées sur la pile et un entier sera simplement
lu et
empilé.
Réaliser une opération en pile consiste à depiler deux arguments, à
effectuer l'opération, puis finalement à empiler le résultat.
Vous devriez obtenir :
maranget@manche ~/TD/TD-3 > java HP 1 2 3 x +
: {}
1 : {1}
2 : {2, 1}
3 : {3, 2, 1}
x : {6, 1}
+ : {7}
maranget@manche ~/TD/TD-3 > java HP 1 2 + 3 x
: {}
1 : {1}
2 : {2, 1}
+ : {3}
3 : {3, 3}
x : {9}
(La pile est affichée après chaque opération.)
N'oubliez pas de réflechir trente secondes au sens de la soustraction et
de la division.
Solution.
| 2 |
Transformateur du langage Texas vers HP |
|
Dans la pratique les gens préfèrent souvent parler à leur calculette
comme à leur maître d'école. C'est à dire qu'il préfèrent poser
leur calcul comme ``1 + 2 x 3'' et non pas comme
``1 2 3 x +''. C'est le parti-pris de la majorité des
calculettes grand public.
En termes informatique, on parle de notation infixe dans le
premier cas et de notation postfixe dans le second.
Il se trouve (et c'est le résultat du premier exercice) qu'il est
assez facile d'exécuter un calcul donné sous forme postfixe et plus
tordu d'exécuter un calcul donné sous forme infixe.
| 2.1 |
Une histoire de parenthèses |
|
On peut représenter assez grossièrement le langage infixe comme suit :
E :=
E opE
| [ E ]
| entier
Avec la convention que op est une des quatres opérations,
+, -, x ou / ;
que [ et ] sont les parenthèses ; et que
entier est n'importe quel entier (positif).
Toutefois cette représentation est ambigüe.
En effet l'expression ``1 + 2 x 3'' peut s'interpréter de deux
façons différentes, qui donneront deux résulats de calculs différents.
Si on suit les règles enseignées par
le maître d'école on obtient 7. Si on
effectue les opérations de gauche à droite sans se poser de questions
on obtient de résulat 9.
De même, il y a deux façons de calculer ``3 - 2 - 1'' qui
donnent comme résultats 0 et 2, et là,
la convention qui résoud l'ambiguité me semble moins claire.
Le tableau suivant résume toutes ces possibilités :
| Expression parenthésée |
Résultat |
Expression postfixe |
| 1 + [ 2 x 3 ] |
7 |
1 2 3 x + |
| [ 1 + 2 ] x 3 |
9 |
1 2 + 3 x |
| [ 3 - 2 ] - 1 |
0 |
3 2 - 1 - |
| 3 - [ 2 - 1 ] |
2 |
3 2 1 - - |
Pour lire les expressions infixes on se
donne la contrainte usuelle en informatique de lire de la gauche
vers la droite et on s'aide de deux piles, une pile stacki
des entiers (pour les calculs) et une pile stackm
des mots. À la fin de la
lecture d'une expression on convient que le résultat du calcul se
trouve en sommet de la pile des entiers et que la pile des mots
est revenue dans son état initial.
On convient aussi,dans un premier temps,
que l'utilisateur du programme a fait l'effort de
parenthéser complètement son expression.
Ensuite, on se donne deux opérations dites shift (avancer) et
reduce (calculer) :
-
L'opération shift consite à empiler le mot lu sur la pile
des mots (stackm) et à avancer d'un mot.
- L'opération reduce consiste à
à effectuer les opérations en attente sur stackm, selon cette
procédure, à appliquer jusqu'à trouver une parenthèse ouvrante sur la pile :
-
Si on dépile un entier, alors empiler sa valeur dans stacki.
- Si on dépile une opération, alors l'effectuer (deux dépilage de
stacki, plus empilage du résultat).
L'algorithme est ensuite très simple.
-
Si le mot lu est une parenthèse fermante , alors reduce,
puis passer au mot suivant.
- Sinon, shift.
Pour que ça marche, il convient de parenthéser beaucoup,
Absolument tous les arguments de tous les opérateurs doivent apparaître entre
parenthèses, ainsi que le résultat final.
Soit dans nos deux examples :
[ [ 1 ] + [ [ 2 ] x [ 3 ] ] ]
[ [ [ 3 ] - [ 2 ] ] - [ 1 ] ]
Écrire la calculette Texas bas de gamme (cela demande une classe
StringStack des
piles de chaînes, qui s'écrit rapidement en copiant puis
modifiant IntStack
et intList).
On obtiendra :
maranget@manche ~/TD/TD-3 > java BasGamme [ [ 1 ] + [ [ 2 ] x [ 3 ] ] ]
: {} {}
[ : {} {[}
[ : {} {[, [}
1 : {} {1, [, [}
] : {1} {[}
+ : {1} {+, [}
[ : {1} {[, +, [}
[ : {1} {[, [, +, [}
2 : {1} {2, [, [, +, [}
] : {2, 1} {[, +, [}
x : {2, 1} {x, [, +, [}
[ : {2, 1} {[, x, [, +, [}
3 : {2, 1} {3, [, x, [, +, [}
] : {3, 2, 1} {x, [, +, [}
] : {6, 1} {+, [}
] : {7} {}
: {7} {}
(a gauche la pile des entiers, à droite celle des mots.)
Solution.
En fait on peut faire effectuer le travail de parenthésage par la
calculette elle même.
Il suffit :
-
De commencer par ouvrir trois parenthèses.
- De faire agir la parenthèse fermante comme
`` ] ] ] [ [ ''.
- De faire agir l'opérateur +, comme
`` ] ] + [ [ '' (et - de même).
- de faire agir l'opérateur x comme
`` ] x [ '' (et / de même).
- De terminer en fermant trois parenthèses.
À partir de ces remarques, écrire une calculette Texas haut de gamme.
maranget@manche ~/TD/TD-3 > java Texas 1 + 2 x 3
: {} {[, [, [}
1 : {} {1, [, [, [}
+ : {1} {[, [, +, [}
2 : {1} {2, [, [, +, [}
x : {2, 1} {[, x, [, +, [}
3 : {2, 1} {3, [, x, [, +, [}
: {7} {}
maranget@manche ~/TD/TD-3 > java Texas [ 1 + 2 ] x 3
: {} {[, [, [}
[ : {} {[, [, [, [}
1 : {} {1, [, [, [, [}
+ : {1} {[, [, +, [, [}
2 : {1} {2, [, [, +, [, [}
] : {3} {[, [, [}
x : {3} {[, x, [, [}
3 : {3} {3, [, x, [, [}
: {9} {}
Solution.
| 2.3 |
Traduction de Texas vers HP |
|
En modifiant légèrement les règles de calcul, écrire un traducteur des
expressions infixes vers les expressions postfixes.
maranget@manche ~/TD/TD-3 > java Traduc 1 + 2 x 3
1 2 3 x +
maranget@manche ~/TD/TD-3 > java Traduc [ 1 + 2 ] x 3
1 2 + 3 x
Solution.
On revient sur la calculette HP, pour étendre ses fonctionnalités.
On peut par exemple changer les bases d'entrée et de sortie.
Spécifiez précisément le problème et résolvez-le.
Pour vous aider voici un exemple à méditer :
maranget@manche ~/TD/TD-3 > java NewHP 10 11 + 16 '>' 10 '>' 16 '<' 10 + 2 '>'
: {}
10 : {10}
11 : {11, 10}
+ : {21}
16 : {16, 21}
> : {15}
10 : {A, 15}
> : {21}
16 : {16, 21}
< : {21}
10 : {16, 21}
+ : {37}
2 : {2, 37}
> : {100101}
Solution.
| Dernière modification :
2002-11-27 |
Ce document a été traduit de LATEX par
HEVEA.