# LeetCode 770: Basic Calculator IV

## Problem Restatement

We are given an algebraic expression as a string.

The expression may contain:

```text
integers
variables
+
-
*
parentheses
```

We are also given some variable values through:

```python
evalvars
evalints
```

For example:

```python
evalvars = ["e"]
evalints = [1]
```

means:

```text
e = 1
```

We need to simplify the expression after substituting known variables.

The result should be returned as a list of string terms.

The official format requires variable factors inside each term to be sorted lexicographically, terms sorted by descending degree, and ties sorted lexicographically by variables. Zero coefficient terms are omitted. Constants are included only if non-zero.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `expression`, a valid algebraic expression |
| Input | `evalvars`, variables with known values |
| Input | `evalints`, integer values for those variables |
| Output | Simplified expression as a list of string terms |
| Operators | `+`, `-`, `*` |
| Order | Parentheses first, then multiplication, then addition and subtraction |

Example function shape:

```python
def basicCalculatorIV(
    expression: str,
    evalvars: list[str],
    evalints: list[int],
) -> list[str]:
    ...
```

## Examples

Example 1:

```python
expression = "e + 8 - a + 5"
evalvars = ["e"]
evalints = [1]
```

Substitute `e = 1`:

```text
1 + 8 - a + 5
```

Simplify:

```text
14 - a
```

Output:

```python
["-1*a", "14"]
```

Example 2:

```python
expression = "e - 8 + temperature - pressure"
evalvars = ["e", "temperature"]
evalints = [1, 12]
```

Substitute:

```text
1 - 8 + 12 - pressure
```

Simplify:

```text
5 - pressure
```

Output:

```python
["-1*pressure", "5"]
```

Example 3:

```python
expression = "(e + 8) * (e - 8)"
evalvars = []
evalints = []
```

No variables are substituted.

Expand:

```text
e * e - 64
```

Output:

```python
["1*e*e", "-64"]
```

## First Thought: Evaluate Like a Normal Calculator

For a normal calculator, each subexpression becomes one number.

Here, a subexpression may become a polynomial.

For example:

```text
a * b + 2 * a * b
```

simplifies to:

```text
3*a*b
```

So instead of storing just an integer value, each expression result must store many terms.

## Key Insight

Represent each polynomial as a dictionary:

```python
term_variables -> coefficient
```

Use a tuple of sorted variable names as the key.

Examples:

| Term | Key | Coefficient |
|---|---|---:|
| `5` | `()` | `5` |
| `-1*a` | `("a",)` | `-1` |
| `3*a*b` | `("a", "b")` | `3` |
| `2*a*a*b` | `("a", "a", "b")` | `2` |

This representation makes combining like terms easy.

For example:

```python
{
    ("a", "b"): 1,
    ("a", "b"): 2,
}
```

becomes:

```python
{
    ("a", "b"): 3,
}
```

## Polynomial Operations

We need three operations.

### Addition

Add coefficients for matching term keys.

```python
("a",) -> 2
("a",) -> 3
```

becomes:

```python
("a",) -> 5
```

### Subtraction

Same as addition, but subtract the second polynomial's coefficients.

```python
("a",) -> 2
minus
("a",) -> 3
```

becomes:

```python
("a",) -> -1
```

### Multiplication

Multiply every term from the first polynomial with every term from the second polynomial.

Variables are combined and sorted.

Example:

```text
(2*a*b) * (3*a*c)
```

Coefficient:

```text
2 * 3 = 6
```

Variables:

```text
a, b + a, c -> a, a, b, c
```

Result:

```text
6*a*a*b*c
```

## Parsing Strategy

The expression has precedence rules:

1. parentheses
2. multiplication
3. addition and subtraction

A clean way is recursive descent parsing.

We define three parser levels:

| Function | Parses |
|---|---|
| `parse_expr` | Addition and subtraction |
| `parse_term` | Multiplication |
| `parse_factor` | Number, variable, or parenthesized expression |

This matches normal arithmetic grammar.

## Tokenization

The expression may include spaces.

We first convert it into tokens.

For example:

```python
"e + 8 - a + 5"
```

becomes:

```python
["e", "+", "8", "-", "a", "+", "5"]
```

Parentheses are also tokens.

## Algorithm

1. Build a dictionary from `evalvars` to `evalints`.
2. Tokenize the expression.
3. Parse the expression recursively:
   1. `parse_factor` handles integers, variables, and parentheses.
   2. `parse_term` handles multiplication.
   3. `parse_expr` handles addition and subtraction.
4. Get the final polynomial dictionary.
5. Remove zero coefficient terms.
6. Sort terms by:
   1. descending degree
   2. lexicographic variable tuple
7. Format each term as a string.
8. Return the formatted list.

## Correctness

Each integer token is converted into a constant polynomial. Each known variable is substituted into a constant polynomial. Each unknown variable is converted into a one-variable polynomial.

The parser follows the expression grammar: `parse_factor` evaluates atomic expressions and parentheses, `parse_term` combines factors using multiplication, and `parse_expr` combines terms using addition and subtraction. Therefore, all operators are evaluated with the required precedence.

The polynomial operations preserve algebraic meaning. Addition and subtraction combine coefficients of matching variable tuples. Multiplication distributes every term on the left over every term on the right, multiplying coefficients and combining variables.

Thus the parsed polynomial is algebraically equivalent to the original expression after substitutions.

The final formatting removes zero coefficient terms and sorts remaining terms by the required degree and lexicographic order. Therefore, the returned list is exactly the required simplified representation.

## Complexity

Let `T` be the number of tokens, and let `M` be the number of distinct polynomial terms produced during expansion.

| Metric | Value | Why |
|---|---|---|
| Time | `O(T * M^2 * V log V)` | Multiplication may combine many term pairs, and variable tuples are sorted |
| Space | `O(M * V)` | Polynomial dictionaries store terms and variable tuples |

`V` is the maximum number of variables inside one term.

The exact bound depends on how much multiplication expands the expression.

## Implementation

```python
from collections import defaultdict

class Solution:
    def basicCalculatorIV(
        self,
        expression: str,
        evalvars: list[str],
        evalints: list[int],
    ) -> list[str]:
        values = dict(zip(evalvars, evalints))
        tokens = self.tokenize(expression)
        index = 0

        def add(poly1, poly2):
            result = defaultdict(int)

            for key, coeff in poly1.items():
                result[key] += coeff

            for key, coeff in poly2.items():
                result[key] += coeff

            return result

        def sub(poly1, poly2):
            result = defaultdict(int)

            for key, coeff in poly1.items():
                result[key] += coeff

            for key, coeff in poly2.items():
                result[key] -= coeff

            return result

        def mul(poly1, poly2):
            result = defaultdict(int)

            for key1, coeff1 in poly1.items():
                for key2, coeff2 in poly2.items():
                    key = tuple(sorted(key1 + key2))
                    result[key] += coeff1 * coeff2

            return result

        def constant(value):
            return {(): value}

        def variable(name):
            return {(name,): 1}

        def parse_expr():
            nonlocal index

            result = parse_term()

            while index < len(tokens) and tokens[index] in {"+", "-"}:
                op = tokens[index]
                index += 1

                right = parse_term()

                if op == "+":
                    result = add(result, right)
                else:
                    result = sub(result, right)

            return result

        def parse_term():
            nonlocal index

            result = parse_factor()

            while index < len(tokens) and tokens[index] == "*":
                index += 1
                right = parse_factor()
                result = mul(result, right)

            return result

        def parse_factor():
            nonlocal index

            token = tokens[index]
            index += 1

            if token == "(":
                result = parse_expr()
                index += 1
                return result

            if token.isdigit():
                return constant(int(token))

            if token in values:
                return constant(values[token])

            return variable(token)

        polynomial = parse_expr()

        terms = [
            (vars_, coeff)
            for vars_, coeff in polynomial.items()
            if coeff != 0
        ]

        terms.sort(key=lambda item: (-len(item[0]), item[0]))

        answer = []

        for vars_, coeff in terms:
            if not vars_:
                answer.append(str(coeff))
            else:
                answer.append(str(coeff) + "*" + "*".join(vars_))

        return answer

    def tokenize(self, expression: str) -> list[str]:
        tokens = []
        i = 0

        while i < len(expression):
            ch = expression[i]

            if ch == " ":
                i += 1
                continue

            if ch in "+-*()":
                tokens.append(ch)
                i += 1
                continue

            j = i

            while j < len(expression) and expression[j].isalnum():
                j += 1

            tokens.append(expression[i:j])
            i = j

        return tokens
```

## Code Explanation

We first build the substitution map:

```python
values = dict(zip(evalvars, evalints))
```

Then we tokenize the expression:

```python
tokens = self.tokenize(expression)
```

A polynomial is stored as a dictionary. The empty tuple `()` represents the constant term.

```python
def constant(value):
    return {(): value}
```

An unknown variable becomes:

```python
def variable(name):
    return {(name,): 1}
```

Addition and subtraction combine coefficients with the same key.

Multiplication loops over every term pair:

```python
for key1, coeff1 in poly1.items():
    for key2, coeff2 in poly2.items():
```

The new variable tuple is:

```python
key = tuple(sorted(key1 + key2))
```

Sorting ensures `b*a` and `a*b` become the same term key.

The parser has three precedence levels.

`parse_expr` handles `+` and `-`.

`parse_term` handles `*`.

`parse_factor` handles numbers, variables, and parenthesized expressions.

When `parse_factor` sees `"("`, it parses a full expression inside the parentheses:

```python
result = parse_expr()
index += 1
return result
```

The `index += 1` skips the closing `")"`.

Finally, we remove zero terms:

```python
if coeff != 0
```

Then sort by required output order:

```python
terms.sort(key=lambda item: (-len(item[0]), item[0]))
```

A higher degree appears first. If two terms have the same degree, their variable tuples decide lexicographic order.

## Testing

```python
def run_tests():
    s = Solution()

    assert s.basicCalculatorIV(
        "e + 8 - a + 5",
        ["e"],
        [1],
    ) == ["-1*a", "14"]

    assert s.basicCalculatorIV(
        "e - 8 + temperature - pressure",
        ["e", "temperature"],
        [1, 12],
    ) == ["-1*pressure", "5"]

    assert s.basicCalculatorIV(
        "(e + 8) * (e - 8)",
        [],
        [],
    ) == ["1*e*e", "-64"]

    assert s.basicCalculatorIV(
        "a * b * c + b * a * c * 4",
        [],
        [],
    ) == ["5*a*b*c"]

    assert s.basicCalculatorIV(
        "a - a",
        [],
        [],
    ) == []

    assert s.basicCalculatorIV(
        "2 * 3 + 4",
        [],
        [],
    ) == ["10"]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| Substitution and free variable | Confirms known variables become constants |
| Multi-letter variables | Confirms variable names are parsed correctly |
| Parentheses and multiplication | Confirms expansion |
| Combining like terms | Confirms variable tuples are normalized |
| Zero coefficient | Confirms zero terms are omitted |
| Pure arithmetic | Confirms constants are evaluated |