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: {
235: return(1);
236: }
237: else
238: {
239: return(-1);
240: }
241: }
242:
243: return(0);
244: }
245:
246:
247: static void
248: simplification_arbre(struct_processus *s_etat_processus,
249: struct_arbre *s_arbre)
250: {
251: integer8 i;
252: integer8 j;
253: integer8 nouveaux_elements;
254:
255: struct_arbre *s_branche;
256:
257: struct_objet *s_objet;
258:
259: if ((*(*(*s_arbre).feuille).donnee).type != FCT)
260: {
261: // L'objet formant le noeud n'est pas une fonction. Il n'y a aucune
262: // simplification possible.
263:
264: return;
265: }
266:
267: // Transformation des soustractions que l'on remplace par
268: // une addition de l'opposé. Si l'on a une soustraction,
269: // on greffe donc une instruction NEG dans l'arbre.
270: // Note : à cet instant, l'instruction '-' ne peut avoir que deux
271: // opérandes.
272:
273: if (strcmp((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
274: .nom_fonction, "-") == 0)
275: {
276: if ((*s_arbre).nombre_branches != 2)
277: {
278: (*s_etat_processus).erreur_execution = d_ex_simplification;
279: return;
280: }
281:
282: liberation(s_etat_processus, (*((*s_arbre).feuille)).donnee);
283:
284: if (((*((*s_arbre).feuille)).donnee = allocation(s_etat_processus,
285: FCT)) == NULL)
286: {
287: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
288: return;
289: }
290:
291: if (((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
292: .nom_fonction = malloc(2 * sizeof(unsigned char))) == NULL)
293: {
294: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
295: return;
296: }
297:
298: strcpy((*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
299: .nom_fonction, "+");
300: (*((struct_fonction *) (*(*((*s_arbre).feuille)).donnee).objet))
301: .nombre_arguments = 1;
302:
303: if ((s_branche = malloc(sizeof(struct_arbre))) == NULL)
304: {
305: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
306: return;
307: }
308:
309: if (((*s_branche).branches = malloc(sizeof(struct_arbre *))) == NULL)
310: {
311: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
312: return;
313: }
314:
315: if (((*s_branche).feuille = allocation_maillon(s_etat_processus))
316: == NULL)
317: {
318: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
319: return;
320: }
321:
322: (*(*s_branche).feuille).suivant = NULL;
323:
324: if (((*(*s_branche).feuille).donnee = allocation(s_etat_processus, FCT))
325: == NULL)
326: {
327: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
328: return;
329: }
330:
331: if (((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
332: .nom_fonction = malloc(4 * sizeof(unsigned char))) == NULL)
333: {
334: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
335: return;
336: }
337:
338: strcpy((*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
339: .nom_fonction, "NEG");
340: (*((struct_fonction *) (*(*(*s_branche).feuille).donnee).objet))
341: .nombre_arguments = 1;
342: (*s_branche).branches[0] = (*s_arbre).branches[1];
343: (*s_branche).nombre_branches = 1;
344: (*s_arbre).branches[1] = s_branche;
345: }
346:
347: // La feuille est une fonction, on peut envisager la simplification
348: // de l'arbre. Pour cela, on descend d'un niveau pour greffer
349: // de nouvelles branches.
350:
351: if (strcmp((*((struct_fonction *) (*(*(*s_arbre).feuille).donnee).objet))
352: .nom_fonction, "+") == 0)
353: {
354: for(i = 0; i < (*s_arbre).nombre_branches; i++)
355: {
356: s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
357:
358: if ((*s_objet).type == FCT)
359: {
360: if (strcmp((*((struct_fonction *) (*s_objet).objet))
361: .nom_fonction, "-") == 0)
362: {
363: simplification_arbre(s_etat_processus,
364: (*s_arbre).branches[i]);
365: s_objet = (*((*((*s_arbre).branches[i])).feuille)).donnee;
366: }
367:
368: if (strcmp((*((struct_fonction *) (*s_objet).objet))
369: .nom_fonction, "+") == 0)
370: {
371: simplification_arbre(s_etat_processus,
372: (*s_arbre).branches[i]);
373:
374: /*
375: On greffe.
376: +
377: +
378: 2
379: SIN
380: 3
381: 10
382:
383: doit donner :
384: +
385: 2
386: SIN
387: 3
388: 10
389: */
390:
391: nouveaux_elements = (*(*s_arbre).branches[i])
392: .nombre_branches;
393:
394: if (((*s_arbre).branches = realloc((*s_arbre).branches,
395: ((unsigned) ((*s_arbre).nombre_branches
396: + nouveaux_elements))
397: * sizeof(struct_arbre *))) == NULL)
398: {
399: (*s_etat_processus).erreur_systeme =
400: d_es_allocation_memoire;
401: return;
402: }
403:
404: for(j = 0; j < nouveaux_elements; j++)
405: {
406: (*s_arbre).branches[(*s_arbre).nombre_branches++] =
407: (*(*s_arbre).branches[i]).branches[j];
408: }
409:
410: free((*s_arbre).branches[i]);
411:
412: // Retrait de la branche
413:
414: for(j = i + 1; j < (*s_arbre).nombre_branches; j++)
415: {
416: (*s_arbre).branches[j - 1] = (*s_arbre).branches[j];
417: }
418:
419: (*s_arbre).nombre_branches--;
420:
421: // Réorganisation des valeurs numériques en queue.
422:
423: qsort((*s_arbre).branches, (size_t) (*s_arbre)
424: .nombre_branches, sizeof(struct_arbre *),
425: ordonnancement_branches);
426: }
427: }
428: }
429:
430: if (((*s_arbre).branches = realloc((*s_arbre).branches,
431: ((unsigned) (*s_arbre).nombre_branches)
432: * sizeof(struct_arbre *))) == NULL)
433: {
434: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
435: return;
436: }
437: }
438:
439: return;
440: }
441:
442:
443: /*
444: ================================================================================
445: Fonction 'simplification' (ne libère pas les paramètres)
446: ================================================================================
447: Entrées : pointeur sur une structure struct_processus
448: --------------------------------------------------------------------------------
449: Sorties :
450: --------------------------------------------------------------------------------
451: Effets de bord : néant
452: ================================================================================
453: */
454:
455: struct_objet *
456: simplification(struct_processus *s_etat_processus, struct_objet *s_objet)
457: {
458: struct_objet *s_objet_simplifie;
459:
460: integer8 i;
461: integer8 nombre_arguments;
462:
463: struct_arbre *s_arbre;
464:
465: struct_liste_chainee *l_element_courant;
466:
467: // Attention : l_liste_locale et l_ancienne_liste_locale ne contiennent pas
468: // un pointeur sur une struct_objet, mais sur une struct_arbre.
469:
470: struct_liste_chainee *l_liste_locale;
471: struct_liste_chainee *l_ancienne_liste_locale;
472:
473: if ((*s_objet).type == ALG)
474: {
475: /*
476: * Transcription de l'expression algébrique en arbre q-aire
477: */
478:
479: l_liste_locale = NULL;
480: l_element_courant = (*s_objet).objet;
481:
482: while(l_element_courant != NULL)
483: {
484: switch((*(*l_element_courant).donnee).type)
485: {
486: // Toutes les fonctions (intrinsèques, extrinsèques et
487: // utilisateurs).
488:
489: case FCT:
490: {
491: // Il s'agit d'un objet de type ALG. Nous pouvons donc
492: // sauter les délimiteurs d'expression.
493:
494: if ((l_element_courant != (*s_objet).objet) &&
495: ((*l_element_courant).suivant != NULL))
496: {
497: nombre_arguments = (*((struct_fonction *)
498: (*(*l_element_courant).donnee).objet))
499: .nombre_arguments;
500:
501: // Si le nombre d'arguments vaut 0, la fonction
502: // apparaît en notation algébrique comme une fonction
503: // infixe.
504:
505: if (nombre_arguments == 0)
506: {
507: nombre_arguments = 2;
508: }
509:
510: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
511: {
512: (*s_etat_processus).erreur_systeme =
513: d_es_allocation_memoire;
514: return(NULL);
515: }
516:
517: (*s_arbre).nombre_branches = nombre_arguments;
518:
519: if (((*s_arbre).feuille = allocation_maillon(
520: s_etat_processus)) == NULL)
521: {
522: (*s_etat_processus).erreur_systeme =
523: d_es_allocation_memoire;
524: return(NULL);
525: }
526:
527: (*(*s_arbre).feuille).donnee = copie_objet(
528: s_etat_processus, (*l_element_courant).donnee,
529: 'P');
530: (*(*s_arbre).feuille).suivant = NULL;
531:
532: if (((*s_arbre).branches = malloc(((size_t) (*s_arbre)
533: .nombre_branches) * sizeof(struct_arbre *)))
534: == NULL)
535: {
536: (*s_etat_processus).erreur_systeme =
537: d_es_allocation_memoire;
538: return(NULL);
539: }
540:
541: for(i = nombre_arguments - 1; i >= 0; i--)
542: {
543: if (l_liste_locale == NULL)
544: {
545: (*s_etat_processus).erreur_execution =
546: d_ex_manque_argument;
547: return(NULL);
548: }
549:
550: (*s_arbre).branches[i] = (struct_arbre *)
551: (*l_liste_locale).donnee;
552:
553: l_ancienne_liste_locale = l_liste_locale;
554: l_liste_locale = (*l_liste_locale).suivant;
555:
556: liberation_maillon(s_etat_processus,
557: l_ancienne_liste_locale);
558: }
559:
560: // Introduction de l'arbre dans la pile locale
561:
562: l_ancienne_liste_locale = l_liste_locale;
563:
564: if ((l_liste_locale = allocation_maillon(
565: s_etat_processus)) == NULL)
566: {
567: (*s_etat_processus).erreur_systeme =
568: d_es_allocation_memoire;
569: return(NULL);
570: }
571:
572: (*l_liste_locale).suivant = l_ancienne_liste_locale;
573: (*l_liste_locale).donnee = (void *) s_arbre;
574: }
575:
576: break;
577: }
578:
579: default:
580: {
581: l_ancienne_liste_locale = l_liste_locale;
582:
583: if ((l_liste_locale = allocation_maillon(s_etat_processus))
584: == NULL)
585: {
586: (*s_etat_processus).erreur_systeme =
587: d_es_allocation_memoire;
588: return(NULL);
589: }
590:
591: (*l_liste_locale).suivant = l_ancienne_liste_locale;
592:
593: if ((s_arbre = malloc(sizeof(struct_arbre))) == NULL)
594: {
595: (*s_etat_processus).erreur_systeme =
596: d_es_allocation_memoire;
597: return(NULL);
598: }
599:
600: if (((*s_arbre).feuille = allocation_maillon(
601: s_etat_processus)) == NULL)
602: {
603: (*s_etat_processus).erreur_systeme =
604: d_es_allocation_memoire;
605: return(NULL);
606: }
607:
608: (*(*s_arbre).feuille).donnee = copie_objet(
609: s_etat_processus, (*l_element_courant).donnee, 'P');
610: (*(*s_arbre).feuille).suivant = NULL;
611: (*s_arbre).nombre_branches = 0;
612: (*s_arbre).branches = NULL;
613:
614: (*l_liste_locale).donnee = (void *) s_arbre;
615: break;
616: }
617: }
618:
619: l_element_courant = (*l_element_courant).suivant;
620: }
621:
622: // Toute l'expression a été balayée. On ne doit plus avoir qu'un
623: // seul niveau dans la pile locale, ce niveau contenant l'arbre
624: // à réduire.
625:
626: if (l_liste_locale == NULL)
627: {
628: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
629: return(NULL);
630: }
631: else if ((*l_liste_locale).suivant != NULL)
632: {
633: (*s_etat_processus).erreur_execution = d_ex_erreur_evaluation;
634: return(NULL);
635: }
636:
637: s_arbre = (void *) (*l_liste_locale).donnee;
638:
639: liberation_maillon(s_etat_processus, l_liste_locale);
640: l_liste_locale = NULL;
641:
642: /*
643: * Simplification de l'arbre
644: */
645:
646: affichage_arbre(s_etat_processus, s_arbre, 0);
647: simplification_arbre(s_etat_processus, s_arbre);
648: affichage_arbre(s_etat_processus, s_arbre, 0);
649:
650: if ((*s_etat_processus).erreur_systeme != d_es)
651: {
652: return(NULL);
653: }
654:
655: /*
656: * Transcription de l'arbre q-aire simplifié en expression algébrique.
657: * Seule une fonction récursive permet de faire cette conversion
658: * simplement.
659: */
660:
661: l_liste_locale = transcription_arbre(s_etat_processus, s_arbre);
662:
663: if ((s_objet_simplifie = allocation(s_etat_processus, ALG))
664: == NULL)
665: {
666: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
667: return(NULL);
668: }
669:
670: // Ajout des délimiteurs '<<' et '>>' à la liste d'instructions
671:
672: if (((*s_objet_simplifie).objet = allocation_maillon(s_etat_processus))
673: == NULL)
674: {
675: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
676: return(NULL);
677: }
678:
679: l_element_courant = (*s_objet_simplifie).objet;
680:
681: if (((*l_element_courant).donnee = allocation(s_etat_processus,
682: FCT)) == NULL)
683: {
684: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
685: return(NULL);
686: }
687:
688: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
689: .nombre_arguments = 0;
690: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
691: .fonction = instruction_vers_niveau_superieur;
692:
693: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
694: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
695: {
696: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
697: return(NULL);
698: }
699:
700: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
701: .nom_fonction, "<<");
702:
703: (*l_element_courant).suivant = l_liste_locale;
704:
705: while((*l_element_courant).suivant != NULL)
706: {
707: l_element_courant = (*l_element_courant).suivant;
708: }
709:
710: if (((*l_element_courant).suivant =
711: allocation_maillon(s_etat_processus)) == NULL)
712: {
713: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
714: return(NULL);
715: }
716:
717: l_element_courant = (*l_element_courant).suivant;
718: (*l_element_courant).suivant = NULL;
719:
720: if (((*l_element_courant).donnee = allocation(s_etat_processus,
721: FCT)) == NULL)
722: {
723: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
724: return(NULL);
725: }
726:
727: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
728: .nombre_arguments = 0;
729: (*((struct_fonction *) (*(*l_element_courant).donnee).objet))
730: .fonction = instruction_vers_niveau_inferieur;
731:
732: if (((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
733: .nom_fonction = malloc(3 * sizeof(unsigned char))) == NULL)
734: {
735: (*s_etat_processus).erreur_systeme = d_es_allocation_memoire;
736: return(NULL);
737: }
738:
739: strcpy((*((struct_fonction *) (*(*l_element_courant).donnee).objet))
740: .nom_fonction, ">>");
741: }
742: else
743: {
744: s_objet_simplifie = copie_objet(s_etat_processus, s_objet, 'P');
745: }
746:
747: return(s_objet_simplifie);
748: }
749:
750: // 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