#### Approach #1: Polynomial Class [Accepted]

Intuition

Keep a class Poly that knows a map from a list of free variables to a coefficient, and support operations on this class.

Algorithm

Each function is straightforward individually. Let's list the functions we use:

• Poly:add(this, that) returns the result of this + that.
• Poly:sub(this, that) returns the result of this - that.
• Poly:mul(this, that) returns the result of this * that.
• Poly:evaluate(this, evalmap) returns the polynomial after replacing all free variables with constants as specified by evalmap.
• Poly:toList(this) returns the polynomial in the correct output format.

• Solution::combine(left, right, symbol) returns the result of applying the binary operator represented by symbol to left and right.

• Solution::make(expr) makes a new Poly represented by either the constant or free variable specified by expr.
• Solution::parse(expr) parses an expression into a new Poly.

Complexity Analysis

• Time Complexity: Let is the length of expression and is the length of evalvars and evalints. With an expression like (a + b) * (c + d) * (e + f) * ... the complexity is .

• Space Complexity: .

Analysis written by: @awice.