770. Basic Calculator IV

Practice Basic Calculator IV for free on NudgeCode: Hard, Stack pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

expression is built from non-negative integers, variables (lowercase words such as a or temp), +, -, * and parentheses, with every token separated by a single space (e.g. "e + 8 - a + 5", "( e + 8 ) * ( e - 8 )"). The usual precedence applies: parentheses, then *, then + / - left to right. There is no unary minus.

evalvars[i] has the known value evalints[i]; substitute these, then simplify the expression to a polynomial in the remaining variables and return its terms as a list of strings:

• Each term is written as its coefficient followed by its variables in lexicographic order, joined by *, e.g. "-2*a*b*b". A constant term is just the number, e.g. "14".
• Order terms by degree (number of variable factors, counting repeats) from high to low; terms of equal degree are ordered by their variable lists compared lexicographically (["a","b"] before ["a","c"]). The constant goes last.
• Leave out terms whose coefficient is 0 (so "0" is never returned; a zero polynomial is []).

Example

expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]  ->  ["-1*a","14"]
expression = "e - 8 + temperature - pressure", evalvars = ["e","temperature"], evalints = [1,12]
->  ["-1*pressure","5"]
expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []  ->  ["1*e*e","-64"]

Constraints

• 1 <= expression.length <= 250; parentheses may appear without spaces next to them, as in "(e + 8)"
• 0 <= evalvars.length <= 100, 1 <= evalvars[i].length <= 20, -100 <= evalints[i] <= 100
• All coefficients and intermediate values fit in a 32-bit signed integer