Given an expression such as expression = "e + 8 - a + 5" and an evaluation map such as {"e": 1} (given in terms of evalvars = ["e"] and evalints = [1]), return a list of tokens representing the simplified expression, such as ["-1*a","14"]
"2x" or "-x".Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.
expression = "1 + 2 * 3" has an answer of ["7"].The format of the output is as follows:
"b*a*c", only "a*b*c"."a*a*b*c" has degree 4.["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"].0 are not included.
"0" has an output of [].Note: You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Example 1:
Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1] Output: ["-1*a","14"]
Example 2:
Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12] Output: ["-1*pressure","5"]
Example 3:
Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = [] Output: ["1*e*e","-64"]
Constraints:
1 <= expression.length <= 250expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.expression does not contain any leading or trailing spaces.expression are separated by a single space.0 <= evalvars.length <= 1001 <= evalvars[i].length <= 20evalvars[i] consists of lowercase English letters.evalints.length == evalvars.length-100 <= evalints[i] <= 100Basic Calculator IV requires parsing and evaluating an algebraic expression that may contain variables, integers, addition, subtraction, multiplication, and parentheses. Instead of computing a single numeric result, the expression must be simplified into a canonical polynomial form.
A common approach is to treat each term as a polynomial represented by a HashMap where keys represent variable combinations (e.g., a*b) and values store coefficients. While parsing the string, use a stack-based expression evaluator or recursive descent parsing to handle parentheses and operator precedence. Addition and subtraction merge polynomial maps, while multiplication combines terms by concatenating variables and multiplying coefficients.
Variable substitutions can be handled using another map before or during evaluation. Finally, normalize the output by sorting terms first by degree and then lexicographically. This structured polynomial manipulation approach ensures correctness when simplifying complex expressions.
The overall time complexity depends on the number of generated terms during polynomial operations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Stack/Recursive Polynomial Parsing with Hash Maps | O(T log T) | O(T) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
One way is with a Polynomial class. For example, * `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`.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, problems involving expression parsing, symbolic computation, and stack-based evaluation are common in FAANG-style interviews. Basic Calculator IV tests strong skills in recursion, hash maps, and expression handling.
Hash maps are commonly used to store polynomial terms where keys represent variable combinations and values represent coefficients. Stacks or recursive parsing structures help evaluate expressions and manage parentheses.
The optimal approach is to represent expressions as polynomials using hash maps. During parsing, operations like addition, subtraction, and multiplication merge or combine polynomial terms while respecting operator precedence and parentheses.
The problem involves parsing algebraic expressions, handling operator precedence, and manipulating symbolic polynomials rather than simple numbers. Managing term combinations and maintaining sorted output adds additional complexity.