exam2/ExamenAlgo2correction.c

   1 /******************************************************************************/
   2 /*                     examen algo II avec implantation                       */
   3 /*                       des expressions arithmetiques                        */
   4 /******************************************************************************/
   5
   6
   7 /* Exercice 1 : questions de cours (correction rapide)
   8
   9 1) Utilisation d'une fonction de hachage sur une valeur pour calculer la cle qui est alors utilisee pour ranger la valeur dans un tableau a l'indice cle.
  10 La recherche d'une valeur est alors immediate : calcul de la cle puis acces a l'element d'indice cle dans le tableau.
  11
  12 2) Dans le pire des cas, AVL car O(log n) pour recherche, insertion et suppression.
  13 Et aussi, tableau (trie) avec methode dichotomique, mais O(log n) pour la recherche seulement.
  14
  15 3) En moyenne, Hachage car O(1) pour recherche, insertion et suppression.
  16
  17 4) Dans une feuille.
  18 Par l'absurde, si l'element de plus petite priorite n'est pas dans une feuille alors cela signifie qu'il existe un noeud fils de plus grande priorite. Contradiction avec la definition d'un tas (tout noeud est >= a chacun de ses fils).
  19 */
  20
  21
  22 /* Exercice 2 : expressions arithmetiques*/
  23
  24 /* remarques : pour l'examen, algorithmes en pseudo-code,
  25 avec des libertes possibles comme dire "la valeur est un operateur".
  26 Bien entendu, il y a plusieurs facon de rediger un algo.
  27 */
  28
  29 #include <stdio.h>
  30 #include <stdlib.h>
  31
  32
  33 #include <stdio.h>
  34 #include <stdlib.h>
  35
  36 typedef char element;
  37
  38 typedef struct noeud {
  39     element valeur;
  40     struct noeud *gauche;
  41     struct noeud *droit;
  42 } NOEUD, *EA;
  43
  44
  45 /* Creation d'un arbre vide */
  46 NOEUD *arbre_vide()
  47 {
  48     return NULL;
  49 }
  50
  51
  52 /* Affichage du contenu de l'arbre (parcours infixe) */
  53 void affiche(NOEUD * p)
  54 {
  55     if (p) {
  56         if (p->gauche != NULL)
  57             printf("( ");       /* p est une feuille (si gauche null alors droit aussi) */
  58         affiche(p->gauche);
  59         printf("%c ", p->valeur);
  60         affiche(p->droit);
  61         if (p->droit != NULL)
  62             printf(") ");       /* p est une feuille (si droit null alors gauche aussi) */
  63     }
  64 }
  65
  66
  67 /* Test si un arbre est bien une EA valide */
  68 int est_valide(NOEUD * p)
  69 {
  70     if (p == NULL)
  71         return 1;
  72     else if (p->valeur == '+' || p->valeur == '-' || p->valeur == '*'
  73              || p->valeur == '/')
  74         return (est_valide(p->gauche) && est_valide(p->droit));
  75     else
  76         return (p->gauche == NULL && p->droit == NULL);
  77 }
  78
  79
  80 /* Test si deux arbres sont egaux (identiques) */
  81 int egal(NOEUD * A1, NOEUD * A2)
  82 {
  83     if (A1 == NULL || A2 == NULL)
  84         return (A1 == NULL && A2 == NULL);
  85     else
  86         return ((A1->valeur == A2->valeur)
  87                 && egal(A1->gauche, A2->gauche)
  88                 && egal(A1->droit, A2->droit));
  89 }
  90
  91
  92 /* Evaluation d'une EA (un arbre) */
  93 int eval(NOEUD * p)
  94 {
  95     if (p->valeur == '+')
  96         return eval(p->gauche) + eval(p->droit);
  97     else if (p->valeur == '-')
  98         return eval(p->gauche) - eval(p->droit);
  99     else if (p->valeur == '*')
 100         return eval(p->gauche) * eval(p->droit);
 101     else if (p->valeur == '/')
 102         return eval(p->gauche) / eval(p->droit);
 103     else
 104         return atoi(&p->valeur);        /* convertion du char en int */
 105 }
 106
 107
 108 /* Construction de l'arbre correspondant a une EA lue au clavier */
 109 NOEUD *construit(char courant)
 110 {
 111     NOEUD *p = NULL;
 112
 113     /* printf("traitement de %c\n",courant); */
 114
 115     if (courant != '(' && courant != ')' && courant != '+'
 116         && courant != '-' && courant != '*' && courant != '/') {
 117         p = (NOEUD *) malloc(sizeof(NOEUD));
 118         p->valeur = courant;
 119         p->gauche = NULL;
 120         p->droit = NULL;
 121     } else {                    /* courant est '(' */
 122         /* l'EA est de la forme (E1 operateur E2) */
 123
 124         /* lecture de E1 */
 125         char courant2;
 126         scanf("%c", &courant2);
 127         getchar();
 128         p = (NOEUD *) malloc(sizeof(NOEUD));
 129         /* traitement de E1 */
 130         p->gauche = construit(courant2);
 131
 132         /* lecture de l'operateur */
 133         char courant3;
 134         scanf("%c", &courant3);
 135         getchar();
 136         p->valeur = courant3;
 137
 138         /* lecture de E2 */
 139         char courant4;
 140         scanf("%c", &courant4);
 141         getchar();
 142         /* traitement de E2 */
 143         p->droit = construit(courant4);
 144
 145         /* lecture de ')' */
 146         char courant5;
 147         scanf("%c", &courant5);
 148         getchar();
 149     }
 150
 151     return p;
 152 }
 153
 154
 155
 156
 157 /* Affichage de l'arbre (sous forme arborescente) */
 158 void affiche_arbre(NOEUD * p, int col)
 159 {
 160     int i;
 161     if (p) {
 162         affiche_arbre(p->droit, col + 1);
 163         for (i = 0; i < col; i++)
 164             printf("   ");
 165         printf("%c\n", p->valeur);
 166         affiche_arbre(p->gauche, col + 1);
 167     }
 168 }
 169
 170
 171 /* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds  */
 172 NOEUD *detruis_arbre(NOEUD * p)
 173 {
 174     if (p == NULL)
 175         return p;
 176     else {
 177         p->gauche = detruis_arbre(p->gauche);
 178         p->droit = detruis_arbre(p->droit);
 179         free(p);
 180         p = NULL;
 181         return p;
 182     }
 183 }
 184
 185
 186 /* Creation d'un noeud */
 187 NOEUD *cree_noeud(char valeur, NOEUD * filsgauche, NOEUD * filsdroit)
 188 {
 189     NOEUD *p = (NOEUD *) malloc(sizeof(NOEUD));
 190     p->valeur = valeur;
 191     p->gauche = filsgauche;
 192     p->droit = filsdroit;
 193     return p;
 194 }
 195
 196
 197 /****************************************************************************/
 198 main()
 199 {
 200     NOEUD *ea = arbre_vide();
 201
 202     /* creation "a la main" de (9 + (3 * 2)) */
 203     NOEUD *feuille9 = cree_noeud('9', NULL, NULL);
 204     NOEUD *feuille3 = cree_noeud('3', NULL, NULL);
 205     NOEUD *feuille2 = cree_noeud('2', NULL, NULL);
 206     NOEUD *ea2 = cree_noeud('*', feuille3, feuille2);
 207     ea = cree_noeud('+', feuille9, ea2);
 208
 209     printf("expression arithmetique : \n");
 210     affiche(ea);
 211     printf("\n");
 212     affiche_arbre(ea, 0);
 213
 214     int valide = est_valide(ea);
 215     if (valide == 1)
 216         printf("l'expression est valide\n");
 217     else
 218         printf("l'expression n'est pas valide\n");
 219
 220     int resultat = eval(ea);
 221     printf("resultat = %d\n", resultat);
 222
 223
 224     /* test egalite */
 225     NOEUD *eab = arbre_vide();
 226     NOEUD *feuille9b = cree_noeud('9', NULL, NULL);
 227     NOEUD *feuille3b = cree_noeud('3', NULL, NULL);
 228     NOEUD *feuille2b = cree_noeud('2', NULL, NULL);
 229     NOEUD *ea2b = cree_noeud('*', feuille3b, feuille2b);
 230     eab = cree_noeud('+', feuille9b, ea2b);
 231     printf("\nexpression arithmetique 2 : \n");
 232     affiche(eab);
 233     printf("\n");
 234
 235     int egalite = egal(ea, eab);
 236     if (egalite == 1)
 237         printf("les 2 expressions sont identiques\n");
 238     else
 239         printf("les 2 expressions ne sont pas identiques\n");
 240
 241
 242     /* test construction */
 243     printf
 244         ("\nsaisir une expression arithmetique (un caractere a la fois) : \n");
 245     char courant;
 246     scanf("%c", &courant);
 247     getchar();                  /* lecture de '(' */
 248     ea = construit(courant);
 249
 250     printf("expression arithmetique : \n");
 251     affiche(ea);
 252     printf("\n");
 253     affiche_arbre(ea, 0);
 254     printf("resultat = %d\n", eval(ea));
 255 }
 256
 257 /***** exemple d'execution ********************************************
 258 expression arithmetique :
 259 ( 9 + ( 3 * 2 ) )
 260       2
 261    *
 262       3
 263 +
 264    9
 265 l'expression est valide
 266 resultat = 15
 267
 268 expression arithmetique 2 :
 269 ( 9 + ( 3 * 2 ) )
 270 les 2 expressions sont identiques
 271
 272 saisir une expression arithmetique (un caractere a la fois) :
 273 (
 274 9
 275 +
 276 (
 277 3
 278 *
 279 2
 280 )
 281 )
 282 expression arithmetique :
 283 ( 9 + ( 3 * 2 ) )
 284       2
 285    *
 286       3
 287 +
 288    9
 289 resultat = 15
 290 *******************************************************************/