Line data Source code
1 : #include "poly.h"
2 : #include <ctype.h>
3 : #include <stdio.h>
4 : #include <stdlib.h>
5 :
6 : // struct to store each term, so coeff*x^{exp}
7 : typedef struct term {
8 : int coeff;
9 : int exp;
10 : struct term *next;
11 : } term_t;
12 :
13 : struct poly_t {
14 : term_t *first;
15 : };
16 : /* void free_poly(poly_t *poly) { */
17 : /* term_t *term = poly->first, *next; */
18 : /* while (term) { */
19 : /* next = term->next; */
20 : /* free(term); */
21 : /* term = next; */
22 : /* } */
23 : /* free(poly); */
24 : /* } */
25 6 : void free_poly(poly_t *poly) {
26 6 : term_t *term = poly->first;
27 : term_t *next;
28 :
29 26 : while (term != NULL) {
30 20 : next = term->next;
31 20 : term->next = NULL;
32 20 : free(term);
33 20 : term = next;
34 : }
35 6 : poly->first = NULL;
36 6 : free(poly);
37 6 : }
38 :
39 22 : void add_term(poly_t *poly, int coeff, int exp) {
40 22 : term_t **curr = &poly->first, *term;
41 :
42 : // Find insertion point or existing term
43 54 : while ((term = *curr) && term->exp > exp)
44 32 : curr = &term->next;
45 :
46 : // Combine like terms or insert new term
47 22 : if (term && term->exp == exp) {
48 2 : term->coeff += coeff;
49 2 : return;
50 : }
51 :
52 20 : if (coeff) {
53 20 : term = malloc(sizeof(term_t));
54 20 : term->coeff = coeff;
55 20 : term->exp = exp;
56 20 : term->next = *curr;
57 20 : *curr = term;
58 20 : }
59 22 : }
60 :
61 : /* poly_t *mul(poly_t *a, poly_t *b) { */
62 : /* poly_t *r = malloc(sizeof(poly_t)); */
63 : /* r->first = NULL; */
64 :
65 : /* for (term_t *at = a->first; at; at = at->next) */
66 : /* for (term_t *bt = b->first; bt; bt = bt->next) */
67 : /* add_term(r, at->coeff * bt->coeff, at->exp + bt->exp); */
68 :
69 : /* return r; */
70 : /* } */
71 2 : poly_t *mul(poly_t *a, poly_t *b) {
72 2 : term_t *at = a->first;
73 2 : term_t *bt = b->first;
74 : int coeff, exp;
75 :
76 2 : poly_t *r = malloc(sizeof(poly_t));
77 2 : r->first = NULL;
78 :
79 7 : while (at != NULL) {
80 17 : while (bt != NULL) {
81 12 : coeff = at->coeff * bt->coeff;
82 12 : exp = at->exp + bt->exp;
83 12 : add_term(r, coeff, exp);
84 12 : bt = bt->next;
85 : }
86 5 : at = at->next;
87 5 : bt = b->first;
88 : }
89 2 : return r;
90 : }
91 :
92 :
93 : /* poly_t *new_poly_from_string(const char *str) { */
94 : /* poly_t *poly = malloc(sizeof(poly_t)); */
95 : /* poly->first = NULL; */
96 :
97 : /* int sign = 1, num = 0, coeff = 0, exp = 0; */
98 :
99 : /* for (; *str; str++) { */
100 : /* switch (*str) { */
101 : /* case ' ': */
102 : /* if (coeff || num) { */
103 : /* add_term(poly, sign * (coeff ? coeff : num), exp ? exp : 0); */
104 : /* sign = 1; */
105 : /* num = coeff = exp = 0; */
106 : /* } */
107 : /* break; */
108 : /* case '-': */
109 : /* sign = -1; */
110 : /* break; */
111 : /* case '+': */
112 : /* sign = 1; */
113 : /* break; */
114 : /* case 'x': */
115 : /* coeff = num ? num : 1; */
116 : /* num = 0; */
117 : /* exp = *(str + 1) == '^' ? atoi(str + 2) : 1; */
118 : /* break; */
119 : /* default: */
120 : /* if (isdigit(*str)) */
121 : /* num = 10 * num + (*str - '0'); */
122 : /* break; */
123 : /* } */
124 : /* } */
125 :
126 : /* // Handle last term */
127 : /* if (coeff || num) */
128 : /* add_term(poly, sign * (coeff ? coeff : num), exp ? exp : 0); */
129 :
130 : /* return poly; */
131 : /* } */
132 4 : poly_t *new_poly_from_string(const char *str) {
133 4 : poly_t *poly = malloc(sizeof(poly_t));
134 4 : poly->first = NULL;
135 :
136 4 : const char *s = str;
137 4 : char sign = '+';
138 4 : int num = 0;
139 4 : int coeff = 0;
140 4 : int exp = 0;
141 :
142 49 : while (*s) {
143 45 : switch (*s) {
144 : case '-':
145 : case '+':
146 6 : sign = *s;
147 6 : s++;
148 6 : break;
149 : case 'x':
150 6 : if (num == 0) {
151 2 : num = 1; // no coefficient, but x is present so it is 1.
152 2 : }
153 6 : coeff = (sign == '-') ? -num : num;
154 6 : exp = 1; // at least one x present.
155 6 : num = 0;
156 6 : s++;
157 6 : break;
158 :
159 : case ' ':
160 : // c is 0 => don't need to add new term.
161 12 : if (coeff == 0) {
162 6 : s++;
163 6 : break;
164 : }
165 : // update e if a number has been found.
166 6 : if (num != 0)
167 3 : exp = num;
168 :
169 : // add term to poly.
170 6 : add_term(poly, coeff, exp);
171 : // reset state.
172 6 : sign = '+';
173 6 : coeff = 0;
174 6 : exp = 0;
175 6 : num = 0;
176 6 : s++;
177 6 : break;
178 :
179 : default:
180 21 : if (isdigit(*s)) {
181 18 : num = 10 * num + (*s - '0');
182 18 : }
183 21 : s++;
184 21 : break;
185 : }
186 : }
187 : // end of string reached, add term if possible.
188 4 : if (num != 0) {
189 4 : add_term(poly, num, exp);
190 4 : }
191 :
192 4 : return poly;
193 : }
194 : /* void print_poly(poly_t *poly) { */
195 : /* int first = 1; */
196 : /* for (term_t *term = poly->first; term; term = term->next) { */
197 : /* if (!first) */
198 : /* printf(" %c ", term->coeff > 0 ? '+' : '-'); */
199 : /* else */
200 : /* first = 0; */
201 :
202 : /* int abs_coeff = abs(term->coeff); */
203 : /* if (abs_coeff > 1 || term->exp == 0) */
204 : /* printf("%d", abs_coeff); */
205 :
206 :
207 : /* if (term->exp > 0) { */
208 : /* if (term->exp > 1) */
209 : /* printf("x^%d", term->exp); */
210 : /* else */
211 : /* printf("x"); */
212 : /* }} */
213 : /* printf("\n"); */
214 : /* } */
215 6 : void print_poly(poly_t *poly) {
216 6 : term_t *term = poly->first;
217 6 : int first = 1; // Flag to handle the first term.
218 :
219 26 : while (term != NULL) {
220 20 : char sign = (term->coeff > 0) ? '+' : '-';
221 20 : int coeff = abs(term->coeff);
222 20 : int exp = term->exp;
223 :
224 : // Print sign if not first element, since first is always positive.
225 20 : if (!first) {
226 14 : printf(" %c ", sign);
227 14 : } else {
228 6 : first = 0;
229 : }
230 20 : if (coeff > 1 || exp == 0)
231 18 : printf("%d", coeff);
232 20 : if (exp > 0)
233 14 : printf("x");
234 20 : if (exp > 1)
235 9 : printf("^%d", exp);
236 :
237 20 : term = term->next; // Move to the next term
238 : }
239 6 : printf("\n");
240 6 : }
|
