Description
Using linked list, write a program to add, subtract and evaluate polynomials: P1(x), P2(x), P3(x)
and P4(x) where P1(x) and P2(x) are input polynomials and P3(x) = P1(x)+P2(x) and
P4(x)=P1(x)-P2(x). Each node in the linked list correspond to a term in the polynomial. So, in
your node structure – you may keep two data components – integers pow and coeff; and one
pointer to the next node.
Input Format:
First line mentions K i.e. the number of test cases. Then there are three lines for each test case,
In the first two lines of a test case, First number indicate the highest degree of polynomials N and
then there are N+1 integers which are the coefficients of polynomial terms in descending order.
In the third (and last line) of a test case, there is one integer i.e. value of x for which you need to
evaluate the polynomials. (Constraints: 0≤K≤50, 0≤N≤9, -2≤x≤2, and Input coefficient terms
would be between -100 to +100; Assume you can safely do calculations for each polynomial
term without worrying about underflow/overflow issues).
Sample Input 1:
1
7 1 0 0 0 10 -3 0 1
3 4 0 0 -2
2
Explanation of Input Format (Considering 2nd Polynomial mentioned above)
3 4 0 0 -2
Highest degree of
polynomial
Coefficient of
�!
Coeff of �” Coeff of �# Coeff of �$
As per above format: 7 1 0 0 0 10 -3 0 1===> �% + 10�3 − 3�2 + 1
3 4 0 0 2 ===> 4�3 − 2
2 ===> value of x should be in range of -2 to 2.
Sample Output 1:
P1(x) : 1x^7 + 10x^3 – 3x^2 + 1
P2(x) : 4x^3 – 2
P3(x) = P1(x) + P2(x) : 1x^7 + 14x^3 – 3x^2 – 1
P4(x) = P1(x) – P2(x) : 1x^7 + 6x^3 – 3x^2 + 3
P1(2) = 197
P2(2) = 30
P3(2) = 227
P4(2) = 167
Note: There is a single space before and after =, +, -, and : in the output.
Explanation of Output Format:
1x^7 + 14x^3 – 3x^2 – 1 ====> �1(�)+�2(�)
1x^7 + 6x^3 – 3x^2 + 3 ====> �1(�) − �2(�)
197 30 227 167 ====> �1(2) �”(2) (�1(2) + �1(2)) (�1(2) − �2(2))
Note that there should be NO nodes in the linked list for the polynomial terms having 0
coefficient value. In the above example, the polynomials f1 and f2 were to be represented using 4
and 2 nodes in the linked list, respectively.
Sample Input 2 Sample Output 2
3
7 1 0 0 0 10 -3 0 1
3 4 0 0 -2
2
7 1 0 0 0 10 -3 0 1
3 4 0 0 -2
1
7 1 0 0 0 10 -3 0 1
7 1 0 0 0 10 -3 0 1
P1(x) : 1x^7 + 10x^3 – 3x^2 + 1
P2(x) : 4x^3 – 2
P3(x) = P1(x) + P2(x) : 1x^7 + 14x^3 – 3x^2 – 1
P4(x) = P1(x) – P2(x) : 1x^7 + 6x^3 – 3x^2 + 3
P1(2) = 197
P2(2) = 30
P3(2) = 227
P4(2) = 167
P1(x) : 1x^7 + 10x^3 – 3x^2 + 1
2 P2(x) : 4x^3 – 2
P3(x) = P1(x) + P2(x) : 1x^7 + 14x^3 – 3x^2 – 1
P4(x) = P1(x) – P2(x) : 1x^7 + 6x^3 – 3x^2 + 3
P1(1) = 9
P2(1) = 2
P3(1) = 11
P4(1) = 7
P1(x) : 1x^7 + 10x^3 – 3x^2 + 1
P2(x) : 1x^7 + 10x^3 – 3x^2 + 1
P3(x) = P1(x) + P2(x) : 2x^7 + 20x^3 – 6x^2 + 2
P4(x) = P1(x) – P2(x) : 0
P1(2) = 197
P2(2) = 197
P3(2) = 394
P4(2) = 0
Remarks: There are three test cases in 2nd Sample Input.
Remember to appropriate free the memory space after each test case.
// Input would be read from terminal (i.e. stdin) and not from any file.
