Skip to main content
Talentd

Basic Calculator IV - Solution & Explanation

HardHash TableMathStringStack8 min readAsked at: Intuit, Roblox, Google
Practice this problem

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".
  • 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 degree 4.
  • 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 0 are not included.
    • For example, an expression of "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 <= 250
  • expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.
  • expression does not contain any leading or trailing spaces.
  • All the tokens in expression are separated by a single space.
  • 0 <= evalvars.length <= 100
  • 1 <= evalvars[i].length <= 20
  • evalvars[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.

Approach 1: Stack-Based Expression Evaluation

This approach uses a stack for handling tokens in the expression and evaluates them based on operator precedence and the values from the evaluation map.

The solution involves a stack data structure to parse and process the expression. It first builds an evaluation map for easy look-up of variable values. The main function parse goes through each character of expression, handling numbers, variables, and operators, maintaining the current total in the stack. Parentheses are handled using recursion, and the final result returned is built by summing up the stack's contents.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n), where n is the length of the expression, as we process each character at most a few times due to stack operations.

Space Complexity: O(n), owing to the stack used for parsing nested expressions.

Try this approach in the editor →

Approach 2: Recursive Evaluation with Operator Precedence

This solution recursively parses and evaluates expressions according to the priority of operators. It evaluates elements within parentheses first and processes operations by precedence level.

This implementation recursively evaluates parts of the expression within parentheses, adhering to operator precedence. It utilizes a stack for handling addition/subtraction and directly processes multiplication. Similar variable evaluation as in previous solutions applies here, with recursion used for handling '(' and ')' correctly.

Code

PythonC#

Python

C#

Complexity

Time Complexity: O(n), where n is the length of the input expression considering the recursive evaluation process simplifies multiple sub-expressions.

Space Complexity: O(n) due to recursion and stack usage for sub-expressions.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Stack-Based Expression Evaluation

Time Complexity: O(n), where n is the length of the expression, as we process each character at most a few times due to stack operations.

Space Complexity: O(n), owing to the stack used for parsing nested expressions.

Recursive Evaluation with Operator Precedence

Time Complexity: O(n), where n is the length of the input expression considering the recursive evaluation process simplifies multiple sub-expressions.

Space Complexity: O(n) due to recursion and stack usage for sub-expressions.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Stack-Based Expression EvaluationO(n * t log t)O(t)Good when implementing a calculator-style parser with explicit operator stacks
Recursive Evaluation with Operator PrecedenceO(n * t log t)O(t)Preferred for clean handling of parentheses and precedence in symbolic expressions

Video Solution

Basic Calculator IV Leetcode Problem Intuition Discussion. • Anish De • 519 views views

Watch 3 more video solutions →

Frequently Asked Questions

Is Basic Calculator IV easy or hard?
Basic Calculator IV is categorized as a Hard problem because it combines expression parsing, symbolic algebra, and careful polynomial representation. Handling operator precedence, variable substitution, and term ordering makes the implementation significantly more complex than earlier calculator problems.
Basic Calculator IV Python/Java solution
Typical implementations use dictionaries or hash maps to represent polynomials and helper functions to add or multiply them. Python solutions commonly use tuples as monomial keys, while Java implementations use maps with lists of variables as canonical keys.
How to solve Basic Calculator IV in O(n)?
A strict O(n) solution is not practical because polynomial multiplication may generate many terms that must be merged and sorted. Efficient solutions aim to minimize intermediate terms using hash maps for aggregation and only sort the final list of monomials.
What is the best approach for Basic Calculator IV?
The most common solution represents expressions as polynomial maps where each monomial maps to a coefficient. A recursive parser or stack-based evaluator processes operators and parentheses while merging polynomial terms. This approach correctly handles symbolic variables, substitution, and multiplication expansion.
Is Basic Calculator IV asked at Google/Amazon/Meta?
Symbolic expression parsing and calculator-style evaluation problems appear in interviews at companies like Google and Meta. While this exact problem is rare, variations involving expression parsing, stacks, recursion, and polynomial evaluation are common in senior-level interviews.
What data structure is used in Basic Calculator IV?
The core structure is a hash map that stores polynomial terms as monomials mapped to coefficients. Stacks or recursive call stacks manage expression parsing, while arrays or tuples store variables in each monomial for sorting and comparison.
What is the time complexity of Basic Calculator IV?
Time complexity is typically O(n * t log t), where n is the expression length and t is the number of generated polynomial terms. Multiplication can combine multiple monomials, which increases term count and requires sorting for the final output.

Ready to solve this problem?

Practice Basic Calculator IV with our built-in code editor and test cases.

Practice on FleetCode
Previous

Basic Calculator III

Next

Parse Lisp Expression