Design a Polynomial Expression Parser and Canonical Formatter

## Interview Prompt Design and implement a parser that converts a polynomial expression into an internal representation and returns a canonical string. Extend it to accept a combination of multiple polynomials and normalize the combined result. The source does not specify an exact grammar, so begin by defining the supported variables, coefficients, signs, exponents, separators or operators, whitespace, and output ordering. Include negative values and numeric-overflow behavior. ### Constraints & Assumptions - The accepted grammar and rejected syntax must be explicit and testable. - Like terms are combined and zero coefficients are omitted from canonical output. - Canonical formatting must be deterministic for equivalent accepted inputs. - Coefficient and exponent parsing must detect overflow instead of wrapping silently. ### Clarifying Questions to Ask - Is the expression univariate or multivariate, and are parentheses supported? - Does combining polynomials mean addition only or a fuller expression grammar? - What integer width or arbitrary-precision policy applies to coefficients and exponents? - Which term order and formatting rules define the canonical output? ### What a Strong Answer Covers - A tokenizer and grammar appropriate to the agreed syntax rather than fragile delimiter splitting. - An internal term representation whose key captures variable powers and whose value is the coefficient. - Combination of like terms, deletion of zero terms, and deterministic term ordering. - Checked numeric parsing and arithmetic plus precise syntax-error positions. - Unit tests for negatives, omitted coefficients, repeated terms, malformed operators, whitespace, and overflow. ### Follow-up Questions - How would multiplication and parentheses change the parser and intermediate representation? - How would you stream a very long sum without retaining every token? - How would multivariate canonical ordering be defined?