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