Le but de cette série d'exercices est de vous permettre de continuer à pratiquer les aspects de la programmation en C utilisant les pointeurs.
Reprenez l'exercice 3 de la série 5, mais en l'écrivant en utilisant l'arithmétique des pointeurs, en affichant par exemple directement toutes les adresses (sans passer par un index) :
0x7fffb7ed88ac : 01010000 80 ('P')
0x7fffb7ed88ad : 00000000 0
0x7fffb7ed88ae : 00000000 0
0x7fffb7ed88af : 00000000 0
Dans le même esprit, vous pouvez reprendre d'autres anciens exercices et écrire des solutions utilisant cette fois l'arithmétique des pointeurs. Par exemple, l'exercice 2 de la série 7 (segmentation en mots).
Utiliser des tableaux dynamiques (exercice 1 de la série 6) ou des listes chaînées (exercice 3 de la série 8), ou
votre propre structure (à inventer), pour implémenter une structure de pile (empiler, dépiler, valeur du sommet, test de pile vide) et
résoudre le problème du parenthésage à deux parenthèses (« langage de Dyck ») : est-ce qu'une expressions utilisant 2 sortes de parenthèses, comme par exemple « (a + [ b * c * ( d + e ) - 3 ] ) * ( x - [ 7 * b ] + 3) » est correctement parenthèsée ou non ?
Les indications sont progressives, aussi, dès que vous pensez en savoir assez, essayez de faire l'exercice par vous-même.
On veut implémenter une pile. Qu'est-ce qui définit une pile ? Son sommet (le seul élément auquel on peut accéder) et les 4 fonctions : empile, dépile, lecture du sommet et test si la pile est vide.
On vous demande d'implémenter la pile soit à l'aide de tableaux dynamiques (exercice 1 de la série 6), soit de listes chaînées (exercice 3 de la série 8) [ou autre chose si vous trouvez mieux]. Il vous suffit simplement de définir où mettre le sommet : en tête ou en queue de la structure de données ?
Que se passe-t-il quand on empile un nouvelle
élément ?
Il devient le nouveau sommet.
Si on choisit de représenter le sommet de la pile par la premier
élément du vecteur (élément 0) alors quand on empile un nouvel
élément il faudra le mettre en 0 et déplacer tout le reste.
Ce qui n'est pas une bonne solution !
Par contre si on choisit de représenter le sommet par le dernier élément du vecteur, empiler consiste alors juste à ajouter un élément au vecteur.
Une pile sera donc représentée par un tableau dynamique/une liste chaînée, le sommet de la pile étant le dernier élément pour un tableau dynamique, le premier pour une liste chaînée.
Avec cette implémentation, empiler un élément revient à l'ajouter à la fin/au début, dépiler revient à enlever le dernier/premier élément, lire le sommet revient à lire le dernier/premier élément et tester si la pile est vide à tester si la structure de données est vide ou non.
( ou [, l'empiler
) ou ]
Entrez une expresssion parenthésée : ([]])
-> Erreur
Entrez une expression parenthésée : ([([()[]])][[()]]())
-> OK
Entrez une expression parenthésée :
Note : Le programme se termine lorsque la chaîne saisie est vide.
On veut faire un programme qui interprète les opérations arithmétiques en notation polonaise inverse (c'est-à-dire notation « postfixée »).
Cette notation consiste à donner tous les arguments avant l'opération.
Par exemple : 4+3 s'écrit 4 3 +. De même : (4 * 5) + 3 s'écrit 4 5 * 3 +
Notez qu'avec ce système de notation il n'y a pas besoin de parenthèse. Il suffit d'écrire les opérations dans le bon sens.
Par exemple : (4+3)*(3+2) s'écrit 4 3 + 3 2 + * alors que 4 + (3*3) + 2 s'écrit 4 3 3 * + 2 +
L'algorithme pour effectuer des opérations données en notation postfixée est le suivant, où P est une pile :
Tant que lire caractère c
Si c est un opérande
empiler c sur P
Sinon
Si c est un opérateur
y <- sommet(P)
dépiler P
x <- sommet(P)
dépiler P
empiler le resultat de "x c y" sur P
À la fin de cet algorithme, le résultat est au sommet de P.
Dans cette série nous allons simplement nous intéresser aux
opérations sur les chiffres : les seuls opérandes seront les
chiffres de 0 à 9.
(Par exemple : 14+ veut dire 1 + 4 [on pourra
bien entendu aussi noter avec des espaces : 1 4 +])
Cette fonction devra implémenter l'algorithme ci-dessus, et utilisera donc une pile d'entiers.
La fonction main bouclera tant que la chaîne entrée n'est pas vide (voir l'exemple ci-dessous).
if ((c >= '0') && (c <= '9'))
Note : on peut aussi utiliser la fonction standard isdigit((int) c) définie dans ctype.h.
(int)(c - '0')
Entrez une expression à évaluer : 8 6 2 - / 3 + -> résultat : 5 Entrez une expression à évaluer : 4 3 + 3 2 + * -> résultat : 35 Entrez une expression à évaluer : 4 3 3 * + 2 + -> résultat : 15 Entrez une expression à évaluer :
La comparaison et l'alignement de séquences de caractères est une tâche fondamentale dans plusieurs domaines d'applications, notamment en reconnaissance vocale, traitement d'images et bio-informatique. Le but de cet exercice est d'implémenter l'algorithme de Needleman-Wunsch (qui est un algorithme de Viterbi), utilisé par exemple dans le BioWall que vous avez pu observer toutes les semaines en entrant dans les salles d'exercices IN.
La première partie de l'algorithme consiste à évaluer la comparaison entre deux chaînes de caractères de tailles différentes, en minimisant le nombre d'insertions de « trous » entre deux caractères d'une même chaîne. En pratique, une matrice M de taille (m + 1) × (n + 1) est construite, où m et n sont les nombres de caractères des deux chaînes à comparer. Un « trou » est caractérisé par un déplacement horizontal ou vertical dans la matrice. On assigne alors à chaque cellule Mi,j de la matrice un score défini par les équations suivantes :
Le but est d'implémenter en C une fonction permettant de construire une telle matrice à partir de deux chaînes de caractères introduites par l'utilisateur. Chaque cellule devra, en plus de son score, conserver la/une des2 cellule(s) parente(s), pour laquelle le maximum de l'équation (1) a été atteint (voir figure 1).
Fig. 1 – Exemple de matrice. Les flèches représentent les cellules parentes.
La seconde partie de l'algorithme permet de retrouver un alignement correct. Pour cela, il faut rechercher un chemin en partant de la cellule Mm,n et arrivant à la cellule M0,0, en utilisant à chaque fois la cellule parente stockée.
Pour implémenter cet algorithme, vous procèderez par étapes:
void afficheSolution(Solution* sol, const char* s1, const char* s2) {
int i,j;
for (i=0,j=0; i<sol->size; ++i) {
switch (sol->dirs[i]) {
case DirDiag: /*continued*/
case DirHorz: printf("%c",s1[j]); ++j; break;
case DirVert: printf("_");
}
}
printf("\n");
for (i=0,j=0; i<sol->size; ++i) {
switch (sol->dirs[i]) {
case DirDiag: /*continued*/
case DirVert: printf("%c",s2[j]); ++j; break;
case DirHorz: printf("_");
}
}
printf("\n");
}
Qui vous donnera pour les valeurs:s1 = "Bonjour monsieur, quelle heure est-il à votre montre ?" s2 = "Bonne journée madame, que l'heureuse fillette vous montre le chemin"le résultat suivant:
Bon___jour____ monsieur, quelle heure est-_il à__ votre montre ?________ Bonne journée madame__, que l'_heureu_se fillette vous_ montre le chemin
