PolynomialMultiplier

SRM 188 · 2004-03-25 · by legakis

SRM 188 · 2004-03-25 · by legakis · Math, String Parsing

Show categories

Class Name: PolynomialMultiplier

Return Type: String

Method Name: product

Arg Types: (string, string)

Problem Statement

Two polynomials are multiplied together by multiplying each term in the first polynomial with each term in the second polynomial, and adding all of these individual products together. For example:


      (4*x^4 + 1) * (3*x^5 + 7*x)
    = (4*x^4 * 3*x^5) + (4*x^4 * 7*x) + (1 * 3*x^5) + (1 * 7*x)
    = 12*x^9 + 28*x^5 + 3*x^5 + 7*x

This can be simplified by combining the two x^5 terms:


    = 12*x^9 + 31*x^5 + 7*x

Write a program which multiplies two polynomials, and simplifies the product by combining terms with the same exponent. Each polynomial will be a function of x, and will consist of one or more terms separated by " + " (a space, '+', and another space). Each term will be in one of the following forms:


    1
    #
    x
    x^#
    #*x
    #*x^#
    (Each '#' character represents a single digit between '2' and '9', inclusive.)

Your program should return the product as a sum of terms, each in one of the formats above, except that the coefficients and exponents in your return value may be larger than a single digit. (Note that coefficients and exponents of 1 are omitted.) In between each term, insert the String " + " (a space, '+', and another space). You should output the terms in order from largest exponent of x to smallest exponent of x. If two or more terms have the same exponent, add their coefficients together to combine them into a single term.

Notes

The terms in the input functions will not necessarily be sorted by exponent of x.
There may be multiple terms in the input function with the same exponent of x.

Constraints

f1 and f2 will each contain between 1 and 50 characters, inclusive.
f1 and f2 will conform to the formatting rules in the problem statement.

Examples

"1 + x"
"1 + x"
Returns: "x^2 + 2*x + 1"

(1 + x) * (1 + x) = 1 + x + x + x*x = x^2 + 2*x + 1 Remember to combine terms with equal exponents, and sort from greatest to smallest exponent.

"4*x^4 + 1"
"3*x^5 + 7*x"
Returns: "12*x^9 + 31*x^5 + 7*x"

This is the example from the problem statement.

"1 + x + 1 + x"
"5 + 5"
Returns: "20*x + 20"

"8*x^5"
"9*x^7"
Returns: "72*x^12"

"5*x^3 + x^4 + 8 + 2*x^6"
"3*x^5 + 4*x + 7*x^9"
Returns: "14*x^15 + 7*x^13 + 35*x^12 + 6*x^11 + 59*x^9 + 15*x^8 + 8*x^7 + 28*x^5 + 20*x^4 + 32*x"

Submissions are judged against all 18 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class PolynomialMultiplier with a public method string product(string f1, string f2) · 18 test cases · 2 s / 256 MB per case