EXERCICE IX

LES PILES ET FILES

 

1.      Faire un programme de traitement díune pile, implanté dans un tableau statique. Utiliser fonctions différentes de : 1) empiler (push) ; 2) dépiler (pop; 3) initialisation (init) ; 4) indication si la pile est pleine (full) ; 4) affichage du contenu de la pile (MyStackPrint). Faire empiler dans la pile un nombre díéléments indéterminés. Faire afficher le contenu de la pile.

#include <stdio.h>

#include <conio.h>

#include <ctype.h>

#define MAX_PILE 20

typedef float TypeEl;

typedef struct

{

††††† TypeEl v[MAX_PILE];

††† int top;

} Stack;

void push(Stack *S, float val);

float pop(Stack *S);

void init(Stack *S);

int full(Stack *S);

void MyStackPrint(Stack *S);

void main()

{†† Stack S;

††††† TypeEl el;

††††† init(&S);

††††† MyStackPrint(&S);

††††† do {

††††††††††††††††† printf("\nEntrer element:");

††††††††††††††††† scanf("%f",&el);

††††††††††††††††† push(&S, el);

††††††††††††††††† printf("El. suivant?O/N:");

††††† †††† } while (toupper(getch())=='O');

††††† MyStackPrint(&S);

}

void init(Stack *S)

{†††† S->top = 0;††† }

void push(Stack *S, TypeEl val)

{†† if(!full(S))

††††††††††††††††† { S->v[ S->top ] = val;

††††††††††††††††† (S->top)++;

††††††††††††††††† }

/*ou bien: S->v[ (S->top)++ ] = val;†† */

††††† else

††††††††††††††††† printf("La pile est pleine\n");

}

 

float pop(Stack *S)

{†† (S->top)--;

††† return (S->v[S->top]);

/*Equivalent to: return (S->v[--(S->top)]);*/

}

 

int full(Stack *S)

{†††† return (S->top >= MAX_PILE);†† }

 

void MyStackPrint(Stack *S)

{††† int i;

††††† if (S->top == 0)

††††††††††††††††† printf("La pile est vide.\n");

††† else

††† †††{ printf("\nLe contenu de la pile: ");

†††††† †††††††††† for (i=0;i<S->top;i++)

†††††† †††††††††††††††††††††††††††††††††† printf("%g††† ",S->v[i]);

††††††††††††††††† printf("\n");

††† †††}

}

 

 

2.      Modifier le programme de p.1 en ajoutant les actions suivantes : 1) dépiler une fois et voir le contenu de la pile après dépilage ; 2) empiler la somme de deux éléments dépilés (dans un opérateur díappel de la fonction push) et voir le contenu de la pile après. 

 

3.      Les fonctions de traitement díune pile, implanté dans un tableau dynamique sont : 1) empiler (stack_push) ; 2) dépiler (stack_data stack_pop; 3) initialisation (stack_init) ; 4) indication si la pile est vide (stack_empty) ; 4) affichage du contenu de la pile (Print).

typedef int stack_data;

 

struct stack_rec

†† {

††††† stack_data data;

††††† struct stack_rec *next;

†† };

 

struct stack_rec *top=NULL;

 

void stack_init()

{†††

††††† top=NULL;

}

 

int stack_empty()

{††if (top==NULL)

††††††† return(1);

†††† else

††††††† return(0);

}

 

void stack_push(stack_data d)

{

††† struct stack_rec *temp;

††† temp =(struct stack_rec *)malloc(sizeof(struct stack_rec));

††† temp->data=d;

††† temp->next=top;

††† top=temp;

}

 

stack_data stack_pop()

{

††††† struct stack_rec *temp;

††††† stack_data d=0;

††††† if (top!=NULL)

††††† {

††††††††††††††††† d=top->data;

††††††††††††††††† temp=top;

††††††††††††††††† top=top->next;

††††††††††††††††† free(temp);

††††† }

††††† return(d);

}

 

void Print()†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† †††††††††

{ struct stack_rec *temp=top;

stack_data d=0;

while (temp!=NULL)

††††† {

††††††††††††††††† d=temp->data;

††††††††††††††††† printf("\n%d",d);

††††††††††††††††† temp=temp->next;

 

††††† }

}

4.       Utiliser les fonctions données au dessus et faire empiler dans la pile un nombre díéléments indéterminés. Faire afficher le contenu de la pile. Dépiler une fois et voir le contenu de la pile après dépilage. Vérifier si la pile est vide.

  1. Faire un programme de vérification de parenthèses en utilisant les fonctions du traitement díune pile (p.1) et líalgorithme suivant:

 

        {, (, [ doit correspondre à }, ) et ] respectivement

 

i = 1

Tantque i< nb de caracteres faire

Si caractere[i] est '(' ou '{' ou ' [' alors

††† empiler caractere[i]

Sinon

†† Si caractere[i] est ') ' ou '}' ou ']' alors

††††† Si caractere[i] = sommet de la pile alors

††††††††† depiler la pile

†† Sinon

ERREUR

i=i+1

†††Fin Tantque

††††

†††† Examples:

†††† 3*(2-[4 / (2 +x]) * y)

†††† ((((x + 4 / 3 * (-5)))))