Watch 5 video solutions for Basic Calculator IV, a hard level problem involving Hash Table, Math, String. This walkthrough by Anish De has 495 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 100Problem Overview: You are given an algebraic expression containing integers, variables, addition, subtraction, multiplication, and parentheses. Some variables have known values. The goal is to evaluate the expression, substitute known variables, and return the simplified polynomial sorted by degree and lexicographic order.
Approach 1: Stack-Based Expression Evaluation (O(n * t log t) time, O(t) space)
This approach parses the expression from left to right and evaluates it using stacks for operands and operators. Each operand is represented as a polynomial map: {monomial -> coefficient}, where the monomial is a sorted tuple of variables. When encountering numbers or variables, you create a polynomial term; if the variable has a value in the evaluation map, substitute it immediately. Operators such as +, -, and * combine polynomial maps by merging coefficients or performing pairwise multiplication of terms. Parentheses push and pop evaluation contexts from the stack. After processing the full expression, remaining terms are sorted by degree and lexicographic order. This method mirrors how calculators process expressions while extending operands to polynomial structures.
Approach 2: Recursive Evaluation with Operator Precedence (O(n * t log t) time, O(t) space)
This method builds a recursive parser that respects operator precedence and parentheses. The expression is split into additive segments, while multiplication is handled within each segment. Each recursive call processes a substring and returns a polynomial map representing its value. Variables are either substituted using the provided values or kept symbolically. Polynomial addition merges coefficient maps, while multiplication creates new monomials by concatenating and sorting variables. Using recursion naturally handles nested parentheses and keeps the parsing logic clean. Internally the polynomial representation relies heavily on a hash table for fast coefficient aggregation and often uses recursion to manage nested expressions.
Recommended for interviews: The recursive precedence parser is usually preferred because it clearly separates parsing logic from polynomial operations and handles nested expressions cleanly. The stack-based evaluator still demonstrates strong understanding of expression parsing and data structures. Interviewers mainly care about how you represent polynomials, combine terms during multiplication, and maintain correct ordering in the final result.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Stack-Based Expression Evaluation | O(n * t log t) | O(t) | Good when implementing a calculator-style parser with explicit operator stacks |
| Recursive Evaluation with Operator Precedence | O(n * t log t) | O(t) | Preferred for clean handling of parentheses and precedence in symbolic expressions |