-
Notifications
You must be signed in to change notification settings - Fork 2
/
Po_create_poly.cpp
447 lines (390 loc) · 17 KB
/
Po_create_poly.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
/*******************************************************************/
/*** FILE : Po_create_poly.c ***/
/*** AUTHOR: Sekhar Muddana ***/
/*** PUBLIC ROUTINES: ***/
/*** struct polynomial *Create_poly() ***/
/*** PRIVATE ROUTINES: ***/
/*** void Print_tree() ***/
/*** void Print_opr_prod_tree() ***/
/*** void Print_art_word() ***/
/*** void Create_exp_str() ***/
/*** int Found_minus() ***/
/*** void Free_tnode_tree() ***/
/*** MODULE DESCRIPTION: ***/
/*** This module contains routines needed to create a ***/
/*** polynomial,from the input string entered by user. ***/
/*******************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <setjmp.h>
#include "Po_create_poly.h"
#include "Po_create_poly_pri.h"
#include "Po_expand_poly.h"
#include "Memory_routines.h"
#include "Po_parse_poly.h"
#include "Po_semantics.h"
#include "Po_prod_bst.h"
#include "Po_parse_exptext.h"
#include "Strings.h"
static void Print_tree(struct unexp_tnode *Pntr);
static void Print_opr_prod_tree(struct unexp_tnode *Pntr);
static void Print_art_word(struct unexp_tnode *Pntr);
static void Create_exp_str(struct unexp_tnode *Pntr, char **Str_ptr, int *Maxsize_str_ptr);
static int Found_minus(struct unexp_tnode *Pntr);
static void Free_tnode_tree(struct unexp_tnode *Pntr);
extern jmp_buf env;
/*******************************************************************/
/* Called from Main() in driver.c. */
/* MODIFIES: None. */
/* REQUIRES: */
/* In_str -- polynomial string, operand portion of the */
/* commands "i [polynomial]" and "q [polynomial]". */
/* RETURNS: */
/* Pointer to the created polynomial if In_str is successfully */
/* parsed. */
/* NULL otherwise. */
/* FUNCTION: */
/* Creates the structure polynomial through a series of calls */
/* to routines in files Po_parse_poly.c, Po_expand_poly.c and */
/* Po_parse_exptext.c */
/* First call Create_parse_tree() with In_str to get the parse */
/* tree corresponding to In_str. */
/* Then expand the parse tree by calling Expand_parse_tree(). */
/* Then get the simplified parse tree having basic operators */
/* like JUXT_PROD, SCALAR_MULT along with small letters and */
/* scalars at the leaves by calling Simplify_parse_tree(), */
/* in a loop until no further simplification is possible. */
/* The Simplified tree is translated into a string by */
/* calling Create_exp_str() which traverses the tree in */
/* inorder. */
/* Finally the expanded string is parsed by calling */
/* Parse_exptext(), which returns a pointer to the polynomial */
/* which in turn returned to the caller of Create_poly(). */
/* NOTE: */
/* The intermediate trees created during the creation of */
/* polynomial can be seen by switching on the DEBUG_EXP flag. */
/*******************************************************************/
struct polynomial *Create_poly(char In_str[], int *In_str_len, int *Out_of_memory)
{
/*static struct unexp_tnode *temp;*/
struct unexp_tnode *Unexp_tree1;
struct unexp_tnode *Unexp_tree2;
struct unexp_tnode *Exp_tree1;
struct unexp_tnode *Exp_tree2;
struct unexp_tnode *Exp_tree3;
struct unexp_tnode *Exp_tree4;
struct polynomial *poly;
char *exp_poly_str;
static char **Exp_poly_str_ptr; /* Exp_poly_str may be expanded! */
static int Maxsize_exp_poly_str;
int Modified = FALSE; /* Has tree been changed in this call? */
#if DEBUG_EXP
int count; /* Debugging information. No of calls to Simplify */
#endif
/*int i;*/
int first_time = TRUE;
/* Allocate space for exp_poly_str first_time */
if (first_time) {
exp_poly_str = (char*) Mymalloc(EXP_STR_LEN);
Maxsize_exp_poly_str = EXP_STR_LEN;
first_time = FALSE;
}
exp_poly_str[0] = '\0';
Exp_poly_str_ptr = &exp_poly_str;
Unexp_tree1 = NULL;
Unexp_tree2 = NULL;
Exp_tree1 = NULL;
Exp_tree2 = NULL;
Exp_tree3 = NULL;
Exp_tree4 = NULL;
if (setjmp(env) != 0) {
Free_tnode_tree(Unexp_tree1);
Free_tnode_tree(Unexp_tree2);
Free_tnode_tree(Exp_tree1);
Free_tnode_tree(Exp_tree2);
Free_tnode_tree(Exp_tree3);
Free_tnode_tree(Exp_tree4);
*Out_of_memory = TRUE;
printf("Command unsuccessfull.\n");
return(NULL);
}
/* Parse tree for the polynomial string In_str entered by user */
Unexp_tree1 = Create_parse_tree(In_str);
if (Unexp_tree1 == NULL)
return(NULL);
#if DEBUG_EXP
Print_tree(Unexp_tree1);
printf("\n");
#endif
/* Expand the Parse tree by using formulae for operators */
Unexp_tree2 = Expand_parse_tree(Unexp_tree1);
#if DEBUG_EXP
Print_tree(Unexp_tree2);
printf("\n");
#endif
/* Simplify the Expanded tree i.e apply distributive laws. */
Exp_tree1 = Simplify_parse_tree(Unexp_tree2,&Modified);
#if DEBUG_EXP
count = 1;
printf("simplified tree %d\n",count);
Print_tree(Exp_tree1);
printf("\n");
#endif
while (Modified) {
Modified = FALSE;
Exp_tree2 = Simplify_parse_tree(Exp_tree1,&Modified);
#if DEBUG_EXP
count++;
printf("count = %d Modified = %d\n",count,Modified);
printf("simplified tree\n");
Print_tree(Exp_tree2);
printf("\n");
printf("freeing Exp_tree1\n");
#endif
Free_tnode_tree(Exp_tree1);
Exp_tree1 = Exp_tree2;
Exp_tree2 = NULL;
}
/* No more simplifications needed! */
Modified = FALSE;
/* Get rid of Unary minus by multiplying that subtree by -1. */
Exp_tree3 = Elim_subtraction(Exp_tree1,&Modified);
#if DEBUG_EXP
count = 1;
Print_tree(Exp_tree3);
printf("\n");
#endif
while (Modified) {
Modified = FALSE;
Exp_tree4 = Elim_subtraction(Exp_tree3,&Modified);
#if DEBUG_EXP
count++;
printf("count = %d Modified = %d\n",count,Modified);
Print_tree(Exp_tree4);
printf("\n");
printf("freeing Exp_tree3\n");
#endif
Free_tnode_tree(Exp_tree3);
Exp_tree3 = Exp_tree4;
Exp_tree4 = NULL;
}
/* Traverse the tree in inorder and write it as a string */
Create_exp_str(Exp_tree3,Exp_poly_str_ptr,&Maxsize_exp_poly_str);
Free_tnode_tree(Unexp_tree1);
Free_tnode_tree(Unexp_tree2);
Free_tnode_tree(Exp_tree1);
Free_tnode_tree(Exp_tree3);
#if DEBUG_EXP
printf("%s",exp_poly_str);
printf("\n");
#endif
/* Parse the string to create the polynomial. */
poly = Parse_exptext(*Exp_poly_str_ptr);
*In_str_len = strlen(exp_poly_str);
free(exp_poly_str);
return(poly);
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* Pntr -- root of the tree of tnodes */
/* RETURNS: None. */
/* FUNCTION: */
/* Print the tree in preorder. */
/* NOTE: */
/* Called only when DEBUG_EXP flag is on. */
/* Very useful to see how the parse tree gets simplified. */
/*******************************************************************/
void Print_tree(struct unexp_tnode *Pntr)
{
if (Pntr != NULL) {
if ((Pntr->op != SMALL_LETTER) && (Pntr->op != SCALAR) &&
(Pntr->op != OPERATOR_PROD) && (Pntr->op != ARTIFICIAL_WORD)) {
printf("%c(",OPR_SYMBOL[Pntr->op]);
Print_tree(Pntr->operand1);
if (Pntr->operand2 != NULL) {
printf(",");
Print_tree(Pntr->operand2);
if (Pntr->operand3 != NULL) {
printf(",");
Print_tree(Pntr->operand3);
}
}
printf(")");
}
else if (Pntr->op == SMALL_LETTER)
printf("%c",Pntr->s_letter);
else if (Pntr->op == SCALAR)
printf("%d",Pntr->scalar_num);
else if (Pntr->op == OPERATOR_PROD) {
printf("%c(",OPR_SYMBOL[Pntr->op]);
Print_tree(Pntr->operand1);
Print_opr_prod_tree(Pntr->operand2);
printf(")");
}
else if (Pntr->op == ARTIFICIAL_WORD) {
printf("%c(",OPR_SYMBOL[Pntr->op]);
Print_tree(Pntr->operand1);
Print_art_word(Pntr->operand2);
printf(")");
}
}
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* Pntr -- Pointer to a list of Operators (left, right) and */
/* their operands. */
/* RETURNS: None. */
/* FUNCTION: */
/* Handle the special case of printing Operators. */
/* Print all operators in the list and their operands. */
/* NOTE: */
/* Called only by Print_tree(). i.e Called only for debugging. */
/*******************************************************************/
void Print_opr_prod_tree(struct unexp_tnode *Pntr)
{
while (Pntr != NULL) {
printf(",");
Print_tree(Pntr);
Pntr = Pntr->next;
}
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* Pntr -- Pointer to a tree corresponding to operator */
/* ARTIFICIAL_WORD. */
/* RETURNS: None. */
/* FUNCTION: */
/* Handle the special case of printing ARTIFICIAL_WORD tree. */
/* Print the tree corresponding to operator ARTIFICIAL_WORD. */
/* NOTE: */
/* Called only by Print_tree(). i.e Called only for debugging. */
/*******************************************************************/
void Print_art_word(struct unexp_tnode *Pntr)
{
while (Pntr != NULL) {
printf(",");
Print_tree(Pntr);
Pntr = Pntr->next;
}
}
/*******************************************************************/
/* MODIFIES: */
/* Str_ptr -- Pointer to the string. */
/* Maxsize_ptr -- Maxsize of the string pointed by Str_ptr. */
/* REQUIRES: */
/* Pntr -- pointer to the root of the expanded polynomial tree.*/
/* RETURNS: None. */
/* FUNCTION: */
/* Build the string pointed by Str_ptr, for the given tree, by */
/* traversing it in inorder. */
/* NOTE: */
/* Str_cat() is used for string concatenation. This special */
/* function is needed because when size of the string pointed */
/* by Str_ptr may not be enough to be concatenated with */
/* another string. In which case Str_cat() reallocates more */
/* space for the string pointed by Str_ptr and changes the */
/* Max_size to reflect the change in string size. */
/* Thus string grows varies dynamically to accommodate large */
/* polynomials. */
/*******************************************************************/
void Create_exp_str(struct unexp_tnode *Pntr, char **Str_ptr, int *Maxsize_str_ptr)
{
char Temp_str[10];
if (Pntr != NULL) {
if ((Pntr->op != SMALL_LETTER) && (Pntr->op != SCALAR)) {
if (Pntr->op == JUXT_PROD) {
sprintf(Temp_str,"(");
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
Create_exp_str(Pntr->operand1,Str_ptr,Maxsize_str_ptr);
if (Pntr->op == ADDITION) {
if (!Found_minus(Pntr->operand2)) {
sprintf(Temp_str,"+");
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
}
else if (Pntr->op == SUBTRACTION) {
sprintf(Temp_str,"-");
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
Create_exp_str(Pntr->operand2,Str_ptr,Maxsize_str_ptr);
if (Pntr->op == JUXT_PROD) {
sprintf(Temp_str,")");
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
}
else if (Pntr->op == SMALL_LETTER) {
sprintf(Temp_str,"%c",Pntr->s_letter);
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
else if (Pntr->op == SCALAR) {
if (Pntr->scalar_num == -1) {
sprintf(Temp_str,"-");
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
else if (Pntr->scalar_num != 1) {
sprintf(Temp_str,"%d",Pntr->scalar_num);
Str_cat(Str_ptr,Temp_str,Maxsize_str_ptr);
}
}
}
}
/*******************************************************************/
/* MODIFIES: None. */
/* REQUIRES: */
/* Pntr -- Pointer to a tree. */
/* RETURNS: */
/* 1 if first if any of the operand1's of the tree are scalars */
/* less than 0. */
/* 0 otherwise. */
/* FUNCTION: */
/* Since the tree is traversed in inorder, avoid printing */
/* something like x+-4y. i.e + needs to be suppressed in case */
/* of scalars less than 0, thus correctly prints x-4y. */
/*******************************************************************/
int Found_minus(struct unexp_tnode *Pntr)
{
if (Pntr == NULL)
return(0);
else if (Pntr->scalar_num < 0)
return(1);
else return(Found_minus(Pntr->operand1));
}
/*******************************************************************/
/* MODIFIES: */
/* Pntr -- Pointer to a tree. */
/* REQUIRES: None. */
/* RETURNS: None. */
/* FUNCTION: */
/* Free all the space used for the tree with root pointer as */
/* Pntr. */
/* NOTE: */
/* Traveses the tree in inorder to free all the nodes. */
/* The nodes are freed and entered onto Free tnode queue */
/* through a call to Free_tnode(). */
/*******************************************************************/
/*
* Input : pointer to the root of the unexpanded polynomial tree.
* Function: free the memory space by going to each leaf node.
*
*/
void Free_tnode_tree(struct unexp_tnode *Pntr)
{
/*static int i = 1;*/
if (Pntr != NULL) {
if ((Pntr->operand1 == NULL) && (Pntr->operand2 == NULL) &&
(Pntr->operand3 == NULL) && (Pntr->next == NULL))
Free_tnode(Pntr);
else {
Free_tnode_tree(Pntr->operand1);
Free_tnode_tree(Pntr->operand2);
Free_tnode_tree(Pntr->operand3);
Free_tnode_tree(Pntr->next);
Free_tnode(Pntr);
}
}
}