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             : 
      17           6 : void free_poly(poly_t *poly) {
      18           6 :   if (poly == NULL)
      19           0 :     return;
      20           6 :   term_t *term = poly->first;
      21             :   term_t *next;
      22             : 
      23          26 :   while (term != NULL) {
      24          20 :     next = term->next;
      25          20 :     term->next = NULL;
      26          20 :     free(term);
      27          20 :     term = next;
      28             :   }
      29           6 :   poly->first = NULL;
      30           6 :   free(poly);
      31           6 : }
      32             : 
      33          22 : void add_term(poly_t *poly, int coeff, int exp) {
      34             :   // If coefficient is zero, don't add the term
      35          22 :   if (coeff == 0) {
      36           0 :     return;
      37             :   }
      38             : 
      39             :   // If the list is empty, create the first term
      40          22 :   if (!poly->first) {
      41           6 :     term_t *new_term = malloc(sizeof(term_t));
      42           6 :     new_term->coeff = coeff;
      43           6 :     new_term->exp = exp;
      44           6 :     new_term->next = NULL;
      45           6 :     poly->first = new_term;
      46           6 :     return;
      47             :   }
      48             : 
      49             :   // Check if there's an existing term with the same exponent
      50          16 :   term_t *current = poly->first;
      51          16 :   term_t *prev = NULL;
      52             : 
      53          48 :   while (current != NULL) {
      54          34 :     if (current->exp == exp) {
      55             :       // Combine coefficients of like terms
      56           2 :       current->coeff += coeff;
      57             : 
      58             :       // If the coefficient becomes zero, remove the term
      59           2 :       if (current->coeff == 0) {
      60           0 :         if (prev == NULL) {
      61           0 :           poly->first = current->next;
      62           0 :         } else {
      63           0 :           prev->next = current->next;
      64             :         }
      65           0 :         free(current);
      66           0 :       }
      67           2 :       return;
      68             :     }
      69             : 
      70          32 :     prev = current;
      71          32 :     current = current->next;
      72             :   }
      73             : 
      74             :   // If no term with the same exponent is found, add a new term
      75          14 :   term_t *new_term = malloc(sizeof(term_t));
      76          14 :   new_term->coeff = coeff;
      77          14 :   new_term->exp = exp;
      78          14 :   new_term->next = NULL;
      79             : 
      80          14 :   current = poly->first;
      81          14 :   prev = NULL;
      82          43 :   while (current != NULL && current->exp > exp) {
      83          29 :     prev = current;
      84          29 :     current = current->next;
      85             :   }
      86             : 
      87          14 :   if (prev == NULL) {
      88           0 :     new_term->next = poly->first;
      89           0 :     poly->first = new_term;
      90           0 :   } else {
      91          14 :     new_term->next = current;
      92          14 :     prev->next = new_term;
      93             :   }
      94          22 : }
      95             : 
      96           2 : poly_t *mul(poly_t *a, poly_t *b) {
      97           2 :   term_t *at = a->first;
      98           2 :   term_t *bt = b->first;
      99             :   int coeff, exp;
     100             : 
     101           2 :   poly_t *r = malloc(sizeof(poly_t));
     102           2 :   r->first = NULL;
     103             : 
     104           7 :   while (at != NULL) {
     105          17 :     while (bt != NULL) {
     106          12 :       coeff = at->coeff * bt->coeff;
     107          12 :       exp = at->exp + bt->exp;
     108          12 :       add_term(r, coeff, exp);
     109          12 :       bt = bt->next;
     110             :     }
     111           5 :     at = at->next;
     112           5 :     bt = b->first;
     113             :   }
     114           2 :   return r;
     115             : }
     116             : 
     117           4 : poly_t *new_poly_from_string(const char *str) {
     118           4 :   poly_t *poly = malloc(sizeof(poly_t));
     119           4 :   poly->first = NULL;
     120             : 
     121           4 :   const char *s = str;
     122           4 :   char sign = '+';
     123           4 :   int num = 0;
     124           4 :   int coeff = 0;
     125           4 :   int exp = 0;
     126             : 
     127          49 :   while (*s) {
     128          45 :     switch (*s) {
     129             :     case '-':
     130             :     case '+':
     131           6 :       sign = *s;
     132           6 :       s++;
     133           6 :       break;
     134             :     case 'x':
     135           6 :       if (num == 0) {
     136           2 :         num = 1; // no coefficient, but x is present so it is 1.
     137           2 :       }
     138           6 :       coeff = (sign == '-') ? -num : num;
     139           6 :       exp = 1; // at least one x present.
     140           6 :       num = 0;
     141           6 :       s++;
     142           6 :       break;
     143             : 
     144             :     case ' ':
     145             :       // c is 0 => don't need to add new term.
     146          12 :       if (coeff == 0) {
     147           6 :         s++;
     148           6 :         break;
     149             :       }
     150             :       // update e if a number has been found.
     151           6 :       if (num != 0)
     152           3 :         exp = num;
     153             : 
     154             :       // add term to poly.
     155           6 :       add_term(poly, coeff, exp);
     156             :       // reset state.
     157           6 :       sign = '+';
     158           6 :       coeff = 0;
     159           6 :       exp = 0;
     160           6 :       num = 0;
     161           6 :       s++;
     162           6 :       break;
     163             : 
     164             :     default:
     165          21 :       if (isdigit(*s)) {
     166          18 :         num = 10 * num + (*s - '0');
     167          18 :       }
     168          21 :       s++;
     169          21 :       break;
     170             :     }
     171             :   }
     172             :   // end of string reached, add term if possible.
     173           4 :   if (num != 0) {
     174           4 :     add_term(poly, num, exp);
     175           4 :   }
     176             : 
     177           4 :   return poly;
     178             : }
     179             : 
     180           6 : void print_poly(poly_t *poly) {
     181           6 :   term_t *term = poly->first;
     182           6 :   int first = 1; // Flag to handle the first term.
     183             : 
     184          26 :   while (term != NULL) {
     185          20 :     char sign = (term->coeff > 0) ? '+' : '-';
     186          20 :     int coeff = abs(term->coeff);
     187          20 :     int exp = term->exp;
     188             : 
     189             :     // Print sign if not first element, since first is always positive.
     190          20 :     if (!first) {
     191          14 :       printf(" %c ", sign);
     192          14 :     } else {
     193           6 :       first = 0;
     194             :     }
     195          20 :     if (coeff > 1 || exp == 0)
     196          18 :       printf("%d", coeff);
     197          20 :     if (exp > 0)
     198          14 :       printf("x");
     199          20 :     if (exp > 1)
     200           9 :       printf("^%d", exp);
     201             : 
     202          20 :     term = term->next; // Move to the next term
     203             :   }
     204           6 :   printf("\n");
     205           6 : }