Question

A polynomial p(x) is an expression in variable x which is in the form axn + bxn-1 + …. + jx + k, where a, b, …, j, k are real numbers, and n is a non-negative integer. n is called the degree of polynomial. Every term in a polynomial consists of a coefficient and an exponent. For example, for the first term axn, a is the coefficient and n is the exponent. This assignment is about representing and computing polynomials using linked list. Consider the polynomial 4x3 + 6x2 + 10x + 6. We can use a linked list to represent this polynomial as in Figure below: Every node corresponds to a term in the Polynomial. The node stores the coefficient and the exponent of the term. The node also has a pointer to point the next node. However, all terms are not necessarily present in a polynomial, e.g., in 12x11 + 9x8 + 4x3 + 5x + 4, the term for x7 is not present. To represent this polynomial, we need a linked list of 5 nodes. Consider addition of two polynomials 5x12 + 2x9 + 4x7 + 6x6 + x3 and 7x8 + 2x7 + 8x6 + 6x4 + 2x2 + 3x + 40. The resulting polynomial is 5x12 + 2x9 + 7x8 + 6x7 + 14x6 + 6x4 +x3 + 2x2 + 3x + 40. Now notice how the addition is carried out. Let us say that the result of addition will be stored in a third linked list. We start with the term which is of highest degree in any of the polynomials. If there is no item having same exponent, we simply append the term to the new list, and continue with the process. Wherever we find that the exponents match, we simply add the coefficients and then store the term in the new list. If one list gets exhausted earlier and the other list still contains some lower order terms, then simply append the remaining terms to the new list. Page 5 of 7 Now we are in a position to write an algorithm for adding two polynomials. Let phead1, phead2 and phead3 represent the pointers of the three lists under consideration. We want to add phead1 and phead 2, and store the result in phead3. This addition can be performed using the procedure below. p1 = phead1; p2 = phead2; p3 = phead3; While ( (p1 != NULL) or (p2 != NULL) ) { If ( p1 = NULL ) { While ( p2 != NULL) { p3->exponent = p2->exponent; p3->coefficient = p2->coefficient; p2 = p2->next; p3 = p3->next; } } Else-If ( p2 = NULL ) { While ( p1 != NULL) { p3->exponent = p1->exponent; p3->coefficient = p1->coefficient; p1 = p1->next; p3 = p3->next; } } Else { While ( p1->exponent > p2->exponent ) { p3->exponent = p1->exponent; p3->coefficient = p1->coefficient; p1 = p1->next; p3 = p3->next; } While ( p1->exponent < p2->exponent ) { p3->exponent = p2->exponent; p3->coefficient = p2->coefficient; p2 = p2->next; p3 = p3->next; } While ( p1->exponent = p2->exponent ) { p3->exponent = p1-> exponent; Page 6 of 7 p3->coefficient = p1->coefficient + p2->coefficient; p1 = p1->next ; p2 = p2->next ; p3 = p3->next; } } } You should write a program in which user can provide polynomials as input. Each polynomial should be represented as a linked list. Your program should be capable of adding two polynomials and storing the resultant polynomial in another linked list. Note that the number of polynomials in the system can be up to 10. The polynomials should be indexed as 0, 1, …, 9. The Interface Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 1 Type the polynomial: x^4+5x^2 A polynomial is created. You now have total 1 polynomials in system. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 1 Type the polynomial: 100x^19+43x^4+11x^0 A polynomial is created. You now have total 2 polynomials in system. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 3 Which polynomial you want to see (0-9)? 4 The input is invalid. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 3 Which polynomial you want to see (0-9)? 0 The polynomial is: x^4+5x^2 Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 2 Let you want to perform C=A+B. Then enter A B C: 0 1 2 The input is invalid. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 1 Type the polynomial: 2x^2+3x^1+5x^0 Page 7 of 7 A polynomial is created. You now have total 3 polynomials in system. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 2 Let you want to perform C=A+B. Then enter A B C: 0 1 2 The polynomials 0 and 1 are added, and the result is stored in polynomial 2. Enter the corresponding number of your desired action: 1 – create a new polynomial, 2 – adding two polynomials, and 3 – print a polynomial. 3 Which polynomial you want to see (0-9)? 2 The polynomial is: 100x^19+44x^4+5x^2+11x^0

Answer 1

This is a really long question and is framed pretty poorly but from the information, that I have gathered, I will provide you with a working c++ code(which is going to be very long). One thing to remember, the first part of the code itself is not easy, you are being given the polynomial in the form of a string so you have to parse the string in such a manner so as to extract the necessary information from the string, the necessary information being the coefficients of  the polynomials and their corresponding exponents. Now remember why we are doing this, you are given the polynomial in the form of a string, so the computer or program cannot just extract the information of the polynomial without doing anything on the given string, so we have to parse the string accordingly. So here goes the code. It is quite big and may contain some bugs (i have checked it though). However, if you find any bug just let me know in the comments and I will be happy to help you out anytime. Thank you.

