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).