# Basic Calculator IV
**Difficulty:** HARD
[External](https://leetcode.com/problems/basic-calculator-iv)
Canonical: https://scaleengineer.com/dsa/problems/basic-calculator-iv
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Recursion](https://scaleengineer.com/dsa/patterns/recursion)
**Data structures:** Hash Table, String, Stack
**Companies:** [Intuit](https://scaleengineer.com/companies/intuit), [Roblox](https://scaleengineer.com/companies/roblox)
---
## 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 `[-231, 231 - 1]`.

**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 <= 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`

# Approaches
## Recursive Descent with List-based Polynomial Representation
This approach tackles the problem by parsing the expression and performing polynomial arithmetic. It uses a straightforward, but inefficient, data structure to represent polynomials: a simple list of term objects. Each operation, like addition or multiplication, produces a new list of terms which must then be explicitly simplified by iterating through the list to find and combine terms with the same variables.
**Time:** The time complexity is dominated by the `simplify` operation. If an intermediate polynomial has `T` terms, simplification takes `O(T^2 * D)`. Since multiplication of two polynomials with `T1` and `T2` terms can result in `T1 * T2` terms, the overall complexity can be very high, making it impractical for expressions that generate a large number of terms. · **Space:** O(T_max * D), where `T_max` is the maximum number of terms in any intermediate polynomial before simplification, and `D` is the maximum degree. The space can be large as simplification is a separate, potentially deferred, step.
**Pros:** The logic is conceptually simple, with a clear separation between generating terms and simplifying the result.
**Cons:** The simplification step, which is required after most operations, is very inefficient. Combining like terms in a list of size `T` takes `O(T^2 * D)` time, where `D` is the maximum degree (cost to compare variable lists).; Generates many intermediate `Term` objects, potentially leading to higher memory usage and garbage collection overhead before simplification.
### Explanation
In this method, we define a `Polynomial` as a `List<Term>`, and a `Term` as an object holding a coefficient and a `List<String>` of variables. The parsing logic is handled by a recursive descent parser which correctly respects operator precedence.

When two polynomials are added, their term lists are simply concatenated. When they are multiplied, a new list is formed containing the product of every term from the first polynomial with every term from the second. The main drawback is that after these operations, the resulting list contains duplicate variable combinations (e.g., two separate terms for `a*b`).

To handle this, a `simplify()` function is called. This function has to go through the list and merge these like terms. A naive implementation would involve a nested loop: for each term, scan the rest of the list for terms with the same variables and combine them. This leads to a quadratic time complexity in the number of terms, which is highly inefficient, especially for expressions that generate many terms.
### Algorithm
- Represent a polynomial as a `List<Term>`, where `Term` is a class containing a coefficient and a list of variables.
- Use a recursive descent parser to break down the expression according to operator precedence (`()`, then `*`, then `+`/`-`).
- For addition and subtraction operations, concatenate the lists of terms from the two operand polynomials.
- For multiplication, generate a new list of terms by taking the cross product of the terms from the two operand polynomials.
- After each operation that modifies the list of terms (like addition or multiplication), call a `simplify` method.
- The `simplify` method iterates through the list to find and combine like terms (terms with the same set of variables). This typically requires a nested loop, comparing each term with every other term.
- Finally, sort the simplified list of terms from the final polynomial according to the specified output format and convert them to strings.

## Recursive Descent with Map-based Polynomial Representation
This efficient approach also uses a recursive descent parser but employs a much better data structure for representing polynomials. By using a `Map` to store terms, with canonical keys representing the variable part of each term, we can combine like terms on-the-fly. This avoids the costly, separate simplification step of the naive list-based approach.
**Time:** Let `T` be the max number of terms and `D` be the max degree. An addition takes `O(T_2 * D)` where `T_2` is the size of the second operand. A multiplication takes `O(T_1 * T_2 * D log D)`, where the `D log D` factor comes from sorting the combined variable list for the new key. While the theoretical worst-case number of terms can be exponential in the number of multiplicative factors, this approach is very efficient for the kinds of expressions allowed by the problem constraints. · **Space:** O(T * D), where `T` is the maximum number of terms in any intermediate polynomial and `D` is the maximum degree. The space complexity is determined by the size of the largest polynomial generated during evaluation.
**Pros:** Highly efficient for combining like terms, which is the most frequent and potentially expensive part of polynomial arithmetic.; Represents the standard and robust method for symbolic manipulation of sparse polynomials.; Code for arithmetic operations is clean and directly maps to mathematical definitions.
**Cons:** Using a mutable object like `List<String>` as a map key can be error-prone if not handled carefully. The list must not be modified after being inserted as a key.
### Explanation
The core of this approach is the representation of a polynomial as a `Map<List<String>, Integer>`. A term like `5*a*c*b` is canonicalized: the variables `(a, b, c)` are sorted lexicographically to `["a", "b", "c"]`, which is used as the key in the map. The value would be the coefficient, `5`. The constant term is represented by an empty list `[]` as the key.

This structure makes polynomial operations very efficient:
- **Addition**: `poly1.add(poly2)` involves iterating through `poly2.terms` and for each term, adding its coefficient to the corresponding term in `poly1.terms`. `map.getOrDefault` makes this concise.
- **Multiplication**: `poly1.multiply(poly2)` creates a new result map. It iterates through all pairs of terms from `poly1` and `poly2`. The product of a term `(vars1, coeff1)` and `(vars2, coeff2)` is a new term with coefficient `coeff1 * coeff2` and variables `vars1` and `vars2` merged and sorted. This new term is then added to the result map.

Because the map automatically handles the combination of like terms (by updating the value for an existing key), there is no need for a separate, slow simplification step. After parsing, the final map is converted to the required output format.

```java
import java.util.*;

class Solution {
    private int index;
    private List<String> tokens;
    private Map<String, Integer> evalMap;

    public List<String> basicCalculatorIV(String expression, String[] evalvars, int[] evalints) {
        evalMap = new HashMap<>();
        for (int i = 0; i < evalvars.length; i++) {
            evalMap.put(evalvars[i], evalints[i]);
        }

        String spacedExpr = expression.replaceAll("([\\(\\)\\+\\-\\\*])", " $1 ");
        tokens = new ArrayList<>(Arrays.asList(spacedExpr.trim().split("\\s+")));
        index = 0;

        Polynomial result = parseExpression();
        return result.toList();
    }

    class Polynomial {
        Map<List<String>, Integer> terms = new HashMap<>();

        Polynomial() {}

        Polynomial(String var) {
            List<String> term = new ArrayList<>();
            term.add(var);
            terms.put(term, 1);
        }

        Polynomial(int val) {
            terms.put(new ArrayList<>(), val);
        }

        Polynomial add(Polynomial other) {
            Polynomial result = new Polynomial();
            result.terms.putAll(this.terms);
            for (Map.Entry<List<String>, Integer> entry : other.terms.entrySet()) {
                result.terms.put(entry.getKey(), result.terms.getOrDefault(entry.getKey(), 0) + entry.getValue());
            }
            return result;
        }

        Polynomial subtract(Polynomial other) {
            Polynomial result = new Polynomial();
            result.terms.putAll(this.terms);
            for (Map.Entry<List<String>, Integer> entry : other.terms.entrySet()) {
                result.terms.put(entry.getKey(), result.terms.getOrDefault(entry.getKey(), 0) - entry.getValue());
            }
            return result;
        }

        Polynomial multiply(Polynomial other) {
            Polynomial result = new Polynomial();
            for (Map.Entry<List<String>, Integer> entry1 : this.terms.entrySet()) {
                for (Map.Entry<List<String>, Integer> entry2 : other.terms.entrySet()) {
                    List<String> newVars = new ArrayList<>(entry1.getKey());
                    newVars.addAll(entry2.getKey());
                    Collections.sort(newVars);
                    int newCoeff = entry1.getValue() * entry2.getValue();
                    result.terms.put(newVars, result.terms.getOrDefault(newVars, 0) + newCoeff);
                }
            }
            return result;
        }

        List<String> toList() {
            List<Term> sortedTerms = new ArrayList<>();
            for (Map.Entry<List<String>, Integer> entry : terms.entrySet()) {
                if (entry.getValue() != 0) {
                    sortedTerms.add(new Term(entry.getValue(), entry.getKey()));
                }
            }
            Collections.sort(sortedTerms);

            List<String> result = new ArrayList<>();
            for (Term term : sortedTerms) {
                result.add(term.toString());
            }
            return result;
        }
    }

    class Term implements Comparable<Term> {
        int coeff;
        List<String> vars;

        Term(int coeff, List<String> vars) {
            this.coeff = coeff;
            this.vars = vars;
        }

        @Override
        public String toString() {
            if (vars.isEmpty()) {
                return String.valueOf(coeff);
            }
            StringBuilder sb = new StringBuilder();
            sb.append(coeff);
            for (String var : vars) {
                sb.append("*").append(var);
            }
            return sb.toString();
        }

        @Override
        public int compareTo(Term other) {
            if (this.vars.size() != other.vars.size()) {
                return other.vars.size() - this.vars.size();
            }
            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 Polynomial parseExpression() {
        Polynomial left = parseTerm();
        while (index < tokens.size()) {
            String op = tokens.get(index);
            if (op.equals("+")) {
                index++;
                Polynomial right = parseTerm();
                left = left.add(right);
            } else if (op.equals("-")) {
                index++;
                Polynomial right = parseTerm();
                left = left.subtract(right);
            } else {
                break;
            }
        }
        return left;
    }

    private Polynomial parseTerm() {
        Polynomial left = parseFactor();
        while (index < tokens.size() && tokens.get(index).equals("*")) {
            index++;
            Polynomial right = parseFactor();
            left = left.multiply(right);
        }
        return left;
    }

    private Polynomial parseFactor() {
        String token = tokens.get(index);
        if (token.equals("(")) {
            index++;
            Polynomial result = parseExpression();
            index++;
            return result;
        } else if (Character.isDigit(token.charAt(0))) {
            index++;
            return new Polynomial(Integer.parseInt(token));
        } else {
            index++;
            if (evalMap.containsKey(token)) {
                return new Polynomial(evalMap.get(token));
            } else {
                return new Polynomial(token);
            }
        }
    }
}
```
### Algorithm
- Represent a polynomial using a `Map<List<String>, Integer>`. The key is a lexicographically sorted list of variable names, serving as a canonical representation for a term's variable part. The value is the term's integer coefficient.
- Use a recursive descent parser to evaluate the expression. The functions `parseExpression`, `parseTerm`, and `parseFactor` handle `+`/`-`, `*`, and literals/parentheses respectively.
- When parsing a number or variable, create a new `Polynomial` object representing that single term.
- **Addition/Subtraction**: To add/subtract `poly2` to/from `poly1`, iterate through `poly2`'s map. For each term, update the corresponding coefficient in `poly1`'s map. The map's structure makes finding like terms an efficient `O(1)` average time operation (plus key comparison time).
- **Multiplication**: To multiply `poly1` and `poly2`, create a new empty `Polynomial` (and its map). Iterate through every pair of terms from `poly1` and `poly2`. For each pair, compute the product term: the new coefficient is the product of the old coefficients, and the new variable list is the sorted combination of the old variable lists. Update the result map with this new term.
- After the entire expression is parsed, convert the final polynomial's map into a list of strings. Filter out terms with zero coefficients, sort the remaining terms based on degree and lexicographical order, and format them as required.

# Solutions
### Java

```java
class Solution {
public
  List<String> basicCalculatorIV(String expression, String[] evalvars,
                                 int[] evalints) {
    Polynomial polynomial = parse(expression);
    Map<String, Integer> evaluateMap = new HashMap<String, Integer>();
    int length = evalvars.length;
    for (int i = 0; i < length; i++)
      evaluateMap.put(evalvars[i], evalints[i]);
    Polynomial evaluation = polynomial.evaluate(evaluateMap);
    List<String> list = evaluation.toList();
    return list;
  }
public
  Polynomial parse(String expression) {
    List<Polynomial> bucket = new ArrayList<Polynomial>();
    List<Character> operators = new ArrayList<Character>();
    int index = 0, length = expression.length();
    while (index < length) {
      if (expression.charAt(index) == '(') {
        int balance = 0;
        int curIndex = index;
        while (curIndex < length) {
          if (expression.charAt(curIndex) == '(')
            balance++;
          else if (expression.charAt(curIndex) == ')')
            balance--;
          if (balance == 0)
            break;
          curIndex++;
        }
        Polynomial curPolynomial =
            parse(expression.substring(index + 1, curIndex));
        bucket.add(curPolynomial);
        index = curIndex;
      } else if (Character.isLetterOrDigit(expression.charAt(index))) {
        boolean flag = true;
        int curIndex = index;
        while (curIndex < length) {
          if (expression.charAt(curIndex) == ' ') {
            Polynomial curPolynomial =
                make(expression.substring(index, curIndex));
            bucket.add(curPolynomial);
            flag = false;
            break;
          }
          curIndex++;
        }
        if (flag) {
          Polynomial polynomial = make(expression.substring(index));
          bucket.add(polynomial);
        }
        index = curIndex;
      } else if (expression.charAt(index) != ' ')
        operators.add(expression.charAt(index));
      index++;
    }
    for (int i = operators.size() - 1; i >= 0; i--) {
      if (operators.get(i) == '*') {
        Polynomial newPolynomial =
            combine(bucket.get(i), bucket.remove(i + 1), operators.remove(i));
        bucket.set(i, newPolynomial);
      }
    }
    if (bucket.isEmpty())
      return new Polynomial();
    Polynomial polynomial = bucket.get(0);
    int size = operators.size();
    for (int i = 0; i < size; i++)
      polynomial = combine(polynomial, bucket.get(i + 1), operators.get(i));
    return polynomial;
  }
public
  Polynomial make(String expression) {
    Polynomial polynomial = new Polynomial();
    List<String> list = new ArrayList<String>();
    if (Character.isDigit(expression.charAt(0)))
      polynomial.update(list, Integer.valueOf(expression));
    else {
      list.add(expression);
      polynomial.update(list, 1);
    }
    return polynomial;
  }
public
  Polynomial combine(Polynomial polynomial1, Polynomial polynomial2,
                     char operator) {
    if (operator== '+')
      return polynomial1.add(polynomial2);
    else if (operator== '-')
      return polynomial1.subtract(polynomial2);
    else if (operator== '*')
      return polynomial1.multiply(polynomial2);
    else
      return null;
  }
} class Polynomial {
  Map<List<String>, Integer> countMap;
public
  Polynomial() { countMap = new HashMap<List<String>, Integer>(); }
public
  void update(List<String> key, int count) {
    int newCount = countMap.getOrDefault(key, 0) + count;
    countMap.put(key, newCount);
  }
public
  Polynomial add(Polynomial polynomial2) {
    Polynomial sum = new Polynomial();
    Set<List<String>> keySet1 = countMap.keySet();
    for (List<String> list : keySet1)
      sum.update(list, countMap.get(list));
    Set<List<String>> keySet2 = polynomial2.countMap.keySet();
    for (List<String> list : keySet2)
      sum.update(list, polynomial2.countMap.get(list));
    return sum;
  }
public
  Polynomial subtract(Polynomial polynomial2) {
    Polynomial difference = new Polynomial();
    Set<List<String>> keySet1 = countMap.keySet();
    for (List<String> list : keySet1)
      difference.update(list, countMap.get(list));
    Set<List<String>> keySet2 = polynomial2.countMap.keySet();
    for (List<String> list : keySet2)
      difference.update(list, -polynomial2.countMap.get(list));
    return difference;
  }
public
  Polynomial multiply(Polynomial polynomial2) {
    Polynomial product = new Polynomial();
    Set<List<String>> keySet1 = countMap.keySet();
    Set<List<String>> keySet2 = polynomial2.countMap.keySet();
    for (List<String> list1 : keySet1) {
      for (List<String> list2 : keySet2) {
        List<String> newList = new ArrayList<String>();
        for (String str : list1)
          newList.add(str);
        for (String str : list2)
          newList.add(str);
        Collections.sort(newList);
        product.update(newList,
                       countMap.get(list1) * polynomial2.countMap.get(list2));
      }
    }
    return product;
  }
public
  Polynomial evaluate(Map<String, Integer> evaluateMap) {
    Polynomial polynomial = new Polynomial();
    Set<List<String>> keySet = countMap.keySet();
    for (List<String> list : keySet) {
      int count = countMap.get(list);
      List<String> freeList = new ArrayList<String>();
      for (String str : list) {
        if (evaluateMap.containsKey(str))
          count *= evaluateMap.get(str);
        else
          freeList.add(str);
      }
      polynomial.update(freeList, count);
    }
    return polynomial;
  }
public
  int compareList(List<String> list1, List<String> list2) {
    int size1 = list1.size(), size2 = list2.size();
    if (size1 != size2)
      return size2 - size1;
    else {
      for (int i = 0; i < size1; i++) {
        String str1 = list1.get(i), str2 = list2.get(i);
        if (!str1.equals(str2))
          return str1.compareTo(str2);
      }
      return 0;
    }
  }
public
  List<String> toList() {
    List<String> list = new ArrayList<String>();
    List<List<String>> keyList = new ArrayList<List<String>>(countMap.keySet()); Collections . sort ( keyList , new Comparator < List < String >>() { public int compare ( List < String > list1 , List < String > list2 ) { return compareList ( list1 , list2 );
  } });
for (List<String> key : keyList) {
  int count = countMap.get(key);
  if (count != 0) {
    StringBuffer sb = new StringBuffer();
    sb.append(count);
    for (String str : key) {
      sb.append('*');
      sb.append(str);
    }
    list.add(sb.toString());
  }
}
return list;
}
}

```

### CPP

```cpp
// OJ: https://leetcode.com/problems/basic-calculator-iv class Solution { private: vector < string > tokenize ( string & expression ) { vector < string > tokens ; for ( int i = 0 ; i < expression . size ();) { string token ; if ( isalnum ( expression [ i ])) { while ( i < expression . size () && isalnum ( expression [ i ])) { token += expression [ i ++ ]; } } else token += expression [ i ++ ]; tokens . push_back ( token ); while ( i < expression . size () && expression [ i ] == ' ' ) ++ i ; } return tokens ; } vector < string > inject ( vector < string > & tokens , unordered_map < string , string > & m ) { for ( auto & token : tokens ) { if ( m . find ( token ) != m . end ()) token = m [ token ]; } return tokens ; } vector < string > toRPN ( vector < string > & tokens ) { stack < string > ops ; vector < string > ans ; for ( auto & token : tokens ) { switch ( token . back ()) { case '+' : case '-' : while ( ops . size () && ops . top () != "(" ) { ans . push_back ( ops . top ()); ops . pop (); } ops . push ( token ); break ; case '*' : if ( ops . size () && ops . top () == "*" ) { ans . push_back ( ops . top ()); ops . pop (); } ops . push ( token ); break ; case '(' : ops . push ( token ); break ; case ')' : while ( ops . size () && ops . top () != "(" ) { ans . push_back ( ops . top ()); ops . pop (); } if ( ops . size ()) ops . pop (); break ; default: ans . push_back ( token ); break ; } } while ( ops . size ()) { ans . push_back ( ops . top ()); ops . pop (); } return ans ; } vector < string > splitSymbols ( string exp ) { istringstream s ( exp ); vector < string > ans ; string symbol ; while ( getline ( s , symbol , '*' )) ans . push_back ( symbol ); return ans ; } vector < string > evaluate ( vector < string > & tokens ) { stack < map < string , int >> s ; for ( auto & token : tokens ) { switch ( token . back ()) { case '+' : case '-' : { int sign = token [ 0 ] == '+' ? 1 : - 1 ; auto b = s . top (); s . pop (); auto a = s . top (); s . pop (); map < string , int > m ; for ( auto & p : a ) { m [ p . first ] += p . second ; } for ( auto & p : b ) { m [ p . first ] += sign * p . second ; } s . push ( m ); break ; } case '*' : { auto b = s . top (); s . pop (); auto a = s . top (); s . pop (); map < string , int > m ; for ( auto & p : a ) { auto symbol1 = splitSymbols ( p . first ); for ( auto & q : b ) { istringstream sb ( q . first ); auto symbol2 = splitSymbols ( q . first ); string symbol ; if ( symbol1 . size () == 1 && symbol1 [ 0 ] == "1" ) { symbol = q . first ; } else if ( symbol2 . size () == 1 && symbol2 [ 0 ] == "1" ) { symbol = p . first ; } else { for ( int i = 0 , j = 0 ; i < symbol1 . size () || j < symbol2 . size ();) { if ( symbol . size ()) symbol += "*" ; if ( i >= symbol1 . size ()) { symbol += symbol2 [ j ++ ]; } else if ( j >= symbol2 . size ()) { symbol += symbol1 [ i ++ ]; } else if ( symbol1 [ i ] < symbol2 [ j ]){ symbol += symbol1 [ i ++ ]; } else { symbol += symbol2 [ j ++ ]; } } } m [ symbol ] += p . second * q . second ; } } s . push ( m ); break ; } default: { map < string , int > m ; if ( isdigit ( token . back ())) { m [ "1" ] = stoi ( token ); } else { m [ token ] = 1 ; } s . push ( m ); break ; } } } vector < string > ans ; for ( auto & p : s . top ()) { if ( ! p . second ) continue ; ans . push_back ( to_string ( p . second ) + ( p . first == "1" ? "" : "*" + p . first )); } stable_sort ( ans . begin (), ans . end (), [ & ]( string a , string b ) { return count ( a . begin (), a . end (), '*' ) > count ( b . begin (), b . end (), '*' ); }); return ans ; } public: vector < string > basicCalculatorIV ( string expression , vector < string >& evalvars , vector < int >& evalints ) { unordered_map < string , string > m ; for ( int i = 0 ; i < evalvars . size (); ++ i ) { m [ evalvars [ i ]] = to_string ( evalints [ i ]); } auto tokens = tokenize ( expression ); tokens = inject ( tokens , m ); tokens = toRPN ( tokens ); tokens = evaluate ( tokens ); return tokens ; } };
```