Code:-

#include <bits/stdc++.h> // imports all necessary headers

using namespace std;

class poly
{
public:
   int coefficient;
   int exponent;
   poly *next;
};

int mark[20];

int main()
{  
   poly* head[20];
   for(int i = 0; i < 20; i++)
   {
       head[i] = NULL;
   }
   int cur_idx = -1;
   while(1)
   {
       cout << "Enter the corresponding number of your desired action" << endl;
       int id;
       cout << "Press 1 to create a new polynomial" << endl;
       cout << "Press 2 to add to two polynomials" << endl;
       cout << "Press 3 to print a polynomial" << endl;
       cin >> id;
       if(id == 1)
       {
           cout << "Type the Polynomial" << endl;
           string str, temp_str = "";
           cin >> str;
           str += '+';
           bool now = true;
           poly* prev = NULL;
           poly* temp = NULL;
           cur_idx++;
           mark[cur_idx]++;
           cout << "A Polynomial is created. You now have total of " << cur_idx << " polynomials in system" << endl;
           for(int i = 0; i < (int)str.size(); i++)
           {
               if(str[i] == '+')
               {
                   string coeff = "", expo = "";
                   stringstream ss1, ss2;
                   int j = 0;
                   while(temp_str[j] != 'x')
                   {
                       coeff += temp_str[j];
                       j++;
                   }
                   while(j < (int)temp_str.size())
                   {
                       if(isdigit(temp_str[j]))
                           expo += temp_str[j];
                       j++;
                   }
                   int COEFF = 0, EXPO = 0;
                   ss1 << coeff;
                   ss2 << expo;
                   ss1 >> COEFF;
                   ss2 >> EXPO;
                   COEFF = max(1, COEFF);
                   temp_str = "";
                   if(now)
                   {
                       now = false;
                       head[cur_idx] = new poly();
                       head[cur_idx]->coefficient = COEFF;
                       head[cur_idx]->exponent = EXPO;
                       head[cur_idx]->next = NULL;
                       prev = head[cur_idx];
                   }
                   else
                   {
                       temp = new poly();
                       temp->coefficient = COEFF;
                       temp->exponent = EXPO;
                       temp->next = NULL;
                       prev->next = temp;
                       prev = temp;
                   }
               }
               else
               {
                   temp_str += str[i];
               }
           }
       }
       if(id == 2)
       {
           cout << "Let you want to perform C = A + B" << endl;
           cout << "Then enter A B C:";
           int A, B, C;
           cin >> A >> B >> C;
           if(!mark[A] or !mark[B] or !mark[C])
           {
               cout << "The input is invalid" << endl;
           }
           else
           {
               poly* p1 = head[A];
               poly* p2 = head[B];
               poly* p3 = head[C];
               while((p1 != NULL) or (p2 != NULL))
               {
                   if(p1 == NULL)
                   {
                       while(p2 != NULL)
                       {
                           p3->exponent = p2->exponent;
                           p3->coefficient = p2->coefficient;
                           p2 = p2->next;
                           p3 = p3->next;
                       }
                   }
                   else if(p2 == NULL)
                   {
                       while(p1 != NULL)
                       {
                           p3->exponent = p1->exponent;
                           p3->coefficient = p1->coefficient;
                           p1 = p1->next;
                           p3 = p3->next;
                       }
                   }
                   else
                   {
                       while(p1->exponent > p2->exponent)
                       {
                           p3->exponent = p1->exponent;
                           p3->coefficient = p1->coefficient;
                           p1 = p1->next;
                           p3 = p3->next;
                       }
                       while(p1->exponent < p2->exponent)
                       {
                           p3->exponent = p2->exponent;
                           p3->coefficient = p2->coefficient;
                           p2 = p2->next;
                           p3 = p3->next;
                       }
                       while(p1->exponent = p2->exponent)
                       {
                           p3->exponent = p1-> exponent;
                           p3->coefficient = p1->coefficient + p2->coefficient;
                           p1 = p1->next;
                           p2 = p2->next;
                           p3 = p3->next;
                       }
                   }
               }
           }
       }
       if(id == 3)
       {
           cout << "Which Polynomial you want to see ?" << endl;
           int no;
           cin >> no;
           if(no > cur_idx)
           {
               cout << "The input is invalid" << endl;
           }
           else
           {
               poly* temp = head[no];
               string disp_pol = "";
               while(temp != NULL)
               {
                   disp_pol += to_string(temp->coefficient);
                   disp_pol += "x^";
                   disp_pol += to_string(temp->exponent);
                   disp_pol += '+';
                   temp = temp->next;
               }
               for(int k = 0; k < disp_pol.size() - 1; k++)
                   cout << disp_pol[k];
               cout << endl;
           }
       }
   }
   return 0;
}