from collections import Counter
import re
class Solution:
def basicCalculatorIV(self, expression, evalvars, evalints):
def parse(expression):
tokens = re.findall(r'\w+|\+|\-|\*|\(|\)', expression)
def get_token():
return tokens.pop(0) if tokens else None
def parse_atom():
token = get_token()
if token == '(':
expr = parse_expr()
get_token() # ')'
return expr
elif token.isdigit():
return Counter({(): int(token)})
elif token.isalpha():
return Counter({(token,): 1})
def parse_factor():
atom = parse_atom()
while tokens and tokens[0] == '*':
get_token()
atom = multiply(atom, parse_atom())
return atom
def parse_term():
term = parse_factor()
while tokens and tokens[0] in ('+', '-'):
op = get_token()
next_factor = parse_factor()
if op == '+':
term += next_factor
else:
term -= next_factor
return term
def parse_expr():
return parse_term()
return parse_expr()
def multiply(a, b):
res = Counter()
for k1, v1 in a.items():
for k2, v2 in b.items():
k = tuple(sorted(k1 + k2))
res[k] += v1 * v2
return res
mapping = dict(zip(evalvars, evalints))
def substitute(expr):
res = Counter()
for k, v in expr.items():
new_k = []
coeff = v
for var in k:
if var in mapping:
coeff *= mapping[var]
else:
new_k.append(var)
res[tuple(sorted(new_k))] += coeff
return res
expr = parse(expression)
expr = substitute(expr)
items = [(k, v) for k, v in expr.items() if v != 0]
items.sort(key=lambda x: (-len(x[0]), x[0]))
res = []
for k, v in items:
term = [str(v)] + list(k)
res.append('*'.join(term))
return res
class Solution {
public:
using Term = vector<string>;
using Poly = map<Term, int>;
vector<string> basicCalculatorIV(string expression, vector<string>& evalvars, vector<int>& evalints) {
unordered_map<string, int> evalmap;
for (int i = 0; i < evalvars.size(); ++i)
evalmap[evalvars[i]] = evalints[i];
int pos = 0;
Poly poly = parse(expression, pos, evalmap);
vector<pair<Term, int>> terms;
for (auto& kv : poly)
if (kv.second != 0)
terms.push_back(kv);
sort(terms.begin(), terms.end(), [](const pair<Term, int>& a, const pair<Term, int>& b) {
if (a.first.size() != b.first.size()) return a.first.size() > b.first.size();
return a.first < b.first;
});
vector<string> result;
for (auto& kv : terms) {
string s = to_string(kv.second);
for (auto& var : kv.first)
s += "*" + var;
result.push_back(s);
}
return result;
}
Poly parse(const string& expr, int& pos, unordered_map<string, int>& evalmap) {
vector<Poly> stack;
vector<char> ops;
stack.push_back(parseTerm(expr, pos, evalmap));
while (pos < expr.size()) {
if (expr[pos] == ' ') { ++pos; continue; }
if (expr[pos] == ')') { ++pos; break; }
char op = expr[pos++];
Poly next = parseTerm(expr, pos, evalmap);
if (op == '*') {
stack.back() = multiply(stack.back(), next);
} else {
ops.push_back(op);
stack.push_back(next);
}
}
Poly res = stack[0];
for (int i = 1; i < stack.size(); ++i) {
if (ops[i-1] == '+') res = add(res, stack[i]);
else res = subtract(res, stack[i]);
}
return res;
}
Poly parseTerm(const string& expr, int& pos, unordered_map<string, int>& evalmap) {
while (pos < expr.size() && expr[pos] == ' ') ++pos;
if (expr[pos] == '(') {
++pos;
return parse(expr, pos, evalmap);
}
int start = pos;
while (pos < expr.size() && (isalnum(expr[pos]))) ++pos;
string token = expr.substr(start, pos - start);
Poly poly;
if (isdigit(token[0])) {
poly[{}] = stoi(token);
} else if (evalmap.count(token)) {
poly[{}] = evalmap[token];
} else if (!token.empty()) {
poly[{token}] = 1;
}
return poly;
}
Poly add(const Poly& a, const Poly& b) {
Poly res = a;
for (auto& kv : b)
res[kv.first] += kv.second;
return res;
}
Poly subtract(const Poly& a, const Poly& b) {
Poly res = a;
for (auto& kv : b)
res[kv.first] -= kv.second;
return res;
}
Poly multiply(const Poly& a, const Poly& b) {
Poly res;
for (auto& kv1 : a) {
for (auto& kv2 : b) {
Term t = kv1.first;
t.insert(t.end(), kv2.first.begin(), kv2.first.end());
sort(t.begin(), t.end());
res[t] += kv1.second * kv2.second;
}
}
return res;
}
};
class Solution {
public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
Map<String, Integer> evalMap = new HashMap<>();
for (int i = 0; i < evalvars.length; ++i)
evalMap.put(evalvars[i], evalints[i]);
List<String> tokens = tokenize(expression);
Map<List<String>, Integer> poly = parse(tokens, evalMap);
List<Map.Entry<List<String>, Integer>> terms = new ArrayList<>();
for (Map.Entry<List<String>, Integer> entry : poly.entrySet())
if (entry.getValue() != 0)
terms.add(entry);
terms.sort((a, b) -> {
if (a.getKey().size() != b.getKey().size())
return b.getKey().size() - a.getKey().size();
return a.getKey().toString().compareTo(b.getKey().toString());
});
List<String> res = new ArrayList<>();
for (Map.Entry<List<String>, Integer> entry : terms) {
StringBuilder sb = new StringBuilder();
sb.append(entry.getValue());
for (String var : entry.getKey())
sb.append("*").append(var);
res.add(sb.toString());
}
return res;
}
private List<String> tokenize(String s) {
List<String> tokens = new ArrayList<>();
int i = 0;
while (i < s.length()) {
char c = s.charAt(i);
if (Character.isLetterOrDigit(c)) {
int j = i;
while (j < s.length() && Character.isLetterOrDigit(s.charAt(j))) ++j;
tokens.add(s.substring(i, j));
i = j;
} else if ("+-*()".indexOf(c) >= 0) {
tokens.add(String.valueOf(c));
++i;
} else ++i;
}
return tokens;
}
private Map<List<String>, Integer> parse(List<String> tokens, Map<String, Integer> evalMap) {
Deque<Map<List<String>, Integer>> stack = new ArrayDeque<>();
Deque<String> ops = new ArrayDeque<>();
stack.push(parseTerm(tokens, evalMap));
while (!tokens.isEmpty()) {
String op = tokens.get(0);
if (op.equals(")")) {
tokens.remove(0);
break;
}
tokens.remove(0);
Map<List<String>, Integer> next = parseTerm(tokens, evalMap);
if (op.equals("*")) {
stack.push(multiply(stack.pop(), next));
} else {
ops.push(op);
stack.push(next);
}
}
Map<List<String>, Integer> res = stack.removeLast();
while (!stack.isEmpty()) {
String op = ops.removeLast();
Map<List<String>, Integer> next = stack.removeLast();
if (op.equals("+")) res = add(next, res);
else res = subtract(next, res);
}
return res;
}
private Map<List<String>, Integer> parseTerm(List<String> tokens, Map<String, Integer> evalMap) {
String token = tokens.remove(0);
Map<List<String>, Integer> poly = new HashMap<>();
if (token.equals("(")) {
poly = parse(tokens, evalMap);
} else if (Character.isDigit(token.charAt(0))) {
poly.put(new ArrayList<>(), Integer.parseInt(token));
} else if (evalMap.containsKey(token)) {
poly.put(new ArrayList<>(), evalMap.get(token));
} else {
List<String> term = new ArrayList<>();
term.add(token);
poly.put(term, 1);
}
return poly;
}
private Map<List<String>, Integer> add(Map<List<String>, Integer> a, Map<List<String>, Integer> b) {
Map<List<String>, Integer> res = new HashMap<>(a);
for (Map.Entry<List<String>, Integer> entry : b.entrySet())
res.put(entry.getKey(), res.getOrDefault(entry.getKey(), 0) + entry.getValue());
return res;
}
private Map<List<String>, Integer> subtract(Map<List<String>, Integer> a, Map<List<String>, Integer> b) {
Map<List<String>, Integer> res = new HashMap<>(a);
for (Map.Entry<List<String>, Integer> entry : b.entrySet())
res.put(entry.getKey(), res.getOrDefault(entry.getKey(), 0) - entry.getValue());
return res;
}
private Map<List<String>, Integer> multiply(Map<List<String>, Integer> a, Map<List<String>, Integer> b) {
Map<List<String>, Integer> res = new HashMap<>();
for (Map.Entry<List<String>, Integer> e1 : a.entrySet()) {
for (Map.Entry<List<String>, Integer> e2 : b.entrySet()) {
List<String> term = new ArrayList<>(e1.getKey());
term.addAll(e2.getKey());
Collections.sort(term);
res.put(term, res.getOrDefault(term, 0) + e1.getValue() * e2.getValue());
}
}
return res;
}
}
var basicCalculatorIV = function(expression, evalvars, evalints) {
function tokenize(expr) {
return expr.match(/\w+|\+|\-|\*|\(|\)/g);
}
function parse(tokens) {
function parseAtom() {
let token = tokens.shift();
if (token === '(') {
let res = parseExpr();
tokens.shift(); // ')'
return res;
} else if (/^\d+$/.test(token)) {
let poly = new Map();
poly.set('', parseInt(token));
return poly;
} else {
let poly = new Map();
if (evalmap.has(token)) {
poly.set('', evalmap.get(token));
} else {
poly.set(token, 1);
}
return poly;
}
}
function multiply(a, b) {
let res = new Map();
for (let [ka, va] of a.entries()) {
for (let [kb, vb] of b.entries()) {
let key = ka && kb ? (ka + '*' + kb).split('*').sort().join('*') : (ka || kb);
res.set(key, (res.get(key) || 0) + va * vb);
}
}
return res;
}
function parseFactor() {
let atom = parseAtom();
while (tokens[0] === '*') {
tokens.shift();
atom = multiply(atom, parseAtom());
}
return atom;
}
function parseExpr() {
let term = parseFactor();
while (tokens.length && (tokens[0] === '+' || tokens[0] === '-')) {
let op = tokens.shift();
let next = parseFactor();
for (let [k, v] of next.entries()) {
term.set(k, (term.get(k) || 0) + (op === '+' ? v : -v));
}
}
return term;
}
return parseExpr();
}
let evalmap = new Map();
for (let i = 0; i < evalvars.length; ++i) {
evalmap.set(evalvars[i], evalints[i]);
}
let tokens = tokenize(expression);
let poly = parse(tokens);
let terms = [];
for (let [k, v] of poly.entries()) {
if (v !== 0) {
let arr = k ? k.split('*') : [];
terms.push({ arr, v });
}
}
terms.sort((a, b) => {
if (b.arr.length !== a.arr.length) return b.arr.length - a.arr.length;
return a.arr.join().localeCompare(b.arr.join());
});
let res = [];
for (let term of terms) {
let s = [term.v].concat(term.arr).join('*');
res.push(s);
}
return res;
};
The Basic Calculator IV problem asks you to evaluate an arithmetic expression given as a string, which may contain variables, integer constants, and the operators +, -, *, and parentheses.
You are also given two lists: evalvars (variable names) and evalints (corresponding integer values). If a variable in the expression matches a name in evalvars, it should be replaced by its value from evalints.
The result should be a list of strings, each representing a term in the simplified polynomial (sorted by degree and lex order), with all like terms combined and zero-coefficient terms omitted.
Key constraints:
evalvars remain as symbols in the output.coefficient*var1*var2*... (no '*' for constants).
At first glance, this problem looks like a standard expression evaluation task, but with the twist of variables and symbolic manipulation. A brute-force approach might try to substitute values and evaluate the string directly, but this fails for symbolic variables and combining like terms.
The key insight is to treat the expression as a polynomial, where each term is a product of variables (possibly none, for constants), and to perform operations (addition, subtraction, multiplication) at the term level. This requires parsing the expression, handling operator precedence and parentheses, and keeping track of terms and their coefficients.
Instead of evaluating numbers, we need to manipulate and combine symbolic terms, much like algebra. Using data structures like maps or counters to represent the polynomial, we can efficiently add, subtract, and multiply terms, and substitute variable values as needed.
To solve the problem efficiently and correctly, we follow these steps:
evalvars by multiplying coefficients accordingly and removing the variable from the term.coefficient*var1*var2*... (no '*' for constants).
Example Input:
expression = "e + 8 - a + 5"
evalvars = ["e"]
evalints = [1]
Step-by-step:
evalvars, so substitute with 1evalvars, so remains as a variable["-1*a", "14"]
Brute-force Approach:
If we attempted to evaluate all possible substitutions and term combinations naively, the time complexity would be exponential in the number of variables and operators due to repeated string manipulations and lack of term consolidation.
Optimized Approach:
The Basic Calculator IV problem is a challenging mix of parsing, symbolic algebra, and data structure manipulation. The key insight is to treat expressions as polynomials, using maps or counters to represent and combine terms efficiently. By parsing the expression recursively and handling operator precedence, substituting variable values, and sorting and formatting the output, we achieve a robust and elegant solution that works for both numeric and symbolic cases.
The approach generalizes well and demonstrates the power of combining parsing techniques with algebraic manipulation and appropriate data structures.