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.

5. 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)))))