#define _C_td8 /* * ---------------------------------------------------------------------------- * * Fichier : td8.c * Langage : C ANSI * Auteur : F. Boyer * Creation : 7 septembre 1997 * ---------------------------------------------------------------------------- * Description : * Programme de traitement d'expressions arithmetiques entieres. Les fonctions * fournies par ce programme permettent de construire un arbre * binaire representant une expression arithmetique, et d'evaluer * une expression arithmetique etant donne l'arbre la representant. * Ces fonctions sont destinees a etre appelees par un autre programme * qui se charge de l'analyse d'une expression arithmetique. * En outre, les fonctions (sauve et restaure) sont egalement fournies * pour permettre de sauvegarder et restaurer un arbre representant une * expression arithmetique donnee. * * ---------------------------------------------------------------------------- * Interventions * >>>>>>>>>>>>> * ---------------------------------------------------------------------------- * Fonctions definies * Locales : * Exportees : main. * * ---------------------------------------------------------------------------- */ /****************************************************************************/ /*------------------- INCLUSION DES INTERFACES SYSTEMES --------------------*/ /****************************************************************************/ #include #include /****************************************************************************/ /*----------------- INCLUSION DES INTERFACES APPLICATIVES ------------------*/ /****************************************************************************/ #include "td8.h" /****************************************************************************/ /*------------------- CONSTANTES, MACROS & TYPES LOCAUX --------------------*/ /****************************************************************************/ /****************************************************************************/ /*------------------- SIGNATURES DES FONCTIONS LOCALES ---------------------*/ /****************************************************************************/ static long fct_eval_plus (t_noeud *); static long fct_eval_moins (t_noeud *); static long fct_eval_mul (t_noeud *); static long fct_eval_div (t_noeud *); static long fct_eval_moins_un (t_noeud *); static long fct_eval_litteral (t_noeud *); static void fct_sauv_plus (FILE *, t_noeud *); static void fct_sauv_moins (FILE *, t_noeud *); static void fct_sauv_mul (FILE *, t_noeud *); static void fct_sauv_div (FILE *, t_noeud *); static void fct_sauv_moins_un (FILE *, t_noeud *); static void fct_sauv_litteral (FILE *, t_noeud *); /****************************************************************************/ /*------------------- DEFINITIONS DES VARIABLES LOCALES --------------------*/ /****************************************************************************/ /****************************************************************************/ /*------------------- IMPLANTATION DES FONCTIONS LOCALES -------------------*/ /****************************************************************************/ /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_plus * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est +. * ---------------------------------------------------------------------------- */ static long fct_eval_plus ( t_noeud *noeud) { return(((noeud->noeud_g)->fct_eval(noeud->noeud_g)) + ((noeud->noeud_d)->fct_eval(noeud->noeud_d))); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_moins * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est -. * ---------------------------------------------------------------------------- */ static long fct_eval_moins ( t_noeud *noeud) { return(((noeud->noeud_g)->fct_eval(noeud->noeud_g)) - ((noeud->noeud_d)->fct_eval(noeud->noeud_d))); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_mul * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est *. * ---------------------------------------------------------------------------- */ static long fct_eval_mul ( t_noeud *noeud) { return(((noeud->noeud_g)->fct_eval(noeud->noeud_g)) * ((noeud->noeud_d)->fct_eval(noeud->noeud_d))); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_div * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est *. * ---------------------------------------------------------------------------- */ static long fct_eval_div ( t_noeud *noeud) { return(((noeud->noeud_g)->fct_eval(noeud->noeud_g)) / ((noeud->noeud_d)->fct_eval(noeud->noeud_d))); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_moins_un * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est le - unaire. * ---------------------------------------------------------------------------- */ static long fct_eval_moins_un ( t_noeud *noeud) { return(-((noeud->noeud_g)->fct_eval(noeud->noeud_g))); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_litteral * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * noeud est un litteral. * ---------------------------------------------------------------------------- */ static long fct_eval_litteral ( t_noeud *noeud) { return(noeud->val); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_sauv_plus * Resultat : * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud adresse du noeud representant l'expression * Description : * Sauve l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est +. * ---------------------------------------------------------------------------- */ static void fct_sauv_plus ( FILE *f, t_noeud *noeud) { char c = 'p'; fwrite(&c, sizeof(c), 1, f); (noeud->noeud_g)->fct_sauv(f, noeud->noeud_g); (noeud->noeud_d)->fct_sauv(f, noeud->noeud_d); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_eval_moins * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est -. * ---------------------------------------------------------------------------- */ static void fct_sauv_moins ( FILE *f, t_noeud *noeud) { char c = 's'; fwrite(&c, sizeof(c), 1, f); (noeud->noeud_g)->fct_sauv(f, noeud->noeud_g); (noeud->noeud_d)->fct_sauv(f, noeud->noeud_d); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_sauv_mul * Resultat : * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud adresse du noeud representant l'expression * Description : * Sauve l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est *. * ---------------------------------------------------------------------------- */ static void fct_sauv_mul ( FILE *f, t_noeud *noeud) { char c = 'm'; fwrite(&c, sizeof(c), 1, f); (noeud->noeud_g)->fct_sauv(f, noeud->noeud_g); (noeud->noeud_d)->fct_sauv(f, noeud->noeud_d); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_sauv_div * Resultat : Valeur evaluee de l'expression arithmetique representee * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud adresse du noeud representant l'expression * Description : * Evalue l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est *. * ---------------------------------------------------------------------------- */ static void fct_sauv_div ( FILE *f, t_noeud *noeud) { char c = 'd'; fwrite(&c, sizeof(c), 1, f); (noeud->noeud_g)->fct_sauv(f, noeud->noeud_g); (noeud->noeud_d)->fct_sauv(f, noeud->noeud_d); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_sauv_moins_un * Resultat : * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud adresse du noeud representant l'expression * Description : * Sauve l'expression arithmetique representee par noeud, sachant que * l'operateur associe a noeud est le - unaire. * ---------------------------------------------------------------------------- */ static void fct_sauv_moins_un ( FILE *f, t_noeud *noeud) { char c = 'n'; fwrite(&c, sizeof(c), 1, f); (noeud->noeud_g)->fct_sauv(f, noeud->noeud_g); } /* * ---------------------------------------------------------------------------- * * Fonction : fct_sauv_litteral * Resultat : * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud adresse du noeud representant l'expression * Description : * Sauve l'expression arithmetique representee par noeud, sachant que * noeud est un litteral. * ---------------------------------------------------------------------------- */ void fct_sauv_litteral ( FILE *f, t_noeud *noeud) { char c = 'l'; fwrite(&c, sizeof(c), 1, f); fwrite(&(noeud->val), sizeof(noeud->val), 1, f); } /****************************************************************************/ /*------------------ IMPLANTATION DES FONCTIONS EXPORTEES ------------------*/ /****************************************************************************/ /* * ---------------------------------------------------------------------------- * * Fonction : sauve * Resultat : * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * noeud t_noeud * l'expression arithmetique a sauvegarder * Description : * Sauvegarde l'arbre correspondant a l'expression arithmetique donnee * dans le fichier donne. * ---------------------------------------------------------------------------- */ void sauve ( FILE *f, t_noeud *noeud) { noeud->fct_sauv(f, noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : restaure * Resultat : * noeud racine de l'arbre construit * Parametres : * Nom Type Role * f FILE* descripteur du fichier de sauvegarde * Description : * Restaure l'arbre correspondant a l'expression arithmetique sauvegardee * dans le fichier donne. * ---------------------------------------------------------------------------- */ t_noeud *restaure ( FILE *f) { t_noeud *n; t_noeud *n_g; t_noeud *n_d; char c; long l; fread(&c, sizeof(c), 1, f); switch(c) { case 'l' : /* litteral */ fread(&l, sizeof(l), 1, f); n = cons_litteral(l); break; case 'p' : /* plus */ n_g = restaure(f); n_d = restaure(f); n = cons_plus(n_g, n_d); break; case 's' : /* moins */ n_g = restaure(f); n_d = restaure(f); n = cons_moins(n_g, n_d); break; case 'm' : /* mul */ n_g = restaure(f); n_d = restaure(f); n = cons_mul(n_g, n_d); break; case 'd' : /* div */ n_g = restaure(f); n_d = restaure(f); n = cons_div(n_g, n_d); break; case 'n' : /* moins unaire */ n_g = restaure(f); n = cons_moins_un(n_g); break; } return(n); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_plus * Resultat : 0 si erreur. adresse du noeud construit sinon. * Parametres : les adresses des noeuds fils (gauche et droit) * Nom Type Role * noeud_d t_noeud adresse du noeud representant la 1ere operande * noeud_g t_noeud adresse du noeud representant la 2eme operande * Description : * construit un sous-arbre dont la racine correspond a l'operateur + * et les noeud fils representent les operandes. * ---------------------------------------------------------------------------- */ t_noeud * cons_plus( t_noeud *noeud_g, t_noeud *noeud_d) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_plus; noeud->fct_sauv = fct_sauv_plus; noeud->noeud_g = noeud_g; noeud->noeud_d = noeud_d; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_moins * Resultat : 0 si erreur. adresse du noeud construit sinon. * Parametres : les adresses des noeuds fils (gauche et droit) * Nom Type Role * noeud_d t_noeud adresse du noeud representant la 1ere operande * noeud_g t_noeud adresse du noeud representant la 2eme operande * Description : * construit un sous-arbre dont la racine correspond a l'operateur - * et les noeud fils representent les operandes. * ---------------------------------------------------------------------------- */ t_noeud * cons_moins( t_noeud *noeud_g, t_noeud *noeud_d) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_moins; noeud->fct_sauv = fct_sauv_moins; noeud->noeud_g = noeud_g; noeud->noeud_d = noeud_d; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_mul * Resultat : 0 si erreur.adresse du noeud construit sinon. * Parametres : les adresses des noeuds fils (gauche et droit) * Nom Type Role * noeud_d t_noeud adresse du noeud representant la 1ere operande * noeud_g t_noeud adresse du noeud representant la 2eme operande * Description : * construit un sous-arbre dont la racine correspond a l'operateur * * et les noeud fils representent les operandes. * ---------------------------------------------------------------------------- */ t_noeud * cons_mul( t_noeud *noeud_g, t_noeud *noeud_d) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_mul; noeud->fct_sauv = fct_sauv_mul; noeud->noeud_g = noeud_g; noeud->noeud_d = noeud_d; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_div * Resultat : 0 si erreur. adresse du noeud construit sinon. * Parametres : les adresses des noeuds fils (gauche et droit) * Nom Type Role * noeud_d t_noeud adresse du noeud representant la 1ere operande * noeud_g t_noeud adresse du noeud representant la 2eme operande * Description : * construit un sous-arbre dont la racine correspond a l'operateur / * et les noeud fils representent les operandes. * ---------------------------------------------------------------------------- */ t_noeud * cons_div( t_noeud *noeud_g, t_noeud *noeud_d) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_div; noeud->fct_sauv = fct_sauv_div; noeud->noeud_g = noeud_g; noeud->noeud_d = noeud_d; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_moins_un * Resultat : 0 si erreur. adresse du noeud construit sinon. * Parametres : l'adresse du noeuds fils * Nom Type Role * noeud_g t_noeud adresse du noeud representant l'operande * Description : * construit un sous-arbre dont la racine correspond a l'operateur + * et les noeud fils representent les operandes. * ---------------------------------------------------------------------------- */ t_noeud * cons_moins_un( t_noeud *noeud_g) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_moins_un; noeud->fct_sauv = fct_sauv_moins_un; noeud->noeud_g = noeud_g; noeud->noeud_d = NULL; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : cons_litteral * Resultat : 0 si erreur. adresse du noeud construit sinon. * Parametres : * Nom Type Role * val long la valeur entiere * Description : * construit un sous-arbre dont la racine correspond au litteral donne * ---------------------------------------------------------------------------- */ t_noeud * cons_litteral( long val) { t_noeud *noeud; if ((noeud = (t_noeud *) malloc(sizeof(t_noeud))) == NULL) { printf("Erreur dans l'allocation memoire\n"); exit(-1); } noeud->fct_eval = fct_eval_litteral; noeud->fct_sauv = fct_sauv_litteral; noeud->val = val; return(noeud); } /* * ---------------------------------------------------------------------------- * * Fonction : main * Resultat : int Code d'erreur commande. * Parametres : * Nom Type Role * * Description : * Point d'entree du programme "tdXX" obtenu par compilation du fichier * "td8.c" (cc -o td8 td8.c). Point d'entree utilise uniquement pour les * tests. * * ---------------------------------------------------------------------------- */ int main() { FILE * f; t_noeud * n1; t_noeud * n2; t_noeud * n3; t_noeud * n4; t_noeud * n5; t_noeud * n6; t_noeud * n; long res; n1 = cons_litteral(3); n2 = cons_litteral(4); n3 = cons_plus(n1,n2); n4 = cons_litteral(34); n5 = cons_moins_un(n4); n6 = cons_mul(n3,n5); res = n6->fct_eval(n6); printf("Resultat : %d\n", res); f = fopen("exp_arith","w"); sauve(f, n6); fclose(f); printf("Sauvegarde terminee\n"); f = fopen("exp_arith","r"); n = restaure(f); fclose(f); res = n->fct_eval(n); printf("Resultat apres restauration: %d\n", res); return(0); }