--- /dev/null
+/******************************************************************************/
+/* examen algo II avec implantation */
+/* des expressions arithmetiques */
+/******************************************************************************/
+
+
+/* Exercice 1 : questions de cours (correction rapide)
+
+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.
+La recherche d'une valeur est alors immediate : calcul de la cle puis acces a l'element d'indice cle dans le tableau.
+
+2) Dans le pire des cas, AVL car O(log n) pour recherche, insertion et suppression.
+Et aussi, tableau (trie) avec methode dichotomique, mais O(log n) pour la recherche seulement.
+
+3) En moyenne, Hachage car O(1) pour recherche, insertion et suppression.
+
+4) Dans une feuille.
+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).
+*/
+
+
+/* Exercice 2 : expressions arithmetiques*/
+
+/* remarques : pour l'examen, algorithmes en pseudo-code,
+avec des libertes possibles comme dire "la valeur est un operateur".
+Bien entendu, il y a plusieurs facon de rediger un algo.
+*/
+
+#include <stdio.h>
+#include <stdlib.h>
+
+
+#include <stdio.h>
+#include <stdlib.h>
+
+typedef char element;
+
+typedef struct noeud {
+ element valeur;
+ struct noeud *gauche;
+ struct noeud *droit;
+} NOEUD, *EA;
+
+
+/* Creation d'un arbre vide */
+NOEUD *arbre_vide()
+{
+ return NULL;
+}
+
+
+/* Affichage du contenu de l'arbre (parcours infixe) */
+void affiche(NOEUD * p)
+{
+ if (p) {
+ if (p->gauche != NULL)
+ printf("( "); /* p est une feuille (si gauche null alors droit aussi) */
+ affiche(p->gauche);
+ printf("%c ", p->valeur);
+ affiche(p->droit);
+ if (p->droit != NULL)
+ printf(") "); /* p est une feuille (si droit null alors gauche aussi) */
+ }
+}
+
+
+/* Test si un arbre est bien une EA valide */
+int est_valide(NOEUD * p)
+{
+ if (p == NULL)
+ return 1;
+ else if (p->valeur == '+' || p->valeur == '-' || p->valeur == '*'
+ || p->valeur == '/')
+ return (est_valide(p->gauche) && est_valide(p->droit));
+ else
+ return (p->gauche == NULL && p->droit == NULL);
+}
+
+
+/* Test si deux arbres sont egaux (identiques) */
+int egal(NOEUD * A1, NOEUD * A2)
+{
+ if (A1 == NULL || A2 == NULL)
+ return (A1 == NULL && A2 == NULL);
+ else
+ return ((A1->valeur == A2->valeur)
+ && egal(A1->gauche, A2->gauche)
+ && egal(A1->droit, A2->droit));
+}
+
+
+/* Evaluation d'une EA (un arbre) */
+int eval(NOEUD * p)
+{
+ if (p->valeur == '+')
+ return eval(p->gauche) + eval(p->droit);
+ else if (p->valeur == '-')
+ return eval(p->gauche) - eval(p->droit);
+ else if (p->valeur == '*')
+ return eval(p->gauche) * eval(p->droit);
+ else if (p->valeur == '/')
+ return eval(p->gauche) / eval(p->droit);
+ else
+ return atoi(&p->valeur); /* convertion du char en int */
+}
+
+
+/* Construction de l'arbre correspondant a une EA lue au clavier */
+NOEUD *construit(char courant)
+{
+ NOEUD *p = NULL;
+
+ /* printf("traitement de %c\n",courant); */
+
+ if (courant != '(' && courant != ')' && courant != '+'
+ && courant != '-' && courant != '*' && courant != '/') {
+ p = (NOEUD *) malloc(sizeof(NOEUD));
+ p->valeur = courant;
+ p->gauche = NULL;
+ p->droit = NULL;
+ } else { /* courant est '(' */
+ /* l'EA est de la forme (E1 operateur E2) */
+
+ /* lecture de E1 */
+ char courant2;
+ scanf("%c", &courant2);
+ getchar();
+ p = (NOEUD *) malloc(sizeof(NOEUD));
+ /* traitement de E1 */
+ p->gauche = construit(courant2);
+
+ /* lecture de l'operateur */
+ char courant3;
+ scanf("%c", &courant3);
+ getchar();
+ p->valeur = courant3;
+
+ /* lecture de E2 */
+ char courant4;
+ scanf("%c", &courant4);
+ getchar();
+ /* traitement de E2 */
+ p->droit = construit(courant4);
+
+ /* lecture de ')' */
+ char courant5;
+ scanf("%c", &courant5);
+ getchar();
+ }
+
+ return p;
+}
+
+
+
+
+/* Affichage de l'arbre (sous forme arborescente) */
+void affiche_arbre(NOEUD * p, int col)
+{
+ int i;
+ if (p) {
+ affiche_arbre(p->droit, col + 1);
+ for (i = 0; i < col; i++)
+ printf(" ");
+ printf("%c\n", p->valeur);
+ affiche_arbre(p->gauche, col + 1);
+ }
+}
+
+
+/* Destruction de l'arbre de racine p en recuperant la place occupee (free) par chacun des noeuds */
+NOEUD *detruis_arbre(NOEUD * p)
+{
+ if (p == NULL)
+ return p;
+ else {
+ p->gauche = detruis_arbre(p->gauche);
+ p->droit = detruis_arbre(p->droit);
+ free(p);
+ p = NULL;
+ return p;
+ }
+}
+
+
+/* Creation d'un noeud */
+NOEUD *cree_noeud(char valeur, NOEUD * filsgauche, NOEUD * filsdroit)
+{
+ NOEUD *p = (NOEUD *) malloc(sizeof(NOEUD));
+ p->valeur = valeur;
+ p->gauche = filsgauche;
+ p->droit = filsdroit;
+ return p;
+}
+
+
+/****************************************************************************/
+main()
+{
+ NOEUD *ea = arbre_vide();
+
+ /* creation "a la main" de (9 + (3 * 2)) */
+ NOEUD *feuille9 = cree_noeud('9', NULL, NULL);
+ NOEUD *feuille3 = cree_noeud('3', NULL, NULL);
+ NOEUD *feuille2 = cree_noeud('2', NULL, NULL);
+ NOEUD *ea2 = cree_noeud('*', feuille3, feuille2);
+ ea = cree_noeud('+', feuille9, ea2);
+
+ printf("expression arithmetique : \n");
+ affiche(ea);
+ printf("\n");
+ affiche_arbre(ea, 0);
+
+ int valide = est_valide(ea);
+ if (valide == 1)
+ printf("l'expression est valide\n");
+ else
+ printf("l'expression n'est pas valide\n");
+
+ int resultat = eval(ea);
+ printf("resultat = %d\n", resultat);
+
+
+ /* test egalite */
+ NOEUD *eab = arbre_vide();
+ NOEUD *feuille9b = cree_noeud('9', NULL, NULL);
+ NOEUD *feuille3b = cree_noeud('3', NULL, NULL);
+ NOEUD *feuille2b = cree_noeud('2', NULL, NULL);
+ NOEUD *ea2b = cree_noeud('*', feuille3b, feuille2b);
+ eab = cree_noeud('+', feuille9b, ea2b);
+ printf("\nexpression arithmetique 2 : \n");
+ affiche(eab);
+ printf("\n");
+
+ int egalite = egal(ea, eab);
+ if (egalite == 1)
+ printf("les 2 expressions sont identiques\n");
+ else
+ printf("les 2 expressions ne sont pas identiques\n");
+
+
+ /* test construction */
+ printf
+ ("\nsaisir une expression arithmetique (un caractere a la fois) : \n");
+ char courant;
+ scanf("%c", &courant);
+ getchar(); /* lecture de '(' */
+ ea = construit(courant);
+
+ printf("expression arithmetique : \n");
+ affiche(ea);
+ printf("\n");
+ affiche_arbre(ea, 0);
+ printf("resultat = %d\n", eval(ea));
+}
+
+/***** exemple d'execution ********************************************
+expression arithmetique :
+( 9 + ( 3 * 2 ) )
+ 2
+ *
+ 3
++
+ 9
+l'expression est valide
+resultat = 15
+
+expression arithmetique 2 :
+( 9 + ( 3 * 2 ) )
+les 2 expressions sont identiques
+
+saisir une expression arithmetique (un caractere a la fois) :
+(
+9
++
+(
+3
+*
+2
+)
+)
+expression arithmetique :
+( 9 + ( 3 * 2 ) )
+ 2
+ *
+ 3
++
+ 9
+resultat = 15
+*******************************************************************/
repositories / Algorithmic_C.git / blobdiff