Basic Calculator IV
Basic Calculator IV is a hard stack problem solved with the stack basics pattern.
The best approach, optimal (recursive descent over merged polynomials), runs in O(M² · L) per multiplication time and O(M · L) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (expand without merging) up.
Problem
You are given an arithmetic expression built from non-negative integers, lowercase variable names, +, -, * and parentheses, with a single space between tokens (parentheses may sit right next to what they enclose). You also get two parallel lists: evalvars[i] has the known value evalints[i]. Every other variable stays symbolic.
Simplify the expression into a polynomial and return its terms as strings. A term is written as its coefficient followed by its variables, each prefixed by *, with the variables in each term sorted alphabetically (for example "-3*a*a*c"); the constant term is just the number (for example "12").
Order the terms by degree (number of variables, counted with repetition) from highest to lowest, and break ties by comparing the variable lists lexicographically. Leave out every term whose coefficient is 0; if nothing is left, return an empty list. * binds tighter than + and -, which are evaluated left to right.
Examples
Example 1
- Input
expression = "x * 3 + y - x", evalvars = ["y"], evalints = [4]- Output
["2*x", "4"]- Why
- y becomes 4, and 3x - x simplifies to 2x. The degree-1 term comes before the constant.
Example 2
- Input
expression = "(p + 2) * (p - q)", evalvars = [], evalints = []- Output
["1*p*p", "-1*p*q", "2*p", "-2*q"]- Why
- Expanding gives pp - pq + 2p - 2q. Degree-2 terms come first, ties broken by the variable list.
Example 3
- Input
expression = "k - k + 7 * 0", evalvars = [], evalints = []- Output
[]- Why
- Everything cancels to 0, and zero terms are never printed.
Constraints
1 <= expression.length <= 250expressioncontains lowercase letters, digits,+,-,*,(,)and single spaces between tokens.- There is no unary minus, and the expression is always valid.
0 <= evalvars.length <= 100,evalvars.length == evalints.length1 <= evalvars[i].length <= 20,-100 <= evalints[i] <= 100- Every coefficient met while simplifying fits in a 32-bit signed integer.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 16 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (expand without merging) | O(2^n) in the worst case | O(2^n) |
| Optimal (recursive descent over merged polynomials) | O(M² · L) per multiplication | O(M · L) |
1Brute force (expand without merging)
O(2^n) in the worst caseWithout merging, each product of two sums multiplies the number of stored terms, e.g. `(a + a) * (a + a) * ...`.O(2^n)All unmerged terms are kept until the end.Parse with the usual precedence rules, but keep every product term as its own entry in a list. Like terms are only merged once, at the very end. This is easy to reason about, but repeated products of sums make the list grow exponentially.
- Split the string into tokens: numbers, variable names, operators and parentheses.
- A factor becomes a one-term list: a constant, a substituted known variable, or (variable, coefficient 1).
*builds the cross product of two lists, concatenating and sorting the variable names of each pair.+/-appends the right-hand list (negated for-).- At the end, sum coefficients per variable list, drop zeros, sort by degree (descending) then by variable list, and format.
class Solution {
static class Term {
long coef;
String key;
Term(long coef, String key) { this.coef = coef; this.key = key; }
}
private List<String> tokens;
private int pos;
private Map<String, Integer> env;
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
env = new HashMap<>();
for (int i = 0; i < evalvars.length; i++) env.put(evalvars[i], evalints[i]);
tokens = new ArrayList<>();
int i = 0, n = expression.length();
while (i < n) {
char c = expression.charAt(i);
if (c == ' ') { i++; continue; }
if (Character.isLetterOrDigit(c)) {
int j = i;
while (j < n && Character.isLetterOrDigit(expression.charAt(j))) j++;
tokens.add(expression.substring(i, j));
i = j;
} else {
tokens.add(String.valueOf(c));
i++;
}
}
pos = 0;
Map<String, Long> poly = new HashMap<>();
for (Term t : parseExpr()) poly.merge(t.key, t.coef, Long::sum);
List<String> keys = new ArrayList<>();
for (Map.Entry<String, Long> e : poly.entrySet()) if (e.getValue() != 0) keys.add(e.getKey());
keys.sort((a, b) -> degree(a) != degree(b) ? degree(b) - degree(a) : a.compareTo(b));
List<String> out = new ArrayList<>();
for (String k : keys) out.add(k.isEmpty() ? String.valueOf(poly.get(k)) : poly.get(k) + "*" + k);
return out;
}
private int degree(String key) {
if (key.isEmpty()) return 0;
int d = 1;
for (char c : key.toCharArray()) if (c == '*') d++;
return d;
}
private List<Term> parseExpr() {
List<Term> res = parseTerm();
while (pos < tokens.size() && (tokens.get(pos).equals("+") || tokens.get(pos).equals("-"))) {
long sign = tokens.get(pos).equals("+") ? 1 : -1;
pos++;
for (Term t : parseTerm()) res.add(new Term(sign * t.coef, t.key));
}
return res;
}
private List<Term> parseTerm() {
List<Term> res = parseFactor();
while (pos < tokens.size() && tokens.get(pos).equals("*")) {
pos++;
List<Term> rhs = parseFactor();
List<Term> prod = new ArrayList<>();
for (Term x : res) {
for (Term y : rhs) prod.add(new Term(x.coef * y.coef, combine(x.key, y.key)));
}
res = prod;
}
return res;
}
private List<Term> parseFactor() {
String t = tokens.get(pos++);
List<Term> res = new ArrayList<>();
if (t.equals("(")) {
res = parseExpr();
pos++; // skip ')'
} else if (Character.isDigit(t.charAt(0))) {
res.add(new Term(Long.parseLong(t), ""));
} else if (env.containsKey(t)) {
res.add(new Term(env.get(t), ""));
} else {
res.add(new Term(1, t));
}
return res;
}
private String combine(String a, String b) {
List<String> vars = new ArrayList<>();
if (!a.isEmpty()) vars.addAll(Arrays.asList(a.split("\\*")));
if (!b.isEmpty()) vars.addAll(Arrays.asList(b.split("\\*")));
Collections.sort(vars);
return String.join("*", vars);
}
}class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
self.env = dict(zip(evalvars, evalints))
tokens = []
i, n = 0, len(expression)
while i < n:
c = expression[i]
if c == " ":
i += 1
elif c.isalnum():
j = i
while j < n and expression[j].isalnum():
j += 1
tokens.append(expression[i:j])
i = j
else:
tokens.append(c)
i += 1
self.tokens, self.pos = tokens, 0
poly = {}
for coef, key in self.parse_expr():
poly[key] = poly.get(key, 0) + coef
keys = [k for k, v in poly.items() if v != 0]
keys.sort(key=lambda k: (-self.degree(k), k))
return [str(poly[k]) if k == "" else f"{poly[k]}*{k}" for k in keys]
def degree(self, key: str) -> int:
return 0 if key == "" else key.count("*") + 1
def combine(self, a: str, b: str) -> str:
parts = (a.split("*") if a else []) + (b.split("*") if b else [])
return "*".join(sorted(parts))
def parse_expr(self) -> list:
res = self.parse_term()
while self.pos < len(self.tokens) and self.tokens[self.pos] in ("+", "-"):
sign = 1 if self.tokens[self.pos] == "+" else -1
self.pos += 1
for coef, key in self.parse_term():
res.append((sign * coef, key))
return res
def parse_term(self) -> list:
res = self.parse_factor()
while self.pos < len(self.tokens) and self.tokens[self.pos] == "*":
self.pos += 1
rhs = self.parse_factor()
res = [(c1 * c2, self.combine(k1, k2)) for c1, k1 in res for c2, k2 in rhs]
return res
def parse_factor(self) -> list:
t = self.tokens[self.pos]
self.pos += 1
if t == "(":
res = self.parse_expr()
self.pos += 1 # skip ')'
return res
if t[0].isdigit():
return [(int(t), "")]
if t in self.env:
return [(self.env[t], "")]
return [(1, t)]class Solution {
vector<string> tokens;
int pos = 0;
unordered_map<string, long long> env;
static int degree(const string& key) {
if (key.empty()) return 0;
int d = 1;
for (char c : key) if (c == '*') d++;
return d;
}
static vector<string> split(const string& key) {
vector<string> parts;
if (key.empty()) return parts;
string cur;
for (char c : key) {
if (c == '*') { parts.push_back(cur); cur.clear(); }
else cur += c;
}
parts.push_back(cur);
return parts;
}
static string combine(const string& a, const string& b) {
vector<string> vars = split(a), vb = split(b);
vars.insert(vars.end(), vb.begin(), vb.end());
sort(vars.begin(), vars.end());
string key;
for (size_t i = 0; i < vars.size(); i++) {
if (i) key += '*';
key += vars[i];
}
return key;
}
vector<pair<long long, string>> parseExpr() {
auto res = parseTerm();
while (pos < (int)tokens.size() && (tokens[pos] == "+" || tokens[pos] == "-")) {
long long sign = tokens[pos] == "+" ? 1 : -1;
pos++;
for (auto& t : parseTerm()) res.push_back({sign * t.first, t.second});
}
return res;
}
vector<pair<long long, string>> parseTerm() {
auto res = parseFactor();
while (pos < (int)tokens.size() && tokens[pos] == "*") {
pos++;
auto rhs = parseFactor();
vector<pair<long long, string>> prod;
for (auto& x : res)
for (auto& y : rhs) prod.push_back({x.first * y.first, combine(x.second, y.second)});
res = prod;
}
return res;
}
vector<pair<long long, string>> parseFactor() {
string t = tokens[pos++];
if (t == "(") {
auto res = parseExpr();
pos++; // skip ')'
return res;
}
if (isdigit((unsigned char)t[0])) return {{stoll(t), ""}};
if (env.count(t)) return {{env[t], ""}};
return {{1, t}};
}
public:
vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
for (size_t i = 0; i < evalvars.size(); i++) env[evalvars[i]] = evalints[i];
int i = 0, n = expression.size();
while (i < n) {
char c = expression[i];
if (c == ' ') { i++; continue; }
if (isalnum((unsigned char)c)) {
int j = i;
while (j < n && isalnum((unsigned char)expression[j])) j++;
tokens.push_back(expression.substr(i, j - i));
i = j;
} else {
tokens.push_back(string(1, c));
i++;
}
}
unordered_map<string, long long> poly;
for (auto& t : parseExpr()) poly[t.second] += t.first;
vector<string> keys;
for (auto& e : poly) if (e.second != 0) keys.push_back(e.first);
sort(keys.begin(), keys.end(), [](const string& a, const string& b) {
int da = degree(a), db = degree(b);
if (da != db) return da > db;
return a < b;
});
vector<string> out;
for (auto& k : keys) out.push_back(k.empty() ? to_string(poly[k]) : to_string(poly[k]) + "*" + k);
return out;
}
};function basicCalculatorIV(expression, evalvars, evalints) {
const env = new Map();
for (let i = 0; i < evalvars.length; i++) env.set(evalvars[i], evalints[i]);
const tokens = [];
const isAlnum = (c) => /[a-z0-9]/.test(c);
let i = 0;
const n = expression.length;
while (i < n) {
const c = expression[i];
if (c === ' ') { i++; continue; }
if (isAlnum(c)) {
let j = i;
while (j < n && isAlnum(expression[j])) j++;
tokens.push(expression.slice(i, j));
i = j;
} else {
tokens.push(c);
i++;
}
}
let pos = 0;
const degree = (key) => (key === '' ? 0 : key.split('*').length);
const combine = (a, b) => {
const vars = [...(a ? a.split('*') : []), ...(b ? b.split('*') : [])];
vars.sort();
return vars.join('*');
};
function parseExpr() {
const res = parseTerm();
while (pos < tokens.length && (tokens[pos] === '+' || tokens[pos] === '-')) {
const sign = tokens[pos] === '+' ? 1 : -1;
pos++;
for (const [coef, key] of parseTerm()) res.push([sign * coef, key]);
}
return res;
}
function parseTerm() {
let res = parseFactor();
while (pos < tokens.length && tokens[pos] === '*') {
pos++;
const rhs = parseFactor();
const prod = [];
for (const [c1, k1] of res) {
for (const [c2, k2] of rhs) prod.push([c1 * c2, combine(k1, k2)]);
}
res = prod;
}
return res;
}
function parseFactor() {
const t = tokens[pos++];
if (t === '(') {
const res = parseExpr();
pos++; // skip ')'
return res;
}
if (/[0-9]/.test(t[0])) return [[Number(t), '']];
if (env.has(t)) return [[env.get(t), '']];
return [[1, t]];
}
const poly = new Map();
for (const [coef, key] of parseExpr()) poly.set(key, (poly.get(key) || 0) + coef);
const keys = [...poly.keys()].filter((k) => poly.get(k) !== 0);
keys.sort((a, b) => degree(b) - degree(a) || (a < b ? -1 : a > b ? 1 : 0));
return keys.map((k) => (k === '' ? String(poly.get(k)) : poly.get(k) + '*' + k));
}2Optimal (recursive descent over merged polynomials)
O(M² · L) per multiplicationM is the number of distinct monomials in the two operands and L the cost of merging and sorting a key; merging keeps M small.O(M · L)Each polynomial stores at most M keys of length up to L.Same parser, but every sub-result is a polynomial map from a variable key (the sorted variable names joined by *, empty for the constant) to its coefficient. Like terms merge as soon as they appear, so the size of any intermediate result is bounded by the number of distinct monomials, not by the number of expansions.
- Tokenize, and put the known variables into a map from name to value.
- parseExpr: read a term, then while the next token is
+or-, read another term and add (or subtract) its coefficients key by key. - parseTerm: read a factor, then while the next token is
*, multiply by the next factor: every pair of keys is combined into a sorted key and their coefficients multiply and accumulate. - parseFactor:
(starts a nested expression; a number or known variable is a constant; an unknown variable is the keynamewith coefficient 1. - Drop zero coefficients, sort keys by degree (descending) then lexicographically by variable list, and print
coef*key(justcoeffor the constant).
class Solution {
private List<String> tokens;
private int pos;
private Map<String, Integer> env;
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
env = new HashMap<>();
for (int i = 0; i < evalvars.length; i++) env.put(evalvars[i], evalints[i]);
tokens = new ArrayList<>();
int i = 0, n = expression.length();
while (i < n) {
char c = expression.charAt(i);
if (c == ' ') { i++; continue; }
if (Character.isLetterOrDigit(c)) {
int j = i;
while (j < n && Character.isLetterOrDigit(expression.charAt(j))) j++;
tokens.add(expression.substring(i, j));
i = j;
} else {
tokens.add(String.valueOf(c));
i++;
}
}
pos = 0;
Map<String, Long> poly = parseExpr();
List<String> keys = new ArrayList<>();
for (Map.Entry<String, Long> e : poly.entrySet()) if (e.getValue() != 0) keys.add(e.getKey());
keys.sort((a, b) -> degree(a) != degree(b) ? degree(b) - degree(a) : a.compareTo(b));
List<String> out = new ArrayList<>();
for (String k : keys) out.add(k.isEmpty() ? String.valueOf(poly.get(k)) : poly.get(k) + "*" + k);
return out;
}
private int degree(String key) {
if (key.isEmpty()) return 0;
int d = 1;
for (char c : key.toCharArray()) if (c == '*') d++;
return d;
}
private Map<String, Long> parseExpr() {
Map<String, Long> res = parseTerm();
while (pos < tokens.size() && (tokens.get(pos).equals("+") || tokens.get(pos).equals("-"))) {
long sign = tokens.get(pos).equals("+") ? 1 : -1;
pos++;
for (Map.Entry<String, Long> e : parseTerm().entrySet()) {
res.merge(e.getKey(), sign * e.getValue(), Long::sum);
}
}
return res;
}
private Map<String, Long> parseTerm() {
Map<String, Long> res = parseFactor();
while (pos < tokens.size() && tokens.get(pos).equals("*")) {
pos++;
Map<String, Long> rhs = parseFactor();
Map<String, Long> prod = new HashMap<>();
for (Map.Entry<String, Long> x : res.entrySet()) {
for (Map.Entry<String, Long> y : rhs.entrySet()) {
prod.merge(combine(x.getKey(), y.getKey()), x.getValue() * y.getValue(), Long::sum);
}
}
res = prod;
}
return res;
}
private Map<String, Long> parseFactor() {
String t = tokens.get(pos++);
Map<String, Long> res = new HashMap<>();
if (t.equals("(")) {
res = parseExpr();
pos++; // skip ')'
} else if (Character.isDigit(t.charAt(0))) {
res.put("", Long.parseLong(t));
} else if (env.containsKey(t)) {
res.put("", (long) env.get(t));
} else {
res.put(t, 1L);
}
return res;
}
private String combine(String a, String b) {
List<String> vars = new ArrayList<>();
if (!a.isEmpty()) vars.addAll(Arrays.asList(a.split("\\*")));
if (!b.isEmpty()) vars.addAll(Arrays.asList(b.split("\\*")));
Collections.sort(vars);
return String.join("*", vars);
}
}class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
self.env = dict(zip(evalvars, evalints))
tokens = []
i, n = 0, len(expression)
while i < n:
c = expression[i]
if c == " ":
i += 1
elif c.isalnum():
j = i
while j < n and expression[j].isalnum():
j += 1
tokens.append(expression[i:j])
i = j
else:
tokens.append(c)
i += 1
self.tokens, self.pos = tokens, 0
poly = self.parse_expr()
keys = [k for k, v in poly.items() if v != 0]
keys.sort(key=lambda k: (-self.degree(k), k))
return [str(poly[k]) if k == "" else f"{poly[k]}*{k}" for k in keys]
def degree(self, key: str) -> int:
return 0 if key == "" else key.count("*") + 1
def combine(self, a: str, b: str) -> str:
parts = (a.split("*") if a else []) + (b.split("*") if b else [])
return "*".join(sorted(parts))
def parse_expr(self) -> dict:
res = self.parse_term()
while self.pos < len(self.tokens) and self.tokens[self.pos] in ("+", "-"):
sign = 1 if self.tokens[self.pos] == "+" else -1
self.pos += 1
for key, coef in self.parse_term().items():
res[key] = res.get(key, 0) + sign * coef
return res
def parse_term(self) -> dict:
res = self.parse_factor()
while self.pos < len(self.tokens) and self.tokens[self.pos] == "*":
self.pos += 1
rhs = self.parse_factor()
prod = {}
for k1, c1 in res.items():
for k2, c2 in rhs.items():
key = self.combine(k1, k2)
prod[key] = prod.get(key, 0) + c1 * c2
res = prod
return res
def parse_factor(self) -> dict:
t = self.tokens[self.pos]
self.pos += 1
if t == "(":
res = self.parse_expr()
self.pos += 1 # skip ')'
return res
if t[0].isdigit():
return {"": int(t)}
if t in self.env:
return {"": self.env[t]}
return {t: 1}class Solution {
typedef unordered_map<string, long long> Poly;
vector<string> tokens;
int pos = 0;
unordered_map<string, long long> env;
static int degree(const string& key) {
if (key.empty()) return 0;
int d = 1;
for (char c : key) if (c == '*') d++;
return d;
}
static vector<string> split(const string& key) {
vector<string> parts;
if (key.empty()) return parts;
string cur;
for (char c : key) {
if (c == '*') { parts.push_back(cur); cur.clear(); }
else cur += c;
}
parts.push_back(cur);
return parts;
}
static string combine(const string& a, const string& b) {
vector<string> vars = split(a), vb = split(b);
vars.insert(vars.end(), vb.begin(), vb.end());
sort(vars.begin(), vars.end());
string key;
for (size_t i = 0; i < vars.size(); i++) {
if (i) key += '*';
key += vars[i];
}
return key;
}
Poly parseExpr() {
Poly res = parseTerm();
while (pos < (int)tokens.size() && (tokens[pos] == "+" || tokens[pos] == "-")) {
long long sign = tokens[pos] == "+" ? 1 : -1;
pos++;
for (auto& e : parseTerm()) res[e.first] += sign * e.second;
}
return res;
}
Poly parseTerm() {
Poly res = parseFactor();
while (pos < (int)tokens.size() && tokens[pos] == "*") {
pos++;
Poly rhs = parseFactor();
Poly prod;
for (auto& x : res)
for (auto& y : rhs) prod[combine(x.first, y.first)] += x.second * y.second;
res = prod;
}
return res;
}
Poly parseFactor() {
string t = tokens[pos++];
if (t == "(") {
Poly res = parseExpr();
pos++; // skip ')'
return res;
}
Poly res;
if (isdigit((unsigned char)t[0])) res[""] = stoll(t);
else if (env.count(t)) res[""] = env[t];
else res[t] = 1;
return res;
}
public:
vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
for (size_t i = 0; i < evalvars.size(); i++) env[evalvars[i]] = evalints[i];
int i = 0, n = expression.size();
while (i < n) {
char c = expression[i];
if (c == ' ') { i++; continue; }
if (isalnum((unsigned char)c)) {
int j = i;
while (j < n && isalnum((unsigned char)expression[j])) j++;
tokens.push_back(expression.substr(i, j - i));
i = j;
} else {
tokens.push_back(string(1, c));
i++;
}
}
Poly poly = parseExpr();
vector<string> keys;
for (auto& e : poly) if (e.second != 0) keys.push_back(e.first);
sort(keys.begin(), keys.end(), [](const string& a, const string& b) {
int da = degree(a), db = degree(b);
if (da != db) return da > db;
return a < b;
});
vector<string> out;
for (auto& k : keys) out.push_back(k.empty() ? to_string(poly[k]) : to_string(poly[k]) + "*" + k);
return out;
}
};function basicCalculatorIV(expression, evalvars, evalints) {
const env = new Map();
for (let i = 0; i < evalvars.length; i++) env.set(evalvars[i], evalints[i]);
const tokens = [];
const isAlnum = (c) => /[a-z0-9]/.test(c);
let i = 0;
const n = expression.length;
while (i < n) {
const c = expression[i];
if (c === ' ') { i++; continue; }
if (isAlnum(c)) {
let j = i;
while (j < n && isAlnum(expression[j])) j++;
tokens.push(expression.slice(i, j));
i = j;
} else {
tokens.push(c);
i++;
}
}
let pos = 0;
const degree = (key) => (key === '' ? 0 : key.split('*').length);
const combine = (a, b) => {
const vars = [...(a ? a.split('*') : []), ...(b ? b.split('*') : [])];
vars.sort();
return vars.join('*');
};
const add = (poly, key, coef) => poly.set(key, (poly.get(key) || 0) + coef);
function parseExpr() {
const res = parseTerm();
while (pos < tokens.length && (tokens[pos] === '+' || tokens[pos] === '-')) {
const sign = tokens[pos] === '+' ? 1 : -1;
pos++;
for (const [key, coef] of parseTerm()) add(res, key, sign * coef);
}
return res;
}
function parseTerm() {
let res = parseFactor();
while (pos < tokens.length && tokens[pos] === '*') {
pos++;
const rhs = parseFactor();
const prod = new Map();
for (const [k1, c1] of res) {
for (const [k2, c2] of rhs) add(prod, combine(k1, k2), c1 * c2);
}
res = prod;
}
return res;
}
function parseFactor() {
const t = tokens[pos++];
if (t === '(') {
const res = parseExpr();
pos++; // skip ')'
return res;
}
if (/[0-9]/.test(t[0])) return new Map([['', Number(t)]]);
if (env.has(t)) return new Map([['', env.get(t)]]);
return new Map([[t, 1]]);
}
const poly = parseExpr();
const keys = [...poly.keys()].filter((k) => poly.get(k) !== 0);
keys.sort((a, b) => degree(b) - degree(a) || (a < b ? -1 : a > b ? 1 : 0));
return keys.map((k) => (k === '' ? String(poly.get(k)) : poly.get(k) + '*' + k));
}Edge cases to test
- All terms cancel, so the answer is an empty list
- A variable is used with itself (
a * a), so a variable repeats inside one term - Variables with names that are prefixes of each other, like
aandab - A known variable inside parentheses next to unknown ones
- Nested parentheses and a multiplication that binds tighter than
-
Hints
Hint 1
Represent every sub-expression as a polynomial: a map from a sorted list of variable names (the empty list for the constant) to a coefficient.
Hint 2
Adding polynomials adds coefficients key by key; multiplying pairs every term of one with every term of the other and merges the variable lists.
Hint 3
Parse with precedence: an expression is terms joined by +/-, a term is factors joined by *, and a factor is a number, a variable or a parenthesised expression.
FAQ
What is the best time complexity for Basic Calculator IV?
Optimal (recursive descent over merged polynomials) runs in O(M² · L) per multiplication time and O(M · L) extra space. M is the number of distinct monomials in the two operands and L the cost of merging and sorting a key; merging keeps M small.
Which pattern does Basic Calculator IV use?
It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.
Is there a brute force solution for Basic Calculator IV?
Yes. Brute force (expand without merging) takes O(2^n) in the worst case time and O(2^n) space. Parse with the usual precedence rules, but keep every product term as its own entry in a list.
Which edge cases should I test for Basic Calculator IV?
All terms cancel, so the answer is an empty list; A variable is used with itself (a a), so a variable repeats inside one term; Variables with names that are prefixes of each other, like a and ab; A known variable inside parentheses next to unknown ones; Nested parentheses and a multiplication that binds tighter than -.