Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

Calculer sans parenthèses

La prochaine évaluation de TP sera basée sur ce sujet et pourra rapporter de 0 à 10 points sur votre note de TP.

Pour aborder ce TP, il faut maîtriser les parties A, C et D du cours. Dans le curriculum de référence, la partie D devait être (idéalement) maîtrisée le 7 février.

Si vous n’avez pas encore étudié et raisonnablement maîtrisé la partie D, alors vous êtes en difficulté. Il vous est conseillé de contacter, si ce n’est déjà fait, le responsable de l’UE (M. Bailleux) pour discuter avec lui de la meilleure stratégie d’apprentissage à adopter. Sachez que les chaînes de caractères, abordées dans la partie C, sont avant tout des tableaux et que vos compétences des parties A et C peuvent vous permettre de répondre à certaines questions.

Les 10 points de la première évaluation pourront par ailleurs être rattrapés à la deuxième, en cas de besoin.

Une pile de mots

Le but de cette partie est d’implémenter deux fonctions permettant d’utiliser une simple chaine de caractères dans le rôle d’une pile de mots.

  • void empile(char* pile, const char* mot) : Empile le mot désigné par le paramètre mot dans la pile désignée par le paramètre pile.
  • int depile void depile(char* pile, char* mot) Si la pile désignée par le paramètre pile est vide, place la chaîne vide dans le tableau désigné par le paramètre mot et retourne 0, sinon qui retire un mot de la pile, copie ce mot dans le tableau désigné par le paramètre mot, et retourne 1.

La pile est représentée par un tableau de caractères dont la taille est définie par une constante.

#define CAPA 256

Une pile vide est représentée par une chaine contenant uniquement le caractère '#', c’est à dire la chaine "#".

Voici la représentation d’une pile contenant le mot "aaa" :

"#aaa#"

Si on empile le mot "bbb", le contenu de la chaine représentant la pile est :

"#aaa#bbb#"

Si on empile ensuite le mot "ccc", le contenu devient :

"#aaa#bbb#ccc#"

Lorsqu’un mot est dépilé, la pile se retrouve dans l’état exact ou elle était avant que ce mot soit empilé.

Voici un exemple d’utilisation :

void essai1(void)
{
    char pile[CAPA];
    strcpy(pile,"#");
    char buf[CAPA];
    
    empile(pile,"aaa");
    printf("%s\n", pile);
    
    empile(pile,"bbb");
    printf("%s\n", pile);
    
    depile(pile, buf);
    printf("dépilé : %s, pile : %s\n", buf, pile);
    
    depile(pile, buf);
    printf("dépilé : %s, pile : %s\n", buf, pile);
}

L’exécution de cette fonction produit les affichages :

#aaa#
#aaa#bbb#
dépilé : bbb, pile : #aaa#
dépilé : aaa, pile : #

Question 1

Implémentez la fonction empile et testez-là en empilant des mots et en affichant la pile avec la fonction printf.

Question 2

Complétez la définition de la fonction depile esquissée ci-dessous. On suppose que la pile est dans un état correct, i.e. contient un '#' en premier caractère, suivi éventuellement d’un ou plusieurs mots, tous suivi d’un '#'.

int depile(char* pile, char* mot)
{
    int i = (int)strlen(pile)-1;
    if(i == 0)
    {
        // À compléter
    }
    else
    {
        // À compléter
        return 1;
    }
}

Attention, la conception de la deuxième partie à compléter (bien que ne nécessitant que quelques lignes de code) nécessite un vrai travail d’ingénierie, c’est à dire décomposer le traitement à réaliser en plusieurs étapes ayant chacune un rôle bien identifié. Une phase de mise au point, avec des affichages d’informations utiles, peut s’avérer nécessaire.

Voici les étapes d’exécution d’une implémentation possible de la fonction dans le cas où la pile contient les mots "aaa" et "bbb".

image-20220225133208992

  1. On place dans une variable i la position du dernier #.
  2. On place un 0 dans pile[i] (Pour faciliter la copie ultérieure du dernier mot empilé).
  3. On décrémente i jusqu’à ce que la case pile[i] contienne #.
  4. On copie la chaine commençant en position i dans le tableau devant recevoir le mot dépilé.
  5. On place un marqueur de fin en position i+1 pour que la pile s’arrête là où se trouvait le début du mot qui vient d’être dépilé.

Il est important de soumettre votre solution à une batterie de tests couvrants les situations suivantes :

  • Dépiler dans une pile vide.
  • Dépiler plusieurs fois de suite dans une pile non vide.
  • Enchaîner une succession d’empilages et dépilages.

