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