LeetCode Solutions Blog

Basic Calculator IV

Number: 781

Difficulty: Hard

Paid? No

Companies: Intuit

Problem Description

Given an arithmetic expression containing variables, numbers, addition, subtraction, multiplication, and parentheses, the goal is to simplify the expression into a list of tokens representing each term. Each term is expressed with its coefficient and variable factors (sorted lexicographically). Additionally, you are given a mapping of some variables to integer values that need to be substituted before simplification. The answer must include only non-zero terms and be ordered first by decreasing degree (number of factors) and then lexicographically by variable names.

Key Insights

Represent each polynomial as a mapping (dictionary) where the key is a tuple of variables (sorted) and the value is the coefficient.
Use recursive descent or a stack-based parsing technique to correctly handle operator precedence (parentheses first, then multiplication, then addition/subtraction).
Define helper methods to perform addition, subtraction, and multiplication on these polynomial dictionaries.
Substitute the provided evaluation variables immediately during parsing to simplify the expression.
Sort the final terms by the degree (number of factors) and lexicographic order of variable names.

Space and Time Complexity

Time Complexity: In the worst case, polynomial multiplication can lead to a combinatorial explosion of terms, resulting in exponential time in the number of multiplications. For typical input sizes, parsing takes O(n) time where n is the length of the expression. Space Complexity: O(m) where m is the number of distinct polynomial terms produced during computation, which in the worst case can also grow exponentially in the number of factors.

Solution

We first tokenize the input expression and then parse it using recursive descent parsing. During parsing, each number or variable is converted into a polynomial represented as a dictionary mapping from a tuple (representing the sorted factors in the term) to its integer coefficient (a constant is represented with an empty tuple). For each binary operator (+, -, *), we define helper functions to add, subtract, or multiply two polynomials. When a variable appears in the polynomial and is found in the evaluation map, it is replaced by its corresponding value. Finally, after the entire expression is computed as a polynomial dictionary, we convert the dictionary into a sorted list of string tokens by:

Sorting terms: higher degree first and then lexicographically.
Formatting each term by placing the coefficient first (always explicitly shown) followed by the factors separated by an asterisk. This approach leverages recursion for its clarity in handling nested parentheses and uses hash tables (dictionaries) to aggregate polynomial terms.

Code Solutions

# Python solution for Basic Calculator IV
from collections import defaultdict

def basicCalculatorIV(expression, evalvars, evalints):
    # Map variables to their integer values.
    eval_map = {var: val for var, val in zip(evalvars, evalints)}
    
    # Function to add two polynomials.
    def poly_add(poly1, poly2):
        result = defaultdict(int)
        for key, val in poly1.items():
            result[key] += val
        for key, val in poly2.items():
            result[key] += val
        return {k: v for k, v in result.items() if v}
    
    # Function to multiply two polynomials.
    def poly_mult(poly1, poly2):
        result = defaultdict(int)
        for key1, coeff1 in poly1.items():
            for key2, coeff2 in poly2.items():
                # Merge the terms (tuples) and sort them.
                new_key = tuple(sorted(key1 + key2))
                result[new_key] += coeff1 * coeff2
        return {k: v for k, v in result.items() if v}
    
    # Parse functions using recursive descent parsing.
    tokens = expression.split()
    index = 0
    
    def parseExpr():
        nonlocal index
        poly = parseTerm()
        while index < len(tokens) and tokens[index] in ['+', '-']:
            op = tokens[index]
            index += 1
            next_poly = parseTerm()
            if op == '+':
                poly = poly_add(poly, next_poly)
            else:
                # Negate next_poly for subtraction.
                poly = poly_add(poly, {k: -v for k, v in next_poly.items()})
        return poly
    
    def parseTerm():
        nonlocal index
        poly = parseFactor()
        while index < len(tokens) and tokens[index] == '*':
            index += 1
            next_poly = parseFactor()
            poly = poly_mult(poly, next_poly)
        return poly
    
    def parseFactor():
        nonlocal index
        token = tokens[index]
        index += 1
        if token == '(':
            # Parse an expression within parentheses.
            poly = parseExpr()
            index += 1  # Skip the closing ')'
            return poly
        else:
            # The token is either a number or variable.
            if token.isdigit():
                return {(): int(token)}
            else:
                # Check if variable can be substituted.
                if token in eval_map:
                    return {(): eval_map[token]}
                else:
                    return {(token,): 1}
    
    # Begin parsing starting from the expression level.
    poly = parseExpr()
    
    # Function to convert a polynomial dictionary to the final answer tokens.
    def format_poly(poly):
        # Convert polynomial items to a list of (degree, sorted_key, coefficient).
        terms = []
        for key, coeff in poly.items():
            if coeff == 0:
                continue
            degree = len(key)
            terms.append((degree, key, coeff))
        # Sorting: degree in descending order, then lexicographically by key.
        terms.sort(key=lambda x: (-x[0], x[1]))
        result = []
        for degree, key, coeff in terms:
            if key:
                # Format term as "coeff*var1*var2*..."
                term = str(coeff) + '*' + '*'.join(key)
            else:
                term = str(coeff)
            result.append(term)
        return result

    return format_poly(poly)

# Example use:
#print(basicCalculatorIV("e + 8 - a + 5", ["e"], [1]))