1: /*
2: ================================================================================
3: RPL/2 (R) version 4.1.32
4: Copyright (C) 1989-2019 Dr. BERTRAND Joël
5:
6: This file is part of RPL/2.
7:
8: RPL/2 is free software; you can redistribute it and/or modify it
9: under the terms of the CeCILL V2 License as published by the french
10: CEA, CNRS and INRIA.
11:
12: RPL/2 is distributed in the hope that it will be useful, but WITHOUT
13: ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14: FITNESS FOR A PARTICULAR PURPOSE. See the CeCILL V2 License
15: for more details.
16:
17: You should have received a copy of the CeCILL License
18: along with RPL/2. If not, write to info@cecill.info.
19: ================================================================================
20: */
21:
22:
23: #include "rpl-conv.h"
24:
25:
26: /*
27: ================================================================================
28: Fonction d'affichage d'un arbre q-aire
29: ================================================================================
30: Entrées : pointeur sur une structure struct_processus
31: --------------------------------------------------------------------------------
32: Sorties :
33: --------------------------------------------------------------------------------
34: Effets de bord : néant
35: ================================================================================
36: */
37:
38: static void
39: affichage_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre,
40: int niveau)
41: {
42: int i;
43:
44: integer8 branche;
45:
46: struct_liste_chainee *l_element_courant;
47:
48: unsigned char *chaine;
49:
50: if (niveau == 0)
51: {
52: printf("--- Arbre $%016X\n", s_arbre);
53: }
54:
55: // Affichage de la feuille (fonction ou donnée générale s'il n'y
56: // a pas de branche)
57:
58: l_element_courant = (*s_arbre).feuille;
59:
60: for(i = 0; i < niveau; i++)
61: {
62: printf(" ");
63: }
64:
65: while(l_element_courant != NULL)
66: {
67: if ((chaine = formateur(s_etat_processus, 0,
68: (*l_element_courant).donnee)) == NULL)
69: {
70: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
71: return;
72: }
73:
74: printf("%s ", chaine);
75: free(chaine);
76:
77: l_element_courant = (*l_element_courant).suivant;
78: }
79:
80: printf("\n");
81:
82: // Affichage des branches (arguments de la fonction dans la feuille)
83:
84: for(branche = 0; branche < (*s_arbre).nombre_branches; branche++)
85: {
86: affichage_arbre(s_etat_processus, (*s_arbre).branches[branche],
87: niveau + 1);
88: }
89:
90: if (niveau == 0)
91: {
92: printf("--- Fin de l'arbre\n");
93: }
94:
95: return;
96: }
97:
98:
99: /*
100: ================================================================================
101: Fonction de transcription d'un arbre en liste chaînée
102: ================================================================================
103: Entrées : pointeur sur une structure struct_processus
104: --------------------------------------------------------------------------------
105: Sorties :
106: --------------------------------------------------------------------------------
107: Effets de bord : néant
108: ================================================================================
109: */
110:
111: static struct_liste_chainee *
112: transcription_arbre(struct_processus *s_etat_processus, struct_arbre *s_arbre)
113: {
114: integer8 i;
115:
116: struct_liste_chainee *l_element_courant;
117: struct_liste_chainee *l_liste;
118: struct_liste_chainee *l_nouvelle_pile_locale;
119: struct_liste_chainee *l_pile_locale;
120:
121: l_pile_locale = NULL;
122:
123: for(i = 0; i < (*s_arbre).nombre_branches; i++)
124: {
125: if ((l_nouvelle_pile_locale = allocation_maillon(s_etat_processus))
126: == NULL)
127: {
128: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
129: return(NULL);
130: }
131:
132: (*l_nouvelle_pile_locale).suivant = l_pile_locale;
133: l_pile_locale = l_nouvelle_pile_locale;
134:
135: if (((*l_pile_locale).donnee = (void *) transcription_arbre(
136: s_etat_processus, (*s_arbre).branches[i])) == NULL)
137: {
138: return(NULL);
139: }
140: }
141:
142: // Ajout des fonctions
143:
144: l_liste = (*s_arbre).feuille;
145: uprintf("avant free %p\n", s_arbre->branches);
146: free((*s_arbre).branches);
147: uprintf("après free %p\n", s_arbre->branches);
148: free(s_arbre);
149:
150: // Chaînage des arguments
151:
152: while(l_pile_locale != NULL)
153: {
154: l_element_courant = (void *) (*l_pile_locale).donnee;
155:
156: if (l_element_courant == NULL)
157: {
158: (*s_etat_processus).erreur_systeme = d_es_pile_vide;
159: return(NULL);
160: }
161:
162: while((*l_element_courant).suivant != NULL)
163: {
164: l_element_courant = (*l_element_courant).suivant;
165: }
166:
167: (*l_element_courant).suivant = l_liste;
168: l_liste = (void *) (*l_pile_locale).donnee;
169:
170: l_nouvelle_pile_locale = (*l_pile_locale).suivant;
171: liberation_maillon(s_etat_processus, l_pile_locale);
172: l_pile_locale = l_nouvelle_pile_locale;
173: }
174:
175: return(l_liste);
176: }
177:
178:
179: /*
180: ================================================================================
181: Fonction de simplification d'un arbre
182: ================================================================================
183: Entrées : pointeur sur une structure struct_processus
184: --------------------------------------------------------------------------------
185: Sorties :
186: --------------------------------------------------------------------------------
187: Effets de bord : néant
188: ================================================================================
189: */
190:
191: static int
192: ordonnancement_branches(const void *a1, const void *a2)
193: {
194: struct_arbre **_a1;
195: struct_arbre **_a2;
196:
197: _a1 = (struct_arbre **) a1;
198: _a2 = (struct_arbre **) a2;
199:
200: if (((**_a1).feuille != NULL) && ((**_a2).feuille != NULL))
201: {
202: // Si les types sont identiques, on ne change rien.
203:
204: if ((*(*(**_a1).feuille).donnee).type ==
205: (*(*(**_a2).feuille).donnee).type)
206: {
207: return(0);
208: }
209:
210: // On rejette les nombres à la fin.
211:
212: if (((*(*(**_a1).feuille).donnee).type == INT) ||
213: ((*(*(**_a1).feuille).donnee).type == REL) ||
214: ((*(*(**_a1).feuille).donnee).type == CPL))
215: {
216: return(1);
217: }
218: else
219: {
220: return(-1);
221: }
222: }
223:
224: return(0);
225: }
226:
227:
228: static void
229: simplification_arbre(struct_processus *s_etat_processus,
230: struct_arbre *s_arbre)
231: {
232: integer8 i;
233: integer8 j;
234: integer8 nouveaux_elements;
235:
236: struct_arbre *s_branche;
237:
238: struct_liste_chainee *l_element_courant;
239: struct_liste_chainee *l_element_suivant;
240:
241: struct_objet *s_objet;
242:
243: if ((*(*(*s_arbre).feuille).donnee).type != FCT)
244: {
245: // L'objet formant le noeud n'est pas une fonction. Il n'y a aucune
246: // simplification possible.
247:
248: return;
249: }
250:
251: // Transformation des soustractions que l'on remplace par
252: // une addition de l'opposé. Si l'on a une soustraction,
253: // on greffe donc une instruction NEG dans l'arbre.
254: // Note : à cet instant, l'instruction '-' ne peut avoir que deux
255: // opérandes.
256:
257: if (strcmp((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
258: .nom_fonction, "-") == 0)
259: {
260: if ((*s_arbre).nombre_branches != 2)
261: {
262: (*s_etat_processus).erreur_execution = d_ex_simplification;
263: return;
264: }
265:
266: liberation(s_etat_processus, (*((*s_arbre).feuille)).donnee);
267:
268: if (((*((*s_arbre).feuille)).donnee = allocation(s_etat_processus,
269: FCT)) == NULL)
270: {
271: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
272: return;
273: }
274:
275: if (((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
276: .nom_fonction = malloc(2 * sizeof(unsigned char))) == NULL)
277: {
278: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
279: return;
280: }
281:
282: strcpy((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
283: .nom_fonction, "+");
284: (*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
285: .nombre_arguments = 1;
286:
287: if ((s_branche = malloc(sizeof(struct_arbre))) == NULL)
288: {
289: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
290: return;
291: }
292:
293: if (((*s_branche).branches = malloc(sizeof(struct_arbre *))) == NULL)
294: {
295: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
296: return;
297: }
298:
299: if (((*s_branche).feuille = allocation_maillon(s_etat_processus))
300: == NULL)
301: {
302: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
303: return;
304: }
305:
306: (*(*s_branche).feuille).suivant = NULL;
307:
308: if (((*(*s_branche).feuille).donnee = allocation(s_etat_processus, FCT))
309: == NULL)
310: {
311: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
312: return;
313: }
314:
315: if (((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
316: .nom_fonction = malloc(4 * sizeof(unsigned char))) == NULL)
317: {
318: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
319: return;
320: }
321:
322: strcpy((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
323: .nom_fonction, "NEG");
324: (*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
325: .nombre_arguments = 1;
326: (*s_branche).branches[0] = (*s_arbre).branches[1];
327: (*s_branche).nombre_branches = 1;
328: (*s_arbre).branches[1] = s_branche;
329: }
330:
331: // La feuille est une fonction, on peut envisager la simplification
332: // de l'arbre. Pour cela, on descend d'un niveau pour greffer
333: // de nouvelles branches.
334:
335: if (strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee).objet))
336: .nom_fonction, "+") == 0)
337: {
338: for(i = 0; i < (*s_arbre).nombre_branches; i++)
339: {
340: s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
341:
342: if ((*s_objet).type == FCT)
343: {
344: if (strcmp((*((struct_fonction *) (*s_objet).objet))
345: .nom_fonction, "-") == 0)
346: {
347: simplification_arbre(s_etat_processus,
348: (*s_arbre).branches[i]);
349: s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
350: }
351:
352: if (strcmp((*((struct_fonction *) (*s_objet).objet))
353: .nom_fonction, "+") == 0)
354: {
355: simplification_arbre(s_etat_processus,
356: (*s_arbre).branches[i]);
357:
358: /*
359: On greffe.
360: +
361: +
362: 2
363: SIN
364: 3
365: 10
366:
367: doit donner :
368: +
369: 2
370: SIN
371: 3
372: 10
373: */
374:
375: nouveaux_elements = (*(*s_arbre).branches[i])
376: .nombre_branches;
377:
378: if (((*s_arbre).branches = realloc((*s_arbre).branches,
379: ((unsigned) ((*s_arbre).nombre_branches
380: + nouveaux_elements))
381: * sizeof(struct_arbre *))) == NULL)
382: {
383: (*s_etat_processus).erreur_systeme =
384: d_es_allocation_memoire;
385: return;
386: }
387:
388: for(j = 0; j < nouveaux_elements; j++)
389: {
390: (*s_arbre).branches[(*s_arbre).nombre_branches++] =
391: (*(*s_arbre).branches[i]).branches[j];
392: }
393:
394: l_element_courant = (*s_arbre).feuille;
395: (*s_arbre).feuille = (*(*s_arbre).branches[i]).feuille;
396:
397: l_element_suivant = (*s_arbre).feuille;
398: while((*l_element_suivant).suivant != NULL)
399: {
400: l_element_suivant = (*l_element_suivant).suivant;
401: }
402:
403: (*l_element_suivant).suivant = l_element_courant;
404: free((*(*s_arbre).branches[i]).branches);
405: free((*s_arbre).branches[i]);
406:
407: // Retrait de la branche
408:
409: for(j = i + 1; j < (*s_arbre).nombre_branches; j++)
410: {
411: (*s_arbre).branches[j - 1] = (*s_arbre).branches[j];
412: }
413:
414: (*s_arbre).nombre_branches--;
415:
416: // Réorganisation des valeurs numériques en queue.
417:
418: qsort((*s_arbre).branches, (size_t) (*s_arbre)
419: .nombre_branches, sizeof(struct_arbre *),
420: ordonnancement_branches);
421: }
422: }
423: }
424:
425: if (((*s_arbre).branches = realloc((*s_arbre).branches,
426: ((unsigned) (*s_arbre).nombre_branches)
427: * sizeof(struct_arbre *))) == NULL)
428: {
429: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
430: return;
431: }
432: }
433:
434: return;
435: }
436:
437:
438: /*
439: ================================================================================
440: Fonction 'simplification' (ne libère pas les paramètres)
441: ================================================================================
442: Entrées : pointeur sur une structure struct_processus
443: --------------------------------------------------------------------------------
444: Sorties :
445: --------------------------------------------------------------------------------
446: Effets de bord : néant
447: ================================================================================
448: */
449:
450: struct_objet *
451: simplification(struct_processus *s_etat_processus, struct_objet *s_objet)
452: {
453: struct_objet *s_objet_simplifie;
454:
455: integer8 i;
456: integer8 nombre_arguments;
457:
458: struct_arbre *s_arbre;
459:
460: struct_liste_chainee *l_element_courant;
461:
462: // Attention : l_liste_locale et l_ancienne_liste_locale ne contiennent pas
463: // un pointeur sur une struct_objet, mais sur une struct_arbre.
464:
465: struct_liste_chainee *l_liste_locale;
466: struct_liste_chainee *l_ancienne_liste_locale;
467:
468: if ((*s_objet).type == ALG)
469: {
470: /*
471: * Transcription de l'expression algébrique en arbre q-aire
472: */
473:
474: l_liste_locale = NULL;
475: l_element_courant = (*s_objet).objet;
476:
477: while(l_element_courant != NULL)
478: {
479: switch((*(*l_element_courant).donnee).type)
480: {
481: // Toutes les fonctions (intrinsèques, extrinsèques et
482: // utilisateurs).
483:
484: case FCT:
485: {
486: // Il s'agit d'un objet de type ALG. Nous pouvons donc
487: // sauter les délimiteurs d'expression.
488:
489: if ((l_element_courant != (*s_objet).objet) &&
490: ((*l_element_courant).suivant != NULL))
491: {
492: nombre_arguments = (*((struct_fonction *)
493: (*(*l_element_courant).donnee).objet))
494: .nombre_arguments;
495:
496: // Si le nombre d'arguments vaut 0, la fonction
497: // apparaît en notation algébrique comme une fonction
498: // infixe.
499:
500: if (nombre_arguments == 0)
501: {
502: nombre_arguments = 2;
503: }
504:
505: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
506: {
507: (*s_etat_processus).erreur_systeme =
508: d_es_allocation_memoire;
509: return(NULL);
510: }
511:
512: (*s_arbre).nombre_branches = nombre_arguments;
513:
514: if (((*s_arbre).feuille = allocation_maillon(
515: s_etat_processus)) == NULL)
516: {
517: (*s_etat_processus).erreur_systeme =
518: d_es_allocation_memoire;
519: return(NULL);
520: }
521:
522: (*(*s_arbre).feuille).donnee = copie_objet(
523: s_etat_processus, (*l_element_courant).donnee,
524: 'P');
525: (*(*s_arbre).feuille).suivant = NULL;
526:
527: if (((*s_arbre).branches = malloc(((size_t) (*s_arbre)
528: .nombre_branches) * sizeof(struct_arbre *)))
529: == NULL)
530: {
531: (*s_etat_processus).erreur_systeme =
532: d_es_allocation_memoire;
533: return(NULL);
534: }
535:
536: for(i = nombre_arguments - 1; i >= 0; i--)
537: {
538: if (l_liste_locale == NULL)
539: {
540: (*s_etat_processus).erreur_execution =
541: d_ex_manque_argument;
542: return(NULL);
543: }
544:
545: (*s_arbre).branches[i] = (struct_arbre *)
546: (*l_liste_locale).donnee;
547:
548: l_ancienne_liste_locale = l_liste_locale;
549: l_liste_locale = (*l_liste_locale).suivant;
550:
551: liberation_maillon(s_etat_processus,
552: l_ancienne_liste_locale);
553: }
554:
555: // Introduction de l'arbre dans la pile locale
556:
557: l_ancienne_liste_locale = l_liste_locale;
558:
559: if ((l_liste_locale = allocation_maillon(
560: s_etat_processus)) == NULL)
561: {
562: (*s_etat_processus).erreur_systeme =
563: d_es_allocation_memoire;
564: return(NULL);
565: }
566:
567: (*l_liste_locale).suivant = l_ancienne_liste_locale;
568: (*l_liste_locale).donnee = (void *) s_arbre;
569: }
570:
571: break;
572: }
573:
574: default:
575: {
576: l_ancienne_liste_locale = l_liste_locale;
577:
578: if ((l_liste_locale = allocation_maillon(s_etat_processus))
579: == NULL)
580: {
581: (*s_etat_processus).erreur_systeme =
582: d_es_allocation_memoire;
583: return(NULL);
584: }
585:
586: (*l_liste_locale).suivant = l_ancienne_liste_locale;
587:
588: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
589: {
590: (*s_etat_processus).erreur_systeme =
591: d_es_allocation_memoire;
592: return(NULL);
593: }
594:
595: if (((*s_arbre).feuille = allocation_maillon(
596: s_etat_processus)) == NULL)
597: {
598: (*s_etat_processus).erreur_systeme =
599: d_es_allocation_memoire;
600: return(NULL);
601: }
602:
603: (*(*s_arbre).feuille).donnee = copie_objet(
604: s_etat_processus, (*l_element_courant).donnee, 'P');
605: (*(*s_arbre).feuille).suivant = NULL;
606: (*s_arbre).nombre_branches = 0;
607: (*s_arbre).branches = NULL;
608:
609: (*l_liste_locale).donnee = (void *) s_arbre;
610: break;
611: }
612: }
613:
614: l_element_courant = (*l_element_courant).suivant;
615: }
616:
617: // Toute l'expression a été balayée. On ne doit plus avoir qu'un
618: // seul niveau dans la pile locale, ce niveau contenant l'arbre
619: // à réduire.
620:
621: if (l_liste_locale == NULL)
622: {
623: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
624: return(NULL);
625: }
626: else if ((*l_liste_locale).suivant != NULL)
627: {
628: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
629: return(NULL);
630: }
631:
632: s_arbre = (void *) (*l_liste_locale).donnee;
633:
634: liberation_maillon(s_etat_processus, l_liste_locale);
635: l_liste_locale = NULL;
636:
637: /*
638: * Simplification de l'arbre
639: */
640:
641: affichage_arbre(s_etat_processus, s_arbre, 0);
642: simplification_arbre(s_etat_processus, s_arbre);
643: affichage_arbre(s_etat_processus, s_arbre, 0);
644:
645: if ((*s_etat_processus).erreur_systeme != d_es)
646: {
647: return(NULL);
648: }
649:
650: /*
651: * Transcription de l'arbre q-aire simplifié en expression algébrique.
652: * Seule une fonction récursive permet de faire cette conversion
653: * simplement.
654: */
655:
656: l_liste_locale = transcription_arbre(s_etat_processus, s_arbre);
657:
658: if ((s_objet_simplifie = allocation(s_etat_processus, ALG))
659: == NULL)
660: {
661: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
662: return(NULL);
663: }
664:
665: // Ajout des délimiteurs '<<' et '>>' à la liste d'instructions
666:
667: if (((*s_objet_simplifie).objet = allocation_maillon(s_etat_processus))
668: == NULL)
669: {
670: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
671: return(NULL);
672: }
673:
674: l_element_courant = (*s_objet_simplifie).objet;
675:
676: if (((*l_element_courant).donnee = allocation(s_etat_processus,
677: FCT)) == NULL)
678: {
679: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
680: return(NULL);
681: }
682:
683: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
684: .nombre_arguments = 0;
685: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
686: .fonction = instruction_vers_niveau_superieur;
687:
688: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
689: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
690: {
691: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
692: return(NULL);
693: }
694:
695: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
696: .nom_fonction, "<<");
697:
698: (*l_element_courant).suivant = l_liste_locale;
699:
700: while((*l_element_courant).suivant != NULL)
701: {
702: l_element_courant = (*l_element_courant).suivant;
703: }
704:
705: if (((*l_element_courant).suivant =
706: allocation_maillon(s_etat_processus)) == NULL)
707: {
708: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
709: return(NULL);
710: }
711:
712: l_element_courant = (*l_element_courant).suivant;
713: (*l_element_courant).suivant = NULL;
714:
715: if (((*l_element_courant).donnee = allocation(s_etat_processus,
716: FCT)) == NULL)
717: {
718: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
719: return(NULL);
720: }
721:
722: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
723: .nombre_arguments = 0;
724: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
725: .fonction = instruction_vers_niveau_inferieur;
726:
727: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
728: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
729: {
730: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
731: return(NULL);
732: }
733:
734: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
735: .nom_fonction, ">>");
736: }
737: else
738: {
739: s_objet_simplifie = copie_objet(s_etat_processus, s_objet, 'P');
740: }
741:
742: return(s_objet_simplifie);
743: }
744:
745: // vim: ts=4
CVSweb interface <joel.bertrand@systella.fr>
![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to simplification.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [local] / rpl / src