1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
|
\documentclass{article}
\usepackage{fullpage}
\usepackage[latin1]{inputenc}
\usepackage{hevea}
\usepackage[french]{babel}
\def\homedir{http://w3.edu.polytechnique.fr/profs/informatique/Luc.Maranget/X.97}
\begin{latexonly}
\gdef\url#1#2{#2}
\gdef\oneurl#1{\url{#1}{{\tt #1}}}
\end{latexonly}
\title{TD-5, encore les pointeurs}
\date{}
\author{}
\pagestyle{empty}
\begin{document}
\maketitle
\thispagestyle{empty}
\begin{center}
Ce document est disponible l'URL
\oneurl{\homedir/TD-5/enonce.html}
\end{center}
\begin{center}
Programmes {\em Prenom.Nom.c} dposer par {\em
ftp} sur {\tt poly} en {\tt /users/profs/maranget/TD-5}.
\end{center}
\section{Calculatrice HP}
On se propose de raliser une petite calculette HP.
\subsection{Quatre oprations}
Cette premire partie s'inspire du cours. On utilisera une pile {\tt
stack}, globale et code
en machine par une liste d'entiers, voici la dfinition de {\tt stack} et
le constructeur des listes~:{\small
\begin{verbatim}
typedef struct cell {
int val;
struct cell *next;
} Cell, *Stack;
Stack stack = NULL;
Cell *cons(int val,Cell *next)
{
Cell *r;
r = (Cell *)malloc(sizeof(Cell));
if ( r == NULL) {
fprintf(stderr,"Plus de memoire\n");
exit(-1);
}
r->val = val;
r->next = next;
return r;
}
\end{verbatim}
}
\begin{itemize}
\item crire les fonctions de base de manipulation de la pile,
affichage de la pile ({\tt afficher}), empilage ({\tt push}) et
dpilage ({\tt pop}). Voici des signatures possibles~:{\small
\begin{verbatim}
void afficher(void)
int pop(void)
void push(int i)
\end{verbatim}
}
\item Une quelconque des quatre oprations (par exemple $-$) se
ralise ainsi~: dpiler le second argument (par exemple $i_2$), dpiler le
premier argument, (par exemple $i_1$), effectuer l'opration (par
exemple $i_1-i_2$) et empiler le rsultat.
La calculatrice obira un programme contenu dans une chane de
caractres et affichera, chaque tape intermdiaire, le caractre lu
(utiliser \verb+printf+ avec le format \verb+"%c"+)
et l'tat de de la pile. Par exemple,
pour le programme {\tt "12-34++"}, on aura~(la pile est affiche du
sommet vers le fond)~:{\small
\begin{verbatim}
[]
1 : [1]
2 : [2, 1]
- : [-1]
3 : [3, -1]
4 : [4, 3, -1]
+ : [7, -1]
+ : [6]
\end{verbatim}
}
Vous aurez donc lire la chane-programme caractre par caractre
(rappelez vous qu'une chane est un tableau de caractres) et
empiler un entier ou raliser une opration selon ce que vous avez
lu. Les quatre oprations devront bien entendu utiliser les primitives de
pile, {\tt push} et {\tt pop}. Attention au sens de la soustraction et
de la division.
\end{itemize}
\subsection{Oprations avances sur les piles}
Les vraies calculatrices HP ont des touches spciales qui permettent
des manipulations de la pile. Les oprations suivantes (qui diffrent
un peu de celles des calculatrices HP) sont raliser sans allouer aucune
cellule de liste.
\begin{itemize}
\item {\em changer} les deux lments du sommet de pile. Cette
opration sera ralise par le caractre {\tt 's'}. Ainsi, le
programme {\tt "12s-"} donnera le rsultat suivant~:{\small
\begin{verbatim}
[]
1 : [1]
2 : [2, 1]
s : [1, 2]
- : [1]
\end{verbatim}
}
\item {\em Rotation de la pile vers le haut}~: tous les lments
montent d'un cran vers le sommet de pile, le sommet de pile se
retrouve en fond de
pile. Le programme {\tt "4321u"} devra produire~:{\small
\begin{verbatim}
[]
4 : [4]
3 : [3, 4]
2 : [2, 3, 4]
1 : [1, 2, 3, 4]
u : [2, 3, 4, 1]
\end{verbatim}
}
\item {\em Rotation de la pile vers le bas}~: c'est l'opration
inverse, tous les lments
descendent d'un cran, le fond de pile se retrouve en sommet de pile.
Ainsi, le programme {\tt "4321d"} s'excute ainsi~:{\small
\begin{verbatim}
[]
4 : [4]
3 : [3, 4]
2 : [2, 3, 4]
1 : [1, 2, 3, 4]
d : [4, 1, 2, 3]
\end{verbatim}
}
\end{itemize}
Remarquez que les rotations reviennent, pour la rotation vers le haut,
mettre la cellule de tte en queue de liste et pour la rotation vers
le bas, mettre la cellule de queue en tte de liste. Vous aurez
sans doute intrt faire de petits dessins pour vous guider.
La solution de cet exercice apparatra \url{hp.c}{en hp.c}.
\section{S'il vous reste du temps}
Raliser une calculatrice PH, dont la structure de contrle est une
file. La file sera ralise par une liste (voir la fin du cours).
Une opration se fera en dfilant les deux arguments et en enfilant le
rsultat.
Vous pouvez aller jusqu' donner une signification claire aux
rotations et les programmer.
\end{document}
|
