Basic Calculator IV
Problem
Parse an algebraic expression with +, -, *, parentheses, integers, and variables. Given evaluation values for some variables, return the simplified polynomial as a sorted list of terms.
Input
expr='e + 8 - a + 5', evalvars=['e'], evalints=[1]Output
['-1*a','14']Substituting e=1 yields -a + 14.
def basicCalculatorIV(expression, evalvars, evalints):
val = dict(zip(evalvars, evalints))
def tokenize(s):
toks, i = [], 0
while i < len(s):
if s[i] == ' ': i += 1
elif s[i] in '()+-*':
toks.append(s[i]); i += 1
else:
j = i
while j < len(s) and s[j] not in ' ()+-*': j += 1
toks.append(s[i:j]); i = j
return toks
def atom(t):
if t.lstrip('-').isdigit(): return {(): int(t)}
return {(): val[t]} if t in val else {(t,): 1}
def mul(a, b):
out = {}
for k1, v1 in a.items():
for k2, v2 in b.items():
k = tuple(sorted(k1+k2))
out[k] = out.get(k, 0) + v1*v2
return out
def add(a, b, sign=1):
out = dict(a)
for k, v in b.items():
out[k] = out.get(k, 0) + sign*v
return out
toks = tokenize(expression)
# Shunting-yard to RPN then evaluate
prec = {'+':1,'-':1,'*':2}
out_q, ops = [], []
for t in toks:
if t == '(': ops.append(t)
elif t == ')':
while ops and ops[-1] != '(': out_q.append(ops.pop())
ops.pop()
elif t in prec:
while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[t]:
out_q.append(ops.pop())
ops.append(t)
else:
out_q.append(t)
while ops: out_q.append(ops.pop())
st = []
for t in out_q:
if t in prec:
b, a = st.pop(), st.pop()
if t == '+': st.append(add(a, b))
elif t == '-': st.append(add(a, b, -1))
else: st.append(mul(a, b))
else:
st.append(atom(t))
poly = st[0]
terms = sorted([(k, v) for k, v in poly.items() if v != 0], key=lambda x: (-len(x[0]), x[0]))
return [(str(v) if not k else f"{v}*" + "*".join(k)) for k, v in terms]function basicCalculatorIV(expression, evalvars, evalints) {
const val = Object.fromEntries(evalvars.map((v, i) => [v, evalints[i]]));
const tokenize = (s) => {
const toks = [];
let i = 0;
while (i < s.length) {
if (s[i] === ' ') { i++; }
else if ('()+-*'.includes(s[i])) { toks.push(s[i]); i++; }
else {
let j = i;
while (j < s.length && !' ()+-*'.includes(s[j])) j++;
toks.push(s.slice(i, j)); i = j;
}
}
return toks;
};
const key = (arr) => arr.length ? arr.join(',') : '';
const atom = (t) => {
if (/^-?\d+$/.test(t)) return { '': parseInt(t, 10) };
if (t in val) return { '': val[t] };
return { [t]: 1 };
};
const mul = (a, b) => {
const out = {};
for (const k1 in a) for (const k2 in b) {
const arr = (k1 ? k1.split(',') : []).concat(k2 ? k2.split(',') : []).sort();
const k = key(arr);
out[k] = (out[k] || 0) + a[k1] * b[k2];
}
return out;
};
const add = (a, b, sign) => {
const out = Object.assign({}, a);
for (const k in b) out[k] = (out[k] || 0) + sign * b[k];
return out;
};
const toks = tokenize(expression);
const prec = { '+': 1, '-': 1, '*': 2 };
const outQ = [], ops = [];
for (const t of toks) {
if (t === '(') ops.push(t);
else if (t === ')') {
while (ops.length && ops[ops.length - 1] !== '(') outQ.push(ops.pop());
ops.pop();
} else if (t in prec) {
while (ops.length && ops[ops.length - 1] !== '(' && prec[ops[ops.length - 1]] >= prec[t]) outQ.push(ops.pop());
ops.push(t);
} else outQ.push(t);
}
while (ops.length) outQ.push(ops.pop());
const st = [];
for (const t of outQ) {
if (t in prec) {
const b = st.pop(), a = st.pop();
if (t === '+') st.push(add(a, b, 1));
else if (t === '-') st.push(add(a, b, -1));
else st.push(mul(a, b));
} else st.push(atom(t));
}
const poly = st[0];
const terms = Object.entries(poly).filter(([, v]) => v !== 0).sort((x, y) => {
const lx = x[0] ? x[0].split(',').length : 0;
const ly = y[0] ? y[0].split(',').length : 0;
if (lx !== ly) return ly - lx;
return x[0] < y[0] ? -1 : 1;
});
return terms.map(([k, v]) => k === '' ? String(v) : v + '*' + k.replace(/,/g, '*'));
}class Solution {
private Map<String, Integer> val = new HashMap<>();
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
for (int i = 0; i < evalvars.length; i++) val.put(evalvars[i], evalints[i]);
List<String> toks = tokenize(expression);
Map<Character, Integer> prec = Map.of('+', 1, '-', 1, '*', 2);
Deque<String> outQ = new ArrayDeque<>();
Deque<String> ops = new ArrayDeque<>();
List<String> rpn = new ArrayList<>();
for (String t : toks) {
if (t.equals("(")) ops.push(t);
else if (t.equals(")")) {
while (!ops.isEmpty() && !ops.peek().equals("(")) rpn.add(ops.pop());
ops.pop();
} else if (t.length() == 1 && prec.containsKey(t.charAt(0))) {
while (!ops.isEmpty() && !ops.peek().equals("(")
&& prec.get(ops.peek().charAt(0)) >= prec.get(t.charAt(0)))
rpn.add(ops.pop());
ops.push(t);
} else rpn.add(t);
}
while (!ops.isEmpty()) rpn.add(ops.pop());
Deque<Map<String, Integer>> st = new ArrayDeque<>();
for (String t : rpn) {
if (t.length() == 1 && prec.containsKey(t.charAt(0))) {
Map<String, Integer> b = st.pop(), a = st.pop();
if (t.equals("+")) st.push(add(a, b, 1));
else if (t.equals("-")) st.push(add(a, b, -1));
else st.push(mul(a, b));
} else st.push(atom(t));
}
Map<String, Integer> poly = st.peek();
List<Map.Entry<String, Integer>> terms = new ArrayList<>();
for (Map.Entry<String, Integer> e : poly.entrySet())
if (e.getValue() != 0) terms.add(e);
terms.sort((x, y) -> {
int lx = x.getKey().isEmpty() ? 0 : x.getKey().split(",").length;
int ly = y.getKey().isEmpty() ? 0 : y.getKey().split(",").length;
if (lx != ly) return ly - lx;
return x.getKey().compareTo(y.getKey());
});
List<String> res = new ArrayList<>();
for (Map.Entry<String, Integer> e : terms)
res.add(e.getKey().isEmpty() ? String.valueOf(e.getValue())
: e.getValue() + "*" + e.getKey().replace(",", "*"));
return res;
}
private List<String> tokenize(String s) {
List<String> toks = new ArrayList<>();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (c == ' ') { i++; }
else if ("()+-*".indexOf(c) >= 0) { toks.add(String.valueOf(c)); i++; }
else {
int j = i;
while (j < s.length() && " ()+-*".indexOf(s.charAt(j)) < 0) j++;
toks.add(s.substring(i, j)); i = j;
}
}
return toks;
}
private String key(List<String> arr) {
Collections.sort(arr);
return String.join(",", arr);
}
private Map<String, Integer> atom(String t) {
Map<String, Integer> m = new HashMap<>();
if (t.matches("-?\\d+")) m.put("", Integer.parseInt(t));
else if (val.containsKey(t)) m.put("", val.get(t));
else m.put(t, 1);
return m;
}
private Map<String, Integer> mul(Map<String, Integer> a, Map<String, Integer> b) {
Map<String, Integer> out = new HashMap<>();
for (Map.Entry<String, Integer> e1 : a.entrySet())
for (Map.Entry<String, Integer> e2 : b.entrySet()) {
List<String> arr = new ArrayList<>();
if (!e1.getKey().isEmpty()) arr.addAll(Arrays.asList(e1.getKey().split(",")));
if (!e2.getKey().isEmpty()) arr.addAll(Arrays.asList(e2.getKey().split(",")));
String k = key(arr);
out.merge(k, e1.getValue() * e2.getValue(), Integer::sum);
}
return out;
}
private Map<String, Integer> add(Map<String, Integer> a, Map<String, Integer> b, int sign) {
Map<String, Integer> out = new HashMap<>(a);
for (Map.Entry<String, Integer> e : b.entrySet())
out.merge(e.getKey(), sign * e.getValue(), Integer::sum);
return out;
}
}class Solution {
unordered_map<string, int> val;
vector<string> tokenize(const string& s) {
vector<string> toks;
int i = 0, n = s.size();
string seps = " ()+-*";
while (i < n) {
char c = s[i];
if (c == ' ') { i++; }
else if (string("()+-*").find(c) != string::npos) { toks.push_back(string(1, c)); i++; }
else {
int j = i;
while (j < n && seps.find(s[j]) == string::npos) j++;
toks.push_back(s.substr(i, j - i)); i = j;
}
}
return toks;
}
vector<string> split(const string& s) {
vector<string> parts;
if (s.empty()) return parts;
size_t start = 0, pos;
while ((pos = s.find(',', start)) != string::npos) {
parts.push_back(s.substr(start, pos - start));
start = pos + 1;
}
parts.push_back(s.substr(start));
return parts;
}
string key(vector<string> arr) {
sort(arr.begin(), arr.end());
string k;
for (size_t i = 0; i < arr.size(); i++) { if (i) k += ","; k += arr[i]; }
return k;
}
bool isInt(const string& t) {
size_t i = (t.size() && t[0] == '-') ? 1 : 0;
if (i == t.size()) return false;
for (; i < t.size(); i++) if (!isdigit((unsigned char)t[i])) return false;
return true;
}
map<string, int> atom(const string& t) {
map<string, int> m;
if (isInt(t)) m[""] = stoi(t);
else if (val.count(t)) m[""] = val[t];
else m[t] = 1;
return m;
}
map<string, int> mul(const map<string, int>& a, const map<string, int>& b) {
map<string, int> out;
for (auto& p1 : a) for (auto& p2 : b) {
vector<string> arr = split(p1.first);
vector<string> arr2 = split(p2.first);
arr.insert(arr.end(), arr2.begin(), arr2.end());
out[key(arr)] += p1.second * p2.second;
}
return out;
}
map<string, int> add(map<string, int> a, const map<string, int>& b, int sign) {
for (auto& p : b) a[p.first] += sign * p.second;
return a;
}
public:
vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
for (int i = 0; i < (int)evalvars.size(); i++) val[evalvars[i]] = evalints[i];
vector<string> toks = tokenize(expression);
unordered_map<string, int> prec = {{"+", 1}, {"-", 1}, {"*", 2}};
vector<string> rpn, ops;
for (auto& t : toks) {
if (t == "(") ops.push_back(t);
else if (t == ")") {
while (!ops.empty() && ops.back() != "(") { rpn.push_back(ops.back()); ops.pop_back(); }
ops.pop_back();
} else if (prec.count(t)) {
while (!ops.empty() && ops.back() != "(" && prec[ops.back()] >= prec[t]) {
rpn.push_back(ops.back()); ops.pop_back();
}
ops.push_back(t);
} else rpn.push_back(t);
}
while (!ops.empty()) { rpn.push_back(ops.back()); ops.pop_back(); }
vector<map<string, int>> st;
for (auto& t : rpn) {
if (prec.count(t)) {
auto b = st.back(); st.pop_back();
auto a = st.back(); st.pop_back();
if (t == "+") st.push_back(add(a, b, 1));
else if (t == "-") st.push_back(add(a, b, -1));
else st.push_back(mul(a, b));
} else st.push_back(atom(t));
}
map<string, int> poly = st.back();
vector<pair<string, int>> terms;
for (auto& p : poly) if (p.second != 0) terms.push_back(p);
sort(terms.begin(), terms.end(), [&](const pair<string, int>& x, const pair<string, int>& y) {
int lx = x.first.empty() ? 0 : (int)split(x.first).size();
int ly = y.first.empty() ? 0 : (int)split(y.first).size();
if (lx != ly) return lx > ly;
return x.first < y.first;
});
vector<string> res;
for (auto& p : terms) {
if (p.first.empty()) res.push_back(to_string(p.second));
else {
string k = p.first;
for (auto& ch : k) if (ch == ',') ch = '*';
res.push_back(to_string(p.second) + "*" + k);
}
}
return res;
}
};Explanation
This is a mini computer-algebra engine. We turn the expression into a polynomial represented as a map from a sorted tuple of variable names to its integer coefficient, then print the terms in canonical order.
It runs in three stages. First tokenize splits the text into operators, parentheses, numbers, and variable names. Next we apply the shunting-yard algorithm to convert those tokens into RPN (postfix), which respects that * binds tighter than + and - and that parentheses group.
Finally we evaluate the RPN with a stack of polynomial maps. An atom becomes a number term, a known variable is substituted with its value, and an unknown variable becomes {(name,): 1}. Operators combine the top two maps: add merges coefficients of matching keys, and mul distributes by joining and re-sorting the variable tuples so like terms collapse together.
Example: expr = "e + 8 - a + 5" with e = 1. Substituting e turns it into 1 + 8 - a + 5. The constants combine to 14 and the variable term stays as -1*a, giving the output ["-1*a", "14"].
At the end we drop zero-coefficient terms and sort by degree (more variables first), then alphabetically, to produce the canonical term list.