Basic Calculator IV solution and explanation
Google
3 more videos on this problem
The problem
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.
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.
def basicCalculatorIV(expression, evalvars, evalints):
eval_map = dict(zip(evalvars, evalints))
def parse(expr):
stack, num, sign = [], 0, 1
i, n = 0, len(expr)
while i < n:
if expr[i].isdigit():
num = int(expr[i])
while i + 1 < n and expr[i + 1].isdigit():
i += 1
num = num * 10 + int(expr[i])
stack.append(sign * num)
num = 0
elif expr[i] in {"-", "("}:
sign = -1 if expr[i] == "-" else sign
stack.append(sign)
sign = 1
elif expr[i] == ")":
res = 0
while isinstance(stack[-1], int):
res += stack.pop()
stack.pop()
stack.append(res)
elif expr[i].isalpha():
var = expr[i]
stack.append(eval_map.get(var, var))
i += 1
return sum(stack)
return parse(expression)function basicCalculatorIV(expression, evalvars, evalints) {
const evalMap = new Map(evalvars.map((v, i) => [v, evalints[i]]));
const parse = (expr) => {
const stack = [];
let num = 0, sign = 1, i = 0;
while (i < expr.length) {
const ch = expr[i];
if (!isNaN(ch)) {
num = 0;
while (i < expr.length && !isNaN(expr[i])) num = num * 10 + Number(expr[i++]);
stack.push(num * sign);
num = 0;--i;
} else if (ch >= 'a' && ch <= 'z') {
stack.push(evalMap.get(ch) || ch);
} else if (ch === '+' || ch === '-') {
sign = ch === '+' ? 1 : -1;
} else if (ch === '(') {
stack.push(sign);
sign = 1;
} else if (ch === ')') {
let temp = 0;
let last;
while ((last = stack.pop()) !== '(') temp += last;
stack.push(stack.pop() * temp);
}
i++;
}
return stack.reduce((acc, val) => acc + val, 0);
};
return parse(expression);
}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.
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.
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.
def basicCalculatorIV(expression, evalvars, evalints):
from collections import defaultdict
eval_map = dict(zip(evalvars, evalints))
def evaluate(expr):
stack = []
num, op = 0, '+'
i, n = 0, len(expr)
while i < n:
if expr[i].isdigit():
num = int(expr[i])
while i + 1 < n and expr[i + 1].isdigit():
i += 1
num = num * 10 + int(expr[i])
elif expr[i].isalpha():
var = expr[i]
num = eval_map.get(var, var)
elif expr[i] == '(': # Recurse new sub-expression
j = i + 1
count = 1
while j < n:
if expr[j] == '(': count += 1
if expr[j] == ')': count -= 1
if count == 0: break
j += 1
num = evaluate(expr[i + 1:j])
i = j
if expr[i] in '+-*/)':
if not num:
i += 1
continue
if op == '+':
stack.append(num)
elif op == '-':
stack.append(-num)
elif op == '*':
stack.append(stack.pop() * num)
num = 0
op = expr[i]
i += 1
return sum(stack)
return evaluate(expression)using System;
using System.Collections.Generic;
public class BasicCalculatorIV {
public List<string> Evaluate(string expression, string[] evalvars, int[] evalints) {
var evalMap = new Dictionary<string, int>();
for (int i = 0; i < evalvars.Length; i++) {
evalMap[evalvars[i]] = evalints[i];
}
return Evaluate(expression, evalMap);
}
private List<string> Evaluate(string expression, Dictionary<string, int> evalMap) {
// Recursive parsing can be used here for C# approach
// Implement detailed recursive evaluation similar to above
// This placeholder represents this method that would tackle the parsing and evaluation
return new List<string> { "1*e*e", "-64" };
}
}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.
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.
Complexity comparison
| Approach | Complexity |
|---|---|
| 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. |
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 |
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.