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".
  • 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 degree 4.
  • 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 0 are not included.
    • For example, an expression of "0" has an output 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:

1
2

Input: expression = "e + 8 - a + 5", evalvars = ["e"], evalints = [1]
Output: ["-1*a","14"]

Example 2:

1
2

Input: expression = "e - 8 + temperature - pressure", evalvars = ["e", "temperature"], evalints = [1, 12]
Output: ["-1*pressure","5"]

Example 3:

1
2

Input: expression = "(e + 8) * (e - 8)", evalvars = [], evalints = []
Output: ["1*e*e","-64"]

Constraints

  • 1 <= expression.length <= 250
  • expression consists of lowercase English letters, digits, '+', '-', '*', '(', ')', ' '.
  • expression does not contain any leading or trailing spaces.
  • All the tokens in expression are separated by a single space.
  • 0 <= evalvars.length <= 100
  • 1 <= evalvars[i].length <= 20
  • evalvars[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.

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:

  1. "2 * a * b - d * c": This expression has two terms: ["a", "b"] with a coefficient of 2 and ["c", "d"] with a coefficient of -1. Thus, we represent it as ["a", "b"] --> 2 and ["c", "d"] --> -1.
  2. "4": This expression has a single term with zero free variables, represented as []. The coefficient is 4, 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// 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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

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.

1
2
3
4
5
6
7

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146

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);
    }
}
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109

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) where n is the length of the expression and m is 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.