LeetCode Solutions Blog

Basic Calculator IV

Difficulty: Hard

Problem Description

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"].

Key Insights

The expression consists of variables, integers, and operators, which need to be parsed and evaluated in the correct order.
We must handle the evaluation of expressions involving parentheses and maintain the correct order of operations (parentheses first, then multiplication, then addition and subtraction).
The output must be formatted with sorted variables and proper coefficients, omitting any terms with a coefficient of zero.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the expression, due to parsing and evaluating the expression in a single pass. Space Complexity: O(m), where m is the number of unique variables and terms generated during evaluation.

Solution

To solve the problem, we will use a recursive approach combined with a stack to manage the evaluation of the expression. We'll break down the expression into manageable tokens, handle the evaluation of variables using a hashmap for easy access, and combine terms according to their coefficients and variables. The resulting terms will be sorted based on the number of variables and their lexicographic order.

Code Solutions

def basicCalculatorIV(expression, evalvars, evalints):
    # Create a mapping for variables to their evaluated integers
    eval_map = dict(zip(evalvars, evalints))
    
    def evaluate(expr):
        stack = []
        current = []
        sign = 1  # 1 for '+', -1 for '-'
        
        i = 0
        while i < len(expr):
            if expr[i] == ' ':
                i += 1
                continue
            if expr[i] in '+-':
                sign = 1 if expr[i] == '+' else -1
                i += 1
            elif expr[i].isdigit():  # Handle numbers
                num = 0
                while i < len(expr) and expr[i].isdigit():
                    num = num * 10 + int(expr[i])
                    i += 1
                current.append(sign * num)
            elif expr[i].isalpha():  # Handle variables
                var = ''
                while i < len(expr) and expr[i].isalpha():
                    var += expr[i]
                    i += 1
                current.append(sign * eval_map.get(var, 1))  # Default to 1 if var is not in eval_map
            elif expr[i] == '(':
                # Find the matching closing parenthesis
                j = i + 1
                count = 1
                while j < len(expr) and count > 0:
                    if expr[j] == '(':
                        count += 1
                    elif expr[j] == ')':
                        count -= 1
                    j += 1
                current.append(evaluate(expr[i+1:j-1]))  # Evaluate the inside of the parentheses
                i = j
            elif expr[i] == ')':
                break
        
        # Combine all the current evaluated terms
        result = {}
        for term in current:
            if isinstance(term, int):
                result[''] = result.get('', 0) + term  # Constant term
            else:
                result[term] = result.get(term, 0) + (1 if sign > 0 else -1)
        
        return result
    
    # Evaluate the expression
    result = evaluate(expression)
    # Format the output according to the problem statement
    output = []
    for term, coeff in sorted(result.items(), key=lambda x: (-len(x[0]), x[0])):
        if coeff == 0:
            continue
        output.append(f"{coeff}{('*' + term) if term else ''}")
    
    return output