TP N°6 - Les Piles
Exercice 1 : Implementation d’une pile à partir d’un tableau
On peut représenter une pile par un tableau (contiguë).
On définira la pile (pile de caractères) en C comme suit :
typedef char typeElem;
#define Max 100
typedef struct
{
int sommet;
typeElem tab[Max];
} pile;
Ecrire les fonctions :
initPile : Initialisation de la pile
pileVide : teste si la pile est vide ou non
pilePleine : teste si la pile est pleine ou non
empiler : ajoute un élément au sommet de la pile si la pile n’est pas pleine
desempiler : enlève l’élément au sommet de la pile si la pile n’est pas vide
consulterSommet : consulte l’élément au sommet de la pile (sans l’enlever)
Les prototypes de ces fonctions sont les suivants :
void initPile(pile *P) ;
int pileVide(pile *P) ;
int pilePleine(pile *P) ;
void empiler(pile *P, typeElem x) ;
void desempiler(pile *P, typeElem *x) ;
void consulterSommet(pile *P, typeElem *x) ;
Exercice 2 : Implémentation d’une pile à partir d’une liste chainée simple
On peut représenter une pile par une liste chainée simple.
On définira la pile (pile de caractères) en C comme :
typedef char typeElem;
typedef struct pileNoeud
{
typeElem element;
struct pileNoeud *suivant;
} pileNoeud;
typedef pileNoeud *pile;
Ecrire les fonctions :
initPile : Initialisation de la pile
pileVide : teste si la pile est vide ou non
pilePleine : teste si la pile est pleine ou non
empiler : ajoute un élément au sommet de la pile.
desempiler : enlève l’élément au sommet de la pile si la pile n’est pas vide
consulterSommet : consulte l’élément au sommet de la pile (sans l’enlever)
Ces fonctions ont les mêmes prototypes que dans l’exercice 1.
Il faudra d’abord écrire la fonction creerNoeud() qui alloue un élément de type pileNoeud. Cette fonction sera appelé par la fonction empiler().
Exercice 3 : Implementation d’une pile à partir d’un tableau Dynamique
Modifier la solution donnee en exercice No1 en utlisant un tableau Dynamique
On définira la pile (pile de caractères) en C comme suit :
typedef char typeElem;
#define Max 100
typedef struct
{
int sommet;
int maxElms;
typeElem *pTab;
} pile;
Ecrire les fonctions :
initPile : Initialisation de la pile
pileVide : teste si la pile est vide ou non
pilePleine : teste si la pile est pleine ou non
empiler : ajoute un élément au sommet de la pile.
desempiler : enlève l’élément au sommet de la pile si la pile n’est pas vide
consulterSommet : consulte l’élément au sommet de la pile (sans l’enlever)
libererPile: libere l'espace occupe par le tableau dynamique
NOTE
Il faut noter que la pile a été implementé dans les exercices 1, 2 et 3 de telle façon qu’on peut utiliser l’une ou l’autre de ces implementations dans les exercices qui suivent.
Exercice 4 : Transformation d’une expression infixée en expression post-fixée
Une utilisation courante des piles est l’élaboration par le compilateur d’une forme intermédiaire de l’expression. Après l’analyse syntaxique et lexicale, l’expression est traduite en une forme intermédiaire plus facilement évaluable.
Implementer en C l’algorithme montré en pseudo code ci-dessous qui converti une expression infixée (chaine de caractères infixExp) en une expression post-fixée (chaine de caractères postfixExp).
On utilisera comme operations : +, -, *, / et le %.
On considere aussi :
precedence(‘+’) = precedence(‘-‘) = 1
precedence(‘*’) = precedence(‘/‘) = precedence(‘%’) = 2
foreach ch de infixExp
{
switch(ch)
{
case operand: // ajouter operand a la fin de postfixExp
postfixExp = postfixExp + ch
break
case ’(’: // sauvegarder ’(’ dans la pile
empiler(pile, ch)
break
case ’)’: // desempiler la pile jusqu’au correspondant ’(’
while (sommet de la pile n’est pas ’(’)
{
postfixExp = postfixExp + (sommet de la pile)
desempiler(pile)
} // end while
desempiler(pile) // enlever le ’(’
break
case operator: // traiter les operateurs dans la pile de plus grande precedence
while (pile Non vide et sommet de pile n’est pas ’(’ et
precedence(ch) <= precedence(sommet de la pile))
{
postfixExp = postfixExp + (sommet de la pile)
desempiler(pile)
} // end while
empiler(pile, ch) // sauvegarder nouveau operateur
break
} // end switch
} // end for
// ajouter a postfixExp les operateurs qui restent dans la pile
while(pile Non vide)
{
postfixExp = postfixExp + (sommet de la pile)
desempiler(pile)
} // end while
Convertir les expressions infix suivantes en postfix format :
3+4*5/6
(3+2)*(4-1)/(8+7)
(4+8)*(6-5)/((3-2)*(2+2))
Vous devriez obtenir respectivement les expressions suivantes :
3 4 5 * 6 / +
3 2 + 4 1 - * 8 7 + /
4 8 + 6 5 - * 3 2 – 2 2 + * /
Exercice 5 : Evaluation d'une expression post-fixée
L’algorithme ci-dessous évalue une expression post-fixée composée d’opérateurs et d’entiers à un seul chiffre. Implementer cet algorithme en C.
Initialiser(pile)
foreach ch of postfixExp
{
if (ch est un operand)
empiler(pile, ch)
else // ch est un operateur
operand2 = desempiler(pile)
operand1 = desempiler(pile)
result = appliquer operateur ch a operand1 et operand2
empiler(pile, result)
}
return desempiler(pile)
Etendre le programme C ecrit auparavant au cas d’entiers composés de plusieurs chiffres. On supposera que les nombres entiers sont separés par des espaces dans l’expression post-fixee.
Exercice 6 : Tri d'une Pile
L’algorithme ci-dessous trie une pile p en utlisant une pile intermediare tmp. A la fin l'algorithme tmp sera triee par ordre decroissant:
Tant que pile initiale p est non vide
desempiler p dans x
Tant que pile tmp est non vide et sommet(tmp) < x
desempiler tmp dans tmp_x
empiler tmp_x dans p
empiler x dans tmp
A la fin la pile tmp sera triee par ordre decroissant