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 [-2^31, 2^31 - 1].
Examples
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
Solution
Method 1 - Using Stack and Object Modeling
Solutions for this version, however, require some extra effort apart from the general structure in Basic Calculator 3 Problem.
Due to the presence of variables (free variables, to be exact), partial results at each calculation step might be expressions rather than pure numbers. We need a structure to properly represent partial results.
We should design a structure to easily handle operations like addition, subtraction, and multiplication. Here, each expression is shown as a collection of mappings between terms and their coefficients, where each term is a list of free variables in lexicographic order. Here are two examples:
"2 * a * b - d * c": This expression has two terms:["a", "b"]with a coefficient of2and["c", "d"]with a coefficient of-1. Thus, we represent it as["a", "b"] --> 2and["c", "d"] --> -1."4": This expression has a single term with zero free variables, represented as[]. The coefficient is4, giving us the mapping[] --> 4. Generally, for any expression consisting of a pure number, we have the mapping[] --> num.
The Term and Expression classes defined below further clarify the details.
See below for a detailed definition of the Term and Expression classes.
Term class:
// doesnt contain coeff
private static class Term implements Comparable<Term> {
List<String> vars;
static final Term C = new Term(Arrays.asList()); // this is the term for pure numbers
Term(List<String> vars) {
this.vars = vars;
}
// code removed below for clarity, complete code available in the solution below
}
Expression Class:
private static class Expression {
Map<Term, Integer> terms;
Expression(Term term, int coeff) {
terms = new HashMap<>();
terms.put(term, coeff);
}
void addTerm(Term term, int coeff) {
terms.put(term, coeff + terms.getOrDefault(term, 0));
}
}
The Term class allows for term comparison based on their degrees and generates custom string representations.
The Expression class facilitates the addition of new terms to the existing mapping.
Addition of two expressions involves merging all mappings from the second expression into the first, combining the coefficients of identical terms when possible.
private Expression addition(Expression expression1, Expression expression2, int sign) {
for (Map.Entry<Term, Integer> e : expression2.terms.entrySet()) {
expression1.addTerm(e.getKey(), sign * e.getValue());
}
return expression1;
}
Subtraction of two expressions is achieved by first negating the coefficients of the second expression’s terms and then adding them to the first expression (effectively, this can be combined with the addition by using the addition function with a sign of -1).
Multiplication of two expressions involves combining each term from the first expression with every term from the second expression, including their coefficients.
private Expression multiplication(Expression expression1, Expression expression2) {
Expression res = new Expression(Term.C, 0);
for (Map.Entry<Term, Integer> e1 : expression1.terms.entrySet()) {
for (Map.Entry<Term, Integer> e2 : expression2.terms.entrySet()) {
res.addTerm(merge(e1.getKey(), e2.getKey()), e1.getValue() * e2.getValue());
}
}
return res;
}
private Term merge(Term term1, Term term2) {
List<String> vars = new ArrayList<>();
vars.addAll(term1.vars);
vars.addAll(term2.vars);
Collections.sort(vars);
return new Term(vars);
}
Finally, to match the required output format, we have a function that converts the mappings in the result expression to a list of strings. Each string consists of the coefficient and the term joined by the * operator. Terms with a 0 coefficient are excluded, and terms without free variables are represented by numbers alone.
Regarding complexity, the nominal runtime complexity of this solution is similar to the recursive approach for Basic Calculator III, which is O(n^2). By using stacks for the simulation, the nominal time complexity can be reduced to O(n)—left as an exercise.
The term “nominal” is used because the complexity analysis assumes constant time for addition, subtraction, and multiplication operations on expressions, as with pure numbers. This assumption is not always valid since the number of terms can grow exponentially (e.g., (a + b) * (c + d) * (e + f) * ...). Nevertheless, this solution should be effective for general test cases.
Code
Java
public 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]);
}
return format(calculate(expression, evalMap));
}
private List<String> format(Expression expression) {
List<Term> terms = new ArrayList<>(expression.terms.keySet());
Collections.sort(terms);
List<String> res = new ArrayList<>(terms.size());
for (Term term : terms) {
int coeff = expression.terms.get(term);
if (coeff == 0) continue;
res.add(coeff + (term.equals(Term.C) ? "" : "*" + term.toString()));
}
return res;
}
private Expression calculate(String s, Map<String, Integer> evalMap) {
Expression l1 = new Expression(Term.C, 0);
int o1 = 1;
Expression l2 = new Expression(Term.C, 1);
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (Character.isDigit(c)) {
int num = c - '0';
while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {
num = num * 10 + (s.charAt(++i) - '0');
}
l2 = multiplication(l2, new Expression(Term.C, num));
} else if (Character.isLowerCase(c)) {
int j = i;
while (i + 1 < s.length() && Character.isLowerCase(s.charAt(i + 1))) i++;
String var = s.substring(j, i + 1);
Term term = evalMap.containsKey(var) ? Term.C : new Term(Arrays.asList(var));
int num = evalMap.getOrDefault(var, 1);
l2 = multiplication(l2, new Expression(term, num));
} else if (c == '(') {
int j = i;
for (int cnt = 0; i < s.length(); i++) {
if (s.charAt(i) == '(') cnt++;
if (s.charAt(i) == ')') cnt--;
if (cnt == 0) break;
}
l2 = multiplication(l2, calculate(s.substring(j + 1, i), evalMap));
} else if (c == '+' || c == '-') {
l1 = addition(l1, l2, o1);
o1 = (c == '+' ? 1 : -1);
l2 = new Expression(Term.C, 1);
}
}
return addition(l1, l2, o1);
}
private static class Term implements Comparable<Term> {
List<String> vars;
static final Term C = new Term(Collections.emptyList());
Term(List<String> vars) {
this.vars = vars;
}
@Override
public int hashCode() {
return vars.hashCode();
}
@Override
public boolean equals(Object obj) {
if (this == obj) return true;
if (!(obj instanceof Term)) return false;
Term other = (Term) obj;
return this.vars.equals(other.vars);
}
@Override
public String toString() {
return String.join("*", vars);
}
@Override
public int compareTo(Term other) {
if (this.vars.size() != other.vars.size()) {
return Integer.compare(other.vars.size(), this.vars.size());
} else {
for (int i = 0; i < this.vars.size(); i++) {
int cmp = this.vars.get(i).compareTo(other.vars.get(i));
if (cmp != 0) return cmp;
}
}
return 0;
}
}
private static class Expression {
Map<Term, Integer> terms;
Expression(Term term, int coeff) {
terms = new HashMap<>();
terms.put(term, coeff);
}
void addTerm(Term term, int coeff) {
terms.put(term, coeff + terms.getOrDefault(term, 0));
}
}
private Expression addition(Expression expression1, Expression expression2, int sign) {
for (Map.Entry<Term, Integer> e : expression2.terms.entrySet()) {
expression1.addTerm(e.getKey(), sign * e.getValue());
}
return expression1;
}
private Expression multiplication(Expression expression1, Expression expression2) {
Expression res = new Expression(Term.C, 0);
for (Map.Entry<Term, Integer> e1 : expression1.terms.entrySet()) {
for (Map.Entry<Term, Integer> e2 : expression2.terms.entrySet()) {
res.addTerm(merge(e1.getKey(), e2.getKey()), e1.getValue() * e2.getValue());
}
}
return res;
}
private Term merge(Term term1, Term term2) {
List<String> vars = new ArrayList<>();
vars.addAll(term1.vars);
vars.addAll(term2.vars);
Collections.sort(vars);
return new Term(vars);
}
}
Python
class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
evalMap = {var: val for var, val in zip(evalvars, evalints)}
return self.format(self.calculate(expression, evalMap))
def format(self, expression) -> List[str]:
terms = sorted(expression.terms.keys())
result = []
for term in terms:
coeff = expression.terms[term]
if coeff == 0:
continue
result.append(coeff + (term == Term.C and '' or '*' + term.toString()))
return result
def calculate(self, s: str, evalMap: Dict[str, int]):
l1, o1 = Expression(Term.C, 0), 1
l2 = Expression(Term.C, 1)
i = 0
while i < len(s):
c = s[i]
if c.isdigit():
num = int(c)
while i + 1 < len(s) and s[i + 1].isdigit():
num = num * 10 + int(s[i + 1])
i += 1
l2 = self.multiplication(l2, Expression(Term.C, num))
elif c.islower():
j = i
while i + 1 < len(s) and s[i + 1].islower():
i += 1
var = s[j:i + 1]
term = Term.C if var in evalMap else Term([var])
num = evalMap.get(var, 1)
l2 = self.multiplication(l2, Expression(term, num))
elif c == '(':
j = i
cnt = 0
while i < len(s):
if s[i] == '(':
cnt += 1
if s[i] == ')':
cnt -= 1
if cnt == 0:
break
i += 1
l2 = self.multiplication(l2, self.calculate(s[j + 1:i], evalMap))
elif c in '+-':
l1 = self.addition(l1, l2, o1)
o1 = 1 if c == '+' else -1
l2 = Expression(Term.C, 1)
i += 1
return self.addition(l1, l2, o1)
def addition(self, expression1, expression2, sign) -> "Expression":
for term, coeff in expression2.terms.items():
expression1.addTerm(term, sign * coeff)
return expression1
def multiplication(self, expression1, expression2) -> "Expression":
result = Expression(Term.C, 0)
for term1, coeff1 in expression1.terms.items():
for term2, coeff2 in expression2.terms.items():
result.addTerm(self.merge(term1, term2), coeff1 * coeff2)
return result
def merge(self, term1, term2) -> "Term":
vars = term1.vars + term2.vars
vars.sort()
return Term(vars)
class Term:
C = "Term([])" # Singleton term representing pure numbers
def __init__(self, vars: List[str]):
self.vars = vars
def __repr__(self):
return f"Term({self.vars})"
def __eq__(self, other):
return isinstance(other, Term) and self.vars == other.vars
def __lt__(self, other):
if len(self.vars) != len(other.vars):
return len(self.vars) > len(other.vars)
return self.vars < other.vars
def __hash__(self):
return hash(tuple(self.vars))
def __str__(self):
return '*'.join(self.vars)
class Expression:
def __init__(self, term: "Term", coeff: int):
self.terms = {term: coeff}
def addTerm(self, term: "Term", coeff: int):
if term in self.terms:
self.terms[term] += coeff
else:
self.terms[term] = coeff
Complexity
- ⏰ Time complexity:
O(n * m^2)wherenis the length of the expression andmis the number of distinct terms. The dominant factor is merging terms during multiplication. - 🧺 Space complexity:
O(n + m)due to storing terms and expression objects.