Basic Calculator IV - Video Solutions
Basic Calculator IV Leetcode Problem Intuition Discussion.
Basic Calculator IV - Video Solution
Watch 4 video solutions for Basic Calculator IV, a hard level problem involving Hash Table, Math, String. This walkthrough by Anish De has 519 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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"]
- An expression alternates chunks and symbols, with a space separating each chunk and symbol.
- A chunk is either an expression in parentheses, a variable, or a non-negative integer.
- A variable is a string of lowercase letters (not including digits.) Note that variables can be multiple letters, and note that variables never have a leading coefficient or unary operator like
"2x"or"-x".
Expressions are evaluated in the usual order: brackets first, then multiplication, then addition and subtraction.
- For example,
expression = "1 + 2 * 3"has an answer of["7"].
The format of the output is as follows:
- For each term of free variables with a non-zero coefficient, we write the free variables within a term in sorted order lexicographically.
- For example, we would never write a term like
"b*a*c", only"a*b*c".
- For example, we would never write a term like
- Terms have degrees equal to the number of free variables being multiplied, counting multiplicity. We write the largest degree terms of our answer first, breaking ties by lexicographic order ignoring the leading coefficient of the term.
- For example,
"a*a*b*c"has degree4.
- For example,
- The leading coefficient of the term is placed directly to the left with an asterisk separating it from the variables (if they exist.) A leading coefficient of 1 is still printed.
- An example of a well-formatted answer is
["-2*a*a*a", "3*a*a*b", "3*b*b", "4*a", "5*c", "-6"]. - Terms (including constant terms) with coefficient
0are not included.- For example, an expression of
"0"has an output of[].
- For example, an expression 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 <= 250expressionconsists of lowercase English letters, digits,'+','-','*','(',')',' '.expressiondoes not contain any leading or trailing spaces.- All the tokens in
expressionare 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] <= 100
Approach Overview
Problem 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.
Complexity Analysis
| 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 |