Exercices d'algorithme : Piles et Files d'attente
Exercice 1 :
Soient Q et P une file et une pile non vides, respectivement. En utilisant seulement une seule variable et les opérations de la classe PILE ET FILE, écrire un algorithme qui renverse l’ordre des éléments de Q.
Réimplanter la fonction fibr ci-dessous en
utilisant une pile pour remplacer les
appels récursifs.
long fibr(int n) {
assert((n>0) &&
(n<47) // les données dans cet intervalle sinon erreur
if ( (n = = 1) || (n = =2)
return 1;
else return fibr(n-1) +
fibr(n-2);
} // fin de la fonction
Exercice 2 :
Soient Q et P une file et une pile non vides, respectivement. En utilisant seulement une seule variable et les opérations de la classe PILE ET FILE, écrire un algorithme qui renverse l’ordre des éléments de Q.
Exercice 3 :
Un problème
fréquent d’un compilateur et des traitements de textes est de déterminer si les parenthèses d’une chaîne de caractères sont balancées et
proprement incluses l’une dans l’une.
Par exemple, la chaîne ((( ) ) ( ) ) ( ) est bien balancée et proprement
écrite. Mais les chaînes )( )( ou ( ) ) ne le sont pas.
- écrire un algorithme qui retourne TRUE si une chaîne de caractères est proprement écrite et bien balancée, et FALSE sinon. Utiliser pour cela une pile.
- Écrire un algorithme qui retourne la position de la première parenthèse qui déroge à cette règle si la chaîne n’est pas bien écrite et bien balancée. Utiliser une PILE pour résoudre ce problème.
#include
RépondreSupprimer#include
#include
#include
const max=3;
typedef struct pile{
int sommet;
char t[];
}pile;
void creer_pvide( pile p){
p.sommet=0;
}
bool est_vide ( pile p){
if(p.sommet==0)
return true;
return false;
}
bool est_plein ( pile p){
if(p.sommet==max)
return true;
return false;
}
void empiler(char x,struct pile *p){
if (est_plein(*p))
printf("la pile est plein");
else{
(*p).sommet++;
(*p).t[(*p).sommet]=x;
}
}
void depiler( pile *p){
if(est_vide(*p))
printf("error !! pile est vide");
else
(*p).sommet--;
}
int psommet( pile p){
return p.t[p.sommet];
}
int taille( pile p){
return p.sommet;
}
/*
def bien_parenthese(txt):
bp = True
p = construit_pile()
i = 0
while bp and i < len(txt):
if txt[i] == "(" or txt[i] == "[":
empile(p, txt[i])
elif txt[i] == ")":
if sommet(p) != "(":
bp = False
else:
depile(p)
elif txt[i] == "]":
if sommet(p) != "[":
bp = False
else:
depile(p)
i = i+1
if not pile_vide(p):
bp = False
return bp
*/
char caract_over(char x){
if ((x=='(')||(x=='[')||(x=='{'))
return x;
}
bool est_balance(char tab[]){
pile *p;
bool bo=true;
creer_pvide(*p);
int i=0;
while(i<strlen(tab) && bo==true){
if(caract(tab[i]))
empiler(tab[i],&(*p));
else {
switch(tab[i]){
case ')': if (psommet(*p)!='(')
bo=false;
else
depiler(&(*p));
case ']': if (psommet(*p)!='[')
bo=false;
else
depiler(&(*p));
case '}': if (psommet(*p)!='{')
bo=false;
else
depiler(&(*p));
}
}
i++;
}
return bo;
}
int main(int argc, char *argv[]) {
char t[20];
printf("donner l'expression :");
scanf("%s",t);
est_balance(t);
scanf("%s",t);
return 0;
}
c'est très compréhensif vos exercices...
RépondreSupprimerMerci bien les gars
#include
RépondreSupprimer#include
#include
#include
////////////////declaraton de type maillon ////////////////
typedef struct tmaillon{
char info ; struct tmaillon *suiv ;} maillon ;
///////////////////////////////////
///////////////////
typedef maillon *pile ; //////pour dire de pile eest un struct tmaillon//////////////
///////////creation d'une pile vide///////////////
void initpile(pile *p ){ *p = NULL ;}
/////fonction qui verifier si la pile est vide ou nn //////////////
bool pilevide(pile p){return (p == NULL);}
void depile(pile *p , char *x){
pile sauv ;
if (p ==NULL) {printf("la pile est vide ");}
else { *x =(*p)->info ;sauv = *p ; (*p)=(*p)->suiv ; free(sauv);}}
///////////////////////////////////////////////////////////////////////////
void empile(pile *p , char x ) {
pile nouv ;
nouv = malloc(sizeof(maillon));
nouv->info = x ;
nouv->suiv = *p ;
*p = nouv ;}
///////////////////////////////
bool parenthes(char ch[]){
pile p ; int i ; int n=strlen(ch) ; char x ; bool stop ;
i =0 ;
initpile(&p);
stop = false;
while(i<=n && !stop){
if(ch[i]=='('){empile(&p,ch[i]);}
else { if(ch[i]==')') {
if(pilevide(p)){stop = true ;}
else {depile(&p,&x);}}} i++ ; }
if(!stop && pilevide(p)) {return true;}
else { return false;}}
////////////////////////////////////
main() {
char ch[100] ;
printf("donne la chaine : ");
gets(ch);
////scanf("%s",ch); si je declare une chaine et j fait un espace danc vas sortir de la licture
if(parenthes(ch)){printf("la chaine est bien balence");}
else{printf("la chaine n'est pas bien balence ");}
}