En réalisant un affichage systématique de la pile et du mot dépilé après chaque action.

Calcul en notation polonaise inverse

Quand on réalise un calcul arithmétique, on est parfois obligé d’utiliser des parenthèses, comme dans l’exemple suivant :

(12 - 6) * (5 + 7)

Le résultat est 72 alors que si on enlève les parenthèses c’est -11.

Mais il existe un moyen de représenter toute expression arithmétique parenthésée sous la forme d’une suite de nombres et d’opérateurs, sans parenthèses. Avec l’exemple précédent, cela donne :

12 6 - 5 7 + *

Le principe de l’évaluation est d’une simplicité déconcertante. C’est d’ailleurs pour cette raison qu’il était utilisé par le toutes premières calculatrice électroniques. On utilise une pile de nombres. À chaque fois qu’un nombre est saisi, il est empilé. Lorsqu’un opérateur est saisi (-, +, /, *), deux nombres sont dépilés, l’opérateur est appliqué sur ces deux nombres, et le résultat est empilé.

Voici les états successifs de la pile lors de l’évaluation de l’expression donnée en exemple :

12
12 6
6      (évaluation du -)
6 5
6 5 7
6 12   (évaluation du +)
72     (évaluation du *)

On veut faire ce genre de chose avec notre pile de chaines, sauf que cette pile contient des chaines et pas des nombres. Lors de la saisie des valeurs, cela ne pose pas de problème. On peut saisir des chaines représentant des nombres. Mais au moment du calcul, il faudra transformer les mots dépilés en valeurs de type int et avant d’empiler le résultat, il faudra le convertir en une chaine.

Entrainez-vous à transposer quelques calculs parenthésés en notation polonaise inverse pour bien comprendre le principe :

(10-2)-((2 + 5) * 3 * 5)
(3 * 5 * 10) + (5 - 2) + (10 * 11)

Saisir et convertir

Voici quelques moyens conseillés pour saisir une chaine au clavier, convertir en entier une chaine représentant un entier, et convertir un entier en chaine.

Tout d’abord, la fonction définie ci-dessous, que vous pouvez reprendre dans votre code source, permet de saisir au clavier une chaine d’au plus lgMax caractères et de la placer dans le tableau désigné par buffer, qui doit être de taille suffisante pour recueillir la chaîne saisie.

void saisie(char* buffer, int lgMax)
{
    fgets(buffer, lgMax+1, stdin);
    buffer[strlen(buffer)-1] = 0;
}

Ensuite, la fonction sscanf peut permettre de traduire une chaîne (du moins son plus grand préfixe interprétable comme un entier) en entier, et la fonction sprintf peut permettre de convertir un entier en chaine. Ces fonctions peuvent être utilisées pour traduire plusieurs données en plusieurs formats en un seul appel, mais nous nous contenterons d’un usage basique, illustré par cet exemple :

void exemple(void)
{
    char buf[CAPA];                            // Ligne A
    
    saisie(buf,CAPA-1);                        // Ligne B
    printf("Chaine lue : %s\n", buf);
    
    int x=0;
    int status = sscanf(buf, "%d", &x);        // Ligne C
    printf("%d entier = %d\n", status, x);
    
    sprintf(buf, "%d", x);                     // Ligne D
    printf("Re-traduit en chaine : %s\n", buf);
}

En ligne A, on crée un tableau de caractères destiné à contenir le résultat d’une saisie au clavier (ligne C), puis d’une traduction d’un entier en chaine (ligne D).

En ligne B, on appelle la fonction saisie pour saisir une chaîne au clavier et la placer dans le tableau pointé par buf. L’argument CAPA-1 limite la taille de la chaine saisie pour éviter un débordement.

En ligne C, on utilise sscanf pour "lire" un entier dans la chaine contenue dans le tableau désigné par buf. L’entier lu est placé dans la variable x.

En ligne D, on fait l’opération inverse. On utilise sprintf pour "écrire" un entier sous forme de chaîne dans le tableau désigné par buf. La fonction sprintf fonctionne comme printf, mais écrit dans une chaîne au lieu de le faire à l’écran.

Vous devez expérimenter l’usage de ces fonctions, faire des essais en exécutant la fonction exemple et en saisissant des valeurs au clavier (comme par exemple "12", "345rt" ou encore "234zz", examiner les résultats pour bien comprendre ce qui se passe. Si vous avez des doutes, posez des questions à votre enseignant de TP.

Saisir et empiler

Vous devez définir une fonction…

void saisEmpile(void);

…qui permet de saisir des chaines (quelconques) au clavier, en utilisant la fonction saisir, et à les empiler dans une pile de capacité CAPA, jusqu’à ce que la chaîne vide soit saisie (par appui sur la touche entrée sans avoir rien tapé avant), puis qui affiche avec printf le contenu de la pile.

Si par exemple l’utilisatrice ou l’utilisateur fait les saisies suivantes…

  • abcd <entrée>
  • 56 <entrée>
  • d <entrée>
  • <entrée>

…la pile affichée doit être :

#abcd#56#d#

N’oubliez pas :

  • D’initialiser correctement la pile, qui doit contenir un # suivi d’un marqueur de fin pour pouvoir fonctionner.
  • De créer un tableau pour récupérer les chaines saisies au clavier.

Calculer

Vous devez compléter la fonction suivante pour qu’elle permette de réaliser un calcul en saisissant des entiers et des opérateurs +, -, *, et / en notation polonaise inverse. On suppose que la personne utilisatrice saisi uniquement des nombres, des opérateurs +, -, *, / et la chaine vide, et saisit un calcul complet, c’est à dire aboutissant à ce qu’il reste une seule valeur dans la pile.

N’oubliez pas que la pile ne contient que des nombres représentés sous forme de chaines, et aucun opérateur. Lorsqu’un opérateur est saisi, il n’est pas empilé, mais 2 valeurs sont dépilées, utilisées avec l’opérateur, et le résultat est empilé.

void calcul(void)
{
    char pile[CAPA];
    strcpy(pile,"#");
    char buf[CAPA];
    
    saisie(buf,10);
    while(/* AAAAA */)
    {
        int c = // BBBBB
        if((c=='+')||(c=='-')||(c=='*')||(c=='/'))
        {
            // CCCCC
        }
        empile(pile, buf);
        saisie(buf, 10);
    }
    depile(pile,buf);
    printf("Résultat : %s\n", buf);
}

La condition AAAAA doit être vraie lorsque la chaine saisie n’est pas vide, c’est à dire lorsqu’un opérateur ou un nombre a été saisi. La saisie d’une chaine vide provoque la sortie de la boucle, et donc la récupération du résultat dans la pile et son affichage.

L’instruction BBBBB place dans la variable c le premier caractère de la chaine venant d’être saisie.

Le bloc CCCCC est plus complexe et réalise les actions suivantes :

  1. Dépiler une chaîne, la convertir en entier.
  2. Dépiler une chaîne, la convertir en entier.
  3. Réaliser l’addition des deux entiers si c contient le caractère +, leur soustraction si c contient le caractère -, etc.
  4. Convertir le résultat en chaine.

Vous devez faire des tests intensifs pour vérifier le parfait fonctionnement de la "calculatrice" réalisée.

Et ensuite

Cette partie est facultative et s’adresse aux personnes les plus avancées.

Si vous avez terminé les exercices précédents, vous devez réfléchir à une automatisation du test de la fonction calcul avec des scénarios de tests pré-encodés dans des tableaux de chaînes de caractères.

Par exemple, le scénario de calcul donné en exemple plus haut…

12 6 - 5 7 + *

…est représenté par le tableau global :

char* scenario1[] =
{
    "72", "12", "6", "-", "5", "7", "+", "*", ""
};

La première chaine représente le résultat attendu et les suivantes les saisies successives aboutissant à ce résultat.

Voici un autre exemple de scénario de test :

char* Scenario2[] =
{
    "23", "33", "5", "2", "*", "-", ""
};

Un jeu de test, constitué de plusieurs scénarios, est représenté par un tableau global :

char** Bench[] =
{
    Scenario1, Scenario2, NULL
};

Les deux fonctions saisie et printf appelées par la fonction calcul seront remplacées par deux fonctions _saisie et _printf que vous devrez définir de manière à ce que :

  • les appels à _saisie simulent des saisies de chaines qui proviendront en fait d’un scénario de test,
  • les appels à _printf n’affichent rien à l’écran (la chaine de formatage sera ignorée), mais placent la valeur à afficher dans une variable globale où elle pourra être récupérée par la fonction de test pour vérifier si elle correspond au résultat prévu par le scénario de test utilisé.

Vous devez déclarer d’autres variables globales. À vous de déterminer lesquelles, quels seront leur rôle, comment la séquence de test doit se dérouler, et d’en déduire les implémentations de la fonction de test et des fonctions _saisie et _printf.

image-20220225213454169