Expand algebraic expression with distribution

Question

Given an expression of lowercase letters, '+', '', and parentheses with no '+' outside any parentheses, return an equivalent expression containing only '+' by fully expanding all products (e.g., (a+b)(c+d) → ac+ad+bc+bd). Achieve O(1) extra-space complexity. Follow-up: If '+' may appear outside parentheses (e.g., a+bc(d+e+f)+k+m*(g+h)+i), output the fully expanded '+'-only form (a+bcd+bce+bcf+k+mg+mh+i). Provide working code that may use O(n) extra space (e.g., a stack).

Expand algebraic expression with distribution

You are given a string expr representing an algebraic expression made of lowercase letters, the operators + (addition) and * (multiplication), and parentheses. Multiplication binds tighter than addition, and parentheses group sub-expressions. Each letter behaves like a variable, and concatenation denotes a product (so a*b is written ab after expansion).

Return an equivalent expression that uses ONLY +, obtained by fully distributing every product over every sum (i.e., expand into a flat sum of monomials).

Within each resulting monomial, keep the letters in the left-to-right order in which they were multiplied (do NOT sort letters). Keep the monomials in the natural left-to-right traversal order produced by distribution, and join them with +.

For example:

• (a+b)*(c+d) expands to ac+ad+bc+bd.
• a+b*c*(d+e+f)+k+m*(g+h)+i expands to a+bcd+bce+bcf+k+mg+mh+i.

The input is always a well-formed expression (balanced parentheses, no unary operators, no empty groups). The original problem first restricts + to appear only inside parentheses and asks for O(1) extra space; the general follow-up allows + anywhere (outside parentheses too). This solution handles the general case, which subsumes the restricted one, using a stack-based recursive parse (O(n) auxiliary space for the parse stack and the output list of monomials).

Constraints

• 1 <= len(expr)
• expr contains only lowercase letters 'a'-'z', '+', '*', '(' and ')'
• Parentheses are balanced and there are no empty groups
• Multiplication has higher precedence than addition; operators are binary
• Within a monomial, letters appear in multiplication (left-to-right) order and are NOT re-sorted

Examples

Example 1

Input: ("(a+b)*(c+d)",)
Output: "ac+ad+bc+bd"

Explanation: Distribute the product of two binomials: each term of the first sum times each term of the second.

Example 2

Input: ("a+b*c*(d+e+f)+k+m*(g+h)+i",)
Output: "a+bcd+bce+bcf+k+mg+mh+i"

Explanation: Follow-up case with '+' outside parentheses: 'a', 'k', 'i' pass through; bc(d+e+f) expands to bcd+bce+bcf; m*(g+h) expands to mg+mh.

Hints

1. Model the expression with a recursive-descent grammar: expr = term ('+' term), term = factor ('' factor)*, factor = letter | '(' expr ')'.
2. Have each parse function return a LIST of monomials (strings). A sum concatenates the two lists; a product takes the cartesian product, concatenating each left monomial with each right monomial in order.
3. A single letter parses to a one-element list [letter]. Joining the final list with '+' gives the answer. The recursion stack provides the O(n) extra space the follow-up permits.