Exercice 1 : (Création d’une pile et ses fonctions)
On vous demande d’implémenter (par liste), une Pile permettant de représenter des piles d’entiers. Pour cela vous développerez les fonctions et opérateurs de base permettant de manipuler les piles, à savoir:
- La fonction permettant de créer une pile vide.
- bool vide() : teste de vacuité.
- int hauteur() : retourne la hauteur de la pile.
- void empiler(int n) : fonction permettant d’empiler un entier au sommet de la pile.
- void depiler() : enlève l’élément au sommet de la pile.
- void remplacer(int n) : remplace le sommet de la pile par n.
- int sommet() : retourne l’élément au sommet de la pile.
Solution :
#include <iostream>
using namespace std ;
struct elemenet
{
int data ;
struct elemenet * next ;
};
typedef struct elemenet Element ;
typedef Element * Stack ;
Stack create_stack()
{
return NULL ;
}
bool is_empty_stack(Stack stk)
{
if(stk == NULL)
return true ;
else
return false ;
}
int deapth_stack(Stack stk)
{
Stack ptr = stk ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Stack push_stack(Stack stk, int val)
{
Stack ptr = new Element ;
ptr->data = val ;
ptr->next = stk ;
stk = ptr ;
return stk ;
}
Stack pop_stack(Stack stk, int &val)
{
if(!is_empty_stack(stk))
{
Stack ptr = stk ;
val = stk->data ;
stk = stk->next ;
delete ptr ;
return stk ;
}
else
{
cout << "Error, the stack is already empty." << endl ;
return NULL ;
}
}
int top_stack(Stack stk)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return 0 ;
}
return stk->data ;
}
Stack replace_top_stack(Stack stk, int val)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return NULL ;
}
stk->data = val ;
return stk ;
}
void display_stack(Stack stk)
{
Stack ptr = stk ;
if(is_empty_stack(stk))
{
cout << "Stack is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
int main()
{
Stack stk = create_stack() ;
display_stack(stk) ;
stk = push_stack(stk, 1) ;
stk = push_stack(stk, 2) ;
stk = push_stack(stk, 3) ;
display_stack(stk) ;
cout << "The top of the stack is : " << top_stack(stk) << endl ;
stk = replace_top_stack(stk, 4) ;
display_stack(stk) ;
cout << "The depth of the stack is : " << deapth_stack(stk) << endl ;
int val ;
stk = pop_stack(stk, val) ;
cout << "The value popped from the stack is : " << val << endl ;
display_stack(stk) ;
stk = pop_stack(stk, val) ;
cout << "The value popped from the stack is : " << val << endl ;
display_stack(stk) ;
stk = pop_stack(stk, val) ;
cout << "The value popped from the stack is : " << val << endl ;
display_stack(stk) ;
return 0 ;
}Exercice 2 : (Création d’une file et ses fonctions)
On vous demande d’implémenter (dynamiquement : par liste) une File permettant de représenter des files d’entiers. Pour cela vous développerez les fonctions et opérateurs de base permettant de manipuler les files, à savoir :
- La structure permettant de créer une file vide.
- bool vide() : teste de vacuité.
- int longueur() : retourne la longueur de la file.
- void adjq(int n) : adjonction en queue d’un entier n. // Emfiler
- void supt() : suppression de l’élément en tête de la file. // Defiler
- int tete() : retourne l’élément en tête de la file.
Solution :
#include <iostream>
using namespace std ;
struct elemenet
{
int data ;
struct elemenet * next ;
};
typedef struct elemenet Element ;
typedef Element * Queue ;
Queue create_queue()
{
return NULL ;
}
bool is_empty_queue(Queue que)
{
if(que == NULL)
return true ;
else
return false ;
}
int deapth_queue(Queue que)
{
Queue ptr = que ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Queue enqueue(Queue que, int val)
{
Queue elm = new Element ;
elm->data = val ;
elm->next = NULL ;
if(is_empty_queue(que))
{
que = elm ;
return que ;
}
Queue ptr = que ;
while(ptr->next != NULL)
ptr = ptr->next ;
ptr->next = elm ;
return que ;
}
Queue dequeue(Queue que, int &val)
{
if(!is_empty_queue(que))
{
Queue ptr = que ;
val = que->data ;
que = que->next ;
delete ptr ;
return que ;
}
else
{
cout << "Error, the queue is already empty." << endl ;
return NULL ;
}
}
int front_queue(Queue que)
{
if(is_empty_queue(que))
{
cout << "Error, Queue is empty." << endl ;
return 0 ;
}
return que->data ;
}
int rear_queue(Queue que)
{
if(is_empty_queue(que))
{
cout << "Error, Queue is empty." << endl ;
return 0 ;
}
Queue ptr = que ;
while(ptr->next != NULL)
ptr = ptr->next ;
return ptr->data ;
}
void display_queue(Queue que)
{
Queue ptr = que ;
if(is_empty_queue(que))
{
cout << "Queue is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
int main()
{
Queue que = create_queue() ;
display_queue(que) ;
que = enqueue(que, 1) ;
que = enqueue(que, 2) ;
que = enqueue(que, 3) ;
display_queue(que) ;
cout << "The front of the queue is : " << front_queue(que) << endl ;
cout << "The rear of the queue is : " << rear_queue(que) << endl ;
cout << "The depth of the queue is : " << deapth_queue(que) << endl ;
int val ;
que = dequeue(que, val) ;
cout << "The value dequeued from the queue is : " << val << endl ;
display_queue(que) ;
que = dequeue(que, val) ;
cout << "The value dequeued from the queue is : " << val << endl ;
display_queue(que) ;
que = dequeue(que, val) ;
cout << "The value dequeued from the queue is : " << val << endl ;
display_queue(que) ;
return 0 ;
}Exercice 3 : (Inverser une pile et une file en préservant les originales)
Concevoir deux algorithmes, qui créent respectivement :
- la file inverse d’une file .
- la pile inverse d’une pile.
Ces deux algorithmes doivent restituer leur entrée inchangée.
Solution :
#include <iostream>
using namespace std ;
struct elemenet
{
int data ;
struct elemenet * next ;
};
typedef struct elemenet Element ;
typedef Element * Stack ;
typedef Element * Queue ;
Stack create_stack()
{
return NULL ;
}
bool is_empty_stack(Stack stk)
{
if(stk == NULL)
return true ;
else
return false ;
}
int depth_stack(Stack stk)
{
Stack ptr = stk ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Stack push(Stack stk, int val)
{
Stack ptr = new Element ;
ptr->data = val ;
ptr->next = stk ;
stk = ptr ;
return stk ;
}
Stack pop(Stack stk, int &val)
{
if(!is_empty_stack(stk))
{
Stack ptr = stk ;
val = stk->data ;
stk = stk->next ;
delete ptr ;
return stk ;
}
else
{
cout << "Error, the stack is already empty." << endl ;
return NULL ;
}
}
int top_stack(Stack stk)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return 0 ;
}
return stk->data ;
}
Stack replace_top_stack(Stack stk, int val)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return NULL ;
}
stk->data = val ;
return stk ;
}
void display_stack(Stack stk)
{
Stack ptr = stk ;
if(is_empty_stack(stk))
{
cout << "Stack is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
Queue create_queue()
{
return NULL ;
}
bool is_empty_queue(Queue que)
{
if(que == NULL)
return true ;
else
return false ;
}
int length_queue(Queue que)
{
Queue ptr = que ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Queue enqueue(Queue que, int val)
{
Queue elm = new Element ;
elm->data = val ;
elm->next = NULL ;
if(is_empty_queue(que))
{
que = elm ;
return que ;
}
Queue ptr = que ;
while(ptr->next != NULL)
ptr = ptr->next ;
ptr->next = elm ;
return que ;
}
Queue dequeue(Queue que, int &val)
{
if(!is_empty_queue(que))
{
Queue ptr = que ;
val = que->data ;
que = que->next ;
delete ptr ;
return que ;
}
else
{
cout << "Error, the queue is already empty." << endl ;
return NULL ;
}
}
int tail_queue(Queue que)
{
if(is_empty_queue(que))
{
cout << "Error, Queue is empty." << endl ;
return 0 ;
}
return que->data ;
}
int head_queue(Queue que)
{
if(is_empty_queue(que))
{
cout << "Error, Queue is empty." << endl ;
return 0 ;
}
Queue ptr = que ;
while(ptr->next != NULL)
ptr = ptr->next ;
return ptr->data ;
}
void display_queue(Queue que)
{
Queue ptr = que ;
if(is_empty_queue(que))
{
cout << "Queue is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
Queue reverse_queue(Queue &que)
{
Queue rst = create_queue() ;
Stack stk = create_stack() ;
int val ;
for(int i = 0 ; i < length_queue(que) ; i++)
{
que = dequeue(que, val) ;
que = enqueue(que, val) ;
stk = push(stk, val) ;
}
while(!is_empty_stack(stk))
{
stk = pop(stk, val) ;
rst = enqueue(rst, val) ;
}
return rst ;
}
Stack reverse_stack(Stack &stk)
{
Stack rst = create_stack() ;
Stack tmp = create_stack() ;
int val ;
while(!is_empty_stack(stk))
{
stk = pop(stk, val) ;
rst = push(rst, val) ;
tmp = push(tmp, val) ;
}
while(!is_empty_stack(tmp))
{
tmp = pop(tmp, val) ;
stk = push(stk, val) ;
}
return rst ;
}
int main()
{
Queue que = create_queue() ;
que = enqueue(que, 1) ;
que = enqueue(que, 2) ;
que = enqueue(que, 3) ;
display_queue(que) ;
Queue q2 = reverse_queue(que) ;
display_queue(q2) ;
Stack stk = create_stack() ;
stk = push(stk, 1) ;
stk = push(stk, 2) ;
stk = push(stk, 3) ;
display_stack(stk) ;
Stack s2 = reverse_stack(stk) ;
display_stack(s2) ;
return 0 ;
}
Exercice 4 : (Inverser une pile)
Écrire un algorithme utilisant une pile (implémentée sous forme de liste chaînée) qui affiche une liste chaînée d’entiers à l’envers.
Solution :
#include <iostream>
using namespace std ;
struct elemenet
{
int data ;
struct elemenet * next ;
};
typedef struct elemenet Element ;
typedef Element * Stack ;
Stack create_stack()
{
return NULL ;
}
bool is_empty_stack(Stack stk)
{
if(stk == NULL)
return true ;
else
return false ;
}
int depth_stack(Stack stk)
{
Stack ptr = stk ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Stack push(Stack stk, int val)
{
Stack ptr = new Element ;
ptr->data = val ;
ptr->next = stk ;
stk = ptr ;
return stk ;
}
Stack pop(Stack stk, int &val)
{
if(!is_empty_stack(stk))
{
Stack ptr = stk ;
val = stk->data ;
stk = stk->next ;
delete ptr ;
return stk ;
}
else
{
cout << "Error, the stack is already empty." << endl ;
return NULL ;
}
}
int top_stack(Stack stk)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return 0 ;
}
return stk->data ;
}
Stack replace_top_stack(Stack stk, int val)
{
if(is_empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return NULL ;
}
stk->data = val ;
return stk ;
}
void display_stack(Stack stk)
{
Stack ptr = stk ;
if(is_empty_stack(stk))
{
cout << "Stack is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
Stack reverse_stack(Stack stk)
{
Stack tmp = create_stack() ;
int val ;
while(!is_empty_stack(stk))
{
stk = pop(stk, val) ;
tmp = push(tmp, val) ;
}
return tmp ;
}
int main()
{
Stack stk = create_stack() ;
stk = push(stk, 1) ;
stk = push(stk, 2) ;
stk = push(stk, 3) ;
display_stack(stk) ;
stk = reverse_stack(stk) ;
display_stack(stk) ;
return 0 ;
}Exercice 5 : (Vérification de parenthèses)
Un fichier texte peut contenir des parenthèses ( ), des crochets [ ], et des accolades { }. Ces éléments peuvent être imbriqués les uns dans les autres (exemple : {a*(b+c[-d])[{e- f }(-g)]} )
Écrire une fonction qui parcourt le fichier texte et détermine si le fichier est correctement parenthèses, c’est-à-dire si toutes les parenthèses, crochets, etc. sont bien refermés par un caractère du même type, et si les parenthèses, crochets et accolades sont correctement imbriqués. Exemple de fichier incorrect : ({)}.
NB : Pour l’exercice n°5 le fichier texte peut être remplacé par une chaine de caractères si les étudiants(es) ne maitrisent pas la notion et l’utilisation des fichiers.
Solution :
#include <iostream>
using namespace std ;
struct elemenet
{
char data ;
struct elemenet * next ;
};
typedef struct elemenet Element ;
typedef Element * Stack ;
Stack create_stack()
{
return NULL ;
}
bool empty_stack(Stack stk)
{
if(stk == NULL)
return true ;
else
return false ;
}
int depth_stack(Stack stk)
{
Stack ptr = stk ;
int count = 0 ;
while(ptr != NULL)
{
count++ ;
ptr = ptr->next ;
}
return count ;
}
Stack push(Stack stk, int val)
{
Stack ptr = new Element ;
ptr->data = val ;
ptr->next = stk ;
stk = ptr ;
return stk ;
}
Stack pop(Stack stk, int &val)
{
if(!empty_stack(stk))
{
Stack ptr = stk ;
val = stk->data ;
stk = stk->next ;
delete ptr ;
return stk ;
}
else
{
cout << "Error, the stack is already empty." << endl ;
return NULL ;
}
}
int top_stack(Stack stk)
{
if(empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return 0 ;
}
return stk->data ;
}
Stack replace_top_stack(Stack stk, int val)
{
if(empty_stack(stk))
{
cout << "Error, Stack is empty." << endl ;
return NULL ;
}
stk->data = val ;
return stk ;
}
void display_stack(Stack stk)
{
Stack ptr = stk ;
if(empty_stack(stk))
{
cout << "Stack is empty." << endl ;
return ;
}
while(ptr != NULL)
{
cout << ptr->data << " " ;
ptr = ptr->next ;
}
cout << endl ;
return ;
}
bool parentheses_match(char * str)
{
Stack stk = create_stack() ;
int val ;
int i = 0 ;
while(str[i] != '\0')
{
if((str[i] == '(')||(str[i] == ')')||(str[i] == '[')||(str[i] == ']')||(str[i] == '{')||(str[i] == '}'))
{
if((str[i] == '(')||(str[i] == '{')||(str[i] == '['))
{
stk = push(stk, str[i]) ;
}
else
{
if(empty_stack(stk))
{
return false ;
}
else
{
if(((str[i] == ')')&&(top_stack(stk) == '('))||((str[i] == '}')&&(top_stack(stk) == '{'))||((str[i] == ']')&&(top_stack(stk) == '[')))
{
stk = pop(stk, val) ;
}
else
{
while(!empty_stack(stk))
stk = pop(stk, val) ; // drain the stack
return false ;
}
}
}
}
i++ ;
}
if(empty_stack(stk))
return true ;
else
{
while(!empty_stack(stk))
stk = pop(stk, val) ;// drain the stack
return false ;
}
}
int main()
{
char str[50] ;
cin >> str ;
if(parentheses_match(str))
{
cout << "The expression matches parenthesis." ;
}
else
{
cout << "The expression doesn't match parenthesis." ;
}
return 0 ;
}