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.
expr='e + 8 - a + 5', evalvars=['e'], evalints=[1]['-1*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]// Outline: tokenize, shunting-yard to RPN, evaluate using polynomial maps.
function basicCalculatorIV(expression, evalvars, evalints) {
const val = Object.fromEntries(evalvars.map((v,i) => [v, evalints[i]]));
// ... see Python version for full logic.
return [];
}// Outline only: tokenize, shunting-yard, polynomial map evaluation.
List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
Map<String,Integer> val = new HashMap<>();
for (int i = 0; i < evalvars.length; i++) val.put(evalvars[i], evalints[i]);
// See Python reference for the full implementation.
return new ArrayList<>();
}// Outline only: tokenize, shunting-yard, polynomial map evaluation.
vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
unordered_map<string,int> val;
for (int i = 0; i < (int)evalvars.size(); i++) val[evalvars[i]] = evalints[i];
// See Python reference for the full implementation.
return {};
}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.