Basic Calculator IV

Hard

Intuit

0 views

Topics:

StringsStacks

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³¹, 2³¹ - 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

Basic Calculator IV

Hard

Intuit

0 views

Topics:

StringsStacks

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³¹, 2³¹ - 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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible values and data types of the constants/variables in the `evalvars` list and their corresponding values in the `evalints` list? Are negative numbers, zero, or floating-point numbers possible?
What characters, besides digits, '+', '-', '*', '/', '(', ')', ' ', and lowercase English letters representing variables, can appear in the expression string? Is the input expression always syntactically valid?
If the expression contains division, should I assume integer division? What happens if division by zero occurs?
If the expression simplifies to a constant, should the output list contain the variable "1" with the constant as its value? Or should the list be empty?
What is the expected output format for variables in the final expression? Should they be sorted alphabetically, combined if possible, or is the order not important?

Brute Force Solution

Approach

The basic idea is to try every single possibility for what each variable in the expression could be. Then, with each possible combination of variable values, we evaluate the expression and see if it leads to a valid simplified form. This is extremely inefficient, but it explores the entire solution space.

Here's how the algorithm would work step-by-step:

Start by considering every possible value for each variable that appears in the expression.
Create every possible combination of these variable values. Imagine a giant table where each row is a different set of values for all variables.
For each combination of variable values, substitute them into the expression.
Evaluate the expression with those specific values. This means performing all the additions, subtractions, multiplications, etc. using the substituted numbers.
If the result of the evaluation is a number, keep track of the variable combination and the resulting number.
After trying all combinations, collect all the simplified expressions that resulted in numeric values and all expressions with unresolved variables.
If we wanted to simplify further, we could apply simplification rules exhaustively like combining similar polynomial terms in every possible way.

Code Implementation

def basic_calculator_iv_brute_force(expression, variables, values):
    all_possible_combinations = [
        dict(zip(variables, combination)) 
        for combination in generate_combinations(values, len(variables))
    ]

    numeric_results = []
    unresolved_expressions = []

    for variable_assignments in all_possible_combinations:
        evaluated_result = evaluate_expression(
            expression, variable_assignments
        )

        if isinstance(evaluated_result, (int, float)):
            numeric_results.append(evaluated_result)
        else:
            unresolved_expressions.append(evaluated_result)

    # No real simplification as its the 'brute force' approach
    return numeric_results, unresolved_expressions

def generate_combinations(value_sets, num_variables):
    if num_variables == 0:
        return [{}]

    if not value_sets:
        return []

    # Build the combinations recursively. Each possible value becomes an option to consider
    remaining_value_sets = value_sets[0]
    sub_combinations = generate_combinations(value_sets[1:], num_variables - 1)
    all_combinations = []

    for value in remaining_value_sets:
        for sub_combination in sub_combinations:
            new_combination = sub_combination.copy()
            new_combination[len(value_sets) - num_variables] = value
            all_combinations.append(new_combination)

    return all_combinations

def evaluate_expression(expression_string, variable_assignments):
    try:
        # Attempt evaluation. The goal is to simulate full expression substitution
        substituted_expression = expression_string
        for variable_name, variable_value in variable_assignments.items():
            substituted_expression = substituted_expression.replace(
                variable_name, str(variable_value)
            )
        result = eval(substituted_expression)
        return result
    except:
        return expression_string

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(V^N) – The provided solution explores every possible combination of variable values. Let V be the number of possible values for each variable and N be the number of unique variables in the expression. We are essentially generating all possible assignments of values to variables. Since each of the N variables can take on V values, we have V choices for the first variable, V choices for the second variable, and so on. Thus the time complexity grows exponentially with the number of variables and the size of the domain of each variable, resulting in O(V^N).

Space Complexity

O(V^K) – The algorithm considers every possible combination of values for each variable. If there are V possible values for each variable and K variables in the expression, the total number of combinations is V^K. To store these combinations and their corresponding evaluated results (either numbers or simplified expressions), the auxiliary space will grow proportionally to the number of combinations. Therefore, the space complexity to store these intermediate values is O(V^K).

Optimal Solution

Approach

This problem requires us to evaluate a complex expression string that might contain variables. The optimal approach involves converting the expression into a structured form that a computer can understand and then using the rules of algebra to simplify it step by step, substituting in the known values of variables as you go.

Here's how the algorithm would work step-by-step:

First, we need to break down the expression string into smaller parts, like numbers, variables, and operations (+, -, *). Think of it like parsing a sentence into words and grammar.
Then, we convert this sequence into a 'reverse polish notation' or RPN. It is a special way to order the parts of the expression that makes it easier for a computer to calculate. Imagine rearranging a sentence so the important action words come last.
Now, we evaluate the RPN expression. When we encounter a number, we keep track of it. When we encounter a variable, we substitute in its known value (if we have one).
When we encounter an operation (+, -, *), we take the previous two things we kept track of, perform the operation, and then keep track of the result.
Important! Since the expression can contain both numbers and variables, the results can be more complex than simple numbers. They might be a combination of numbers and variables, like '2*x + 3*y + 5'. We need to handle these combinations correctly using the rules of algebra.
Keep doing the steps above until we've processed the entire RPN expression. The last thing we are keeping track of is the final result.
Finally, we simplify the final result by combining any similar terms (like adding all the 'x' terms together). This gives us the most concise answer.

Code Implementation

class Solution:
    def basicCalculatorIV(self, expression, evalvars, evalints):
        variable_map = dict(zip(evalvars, evalints))

        def tokenize(expression_string):
            tokens = []
            current_number = ""
            for character in expression_string:
                if character.isdigit():
                    current_number += character
                elif character.isalpha():
                    if current_number:
                        tokens.append(current_number)
                        current_number = ""
                    tokens.append(character)
                elif character in ["+", "-", "*", "(", ")"]:
                    if current_number:
                        tokens.append(current_number)
                        current_number = ""
                    tokens.append(character)
                elif character == " ":
                    if current_number:
                        tokens.append(current_number)
                        current_number = ""
                else:
                    pass
            if current_number:
                tokens.append(current_number)
            return tokens

        def to_rpn(tokens):
            precedence = {"+": 1, "-": 1, "*": 2}
            output_queue = []
            operator_stack = []

            for token in tokens:
                if token.isdigit() or token.isalpha():
                    output_queue.append(token)
                elif token in ["+", "-", "*"]:
                    while operator_stack and operator_stack[-1] in ["+", "-", "*"] and precedence[token] <= precedence[operator_stack[-1]]:
                        output_queue.append(operator_stack.pop())
                    operator_stack.append(token)
                elif token == "(":
                    operator_stack.append(token)
                elif token == ")":
                    while operator_stack and operator_stack[-1] != "(":
                        output_queue.append(operator_stack.pop())
                    operator_stack.pop()
            while operator_stack:
                output_queue.append(operator_stack.pop())
            return output_queue

        def evaluate_rpn(rpn_tokens, variable_map):

            stack = []

            def evaluate_operation(operand1, operand2, operator):
                if isinstance(operand1, dict) and isinstance(operand2, dict):
                    result = {}
                    for poly1, coef1 in operand1.items():
                        for poly2, coef2 in operand2.items():
                            new_poly = tuple(sorted(poly1 + poly2))
                            result[new_poly] = result.get(new_poly, 0) + coef1 * coef2
                elif isinstance(operand1, dict) and isinstance(operand2, int):
                    result = {}
                    for poly1, coef1 in operand1.items():
                        result[poly1] = coef1 * operand2
                elif isinstance(operand1, int) and isinstance(operand2, dict):
                    result = {}
                    for poly2, coef2 in operand2.items():
                        result[poly2] = coef2 * operand1
                else:
                    if operator == '+':
                        result = operand1 + operand2
                    elif operator == '-':
                        result = operand1 - operand2
                    elif operator == '*':
                        result = operand1 * operand2
                    else:
                        result = 0
                return result

            for token in rpn_tokens:
                if token.isdigit():
                    stack.append(int(token))
                elif token.isalpha():
                    if token in variable_map:
                        stack.append(variable_map[token])
                    else:
                        stack.append({(token,): 1})
                elif token in ["+", "-", "*"]:
                    operand2 = stack.pop()
                    operand1 = stack.pop()
                    result = evaluate_operation(operand1, operand2, token)
                    stack.append(result)

            return stack[0]

        def simplify(polynomial):
            if isinstance(polynomial, int):
                return [str(polynomial)]

            simplified = []
            terms = []
            for poly, coef in polynomial.items():
                if coef != 0:
                    terms.append((poly, coef))

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

            for poly, coef in terms:
                poly_str = "".join([s + "*" for s in poly])[:-1] if poly else "1"
                if coef == 1 and poly_str != "1":
                    simplified.append(poly_str)
                elif coef == -1 and poly_str != "1":
                    simplified.append("-" + poly_str)
                else:
                    simplified.append(str(coef) + "*" + poly_str)
            return simplified

        # Tokenize the input expression.
        tokens = tokenize(expression)

        # Convert tokens to Reverse Polish Notation.
        rpn = to_rpn(tokens)

        # Evaluate the RPN expression using variable mappings.
        result = evaluate_rpn(rpn, variable_map)

        # Simplify the polynomial result to the required format.
        simplified_result = simplify(result)

        return simplified_result

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^2) – Parsing the expression into tokens takes O(n) time, where n is the length of the expression. Converting to RPN also takes O(n) time. However, the critical operation that dominates the complexity is simplifying the polynomial result after evaluating the RPN expression. This simplification might involve combining like terms, which in the worst-case scenario (a polynomial with n terms, each potentially needing comparison with every other term) can take O(n^2) time. Therefore, the overall time complexity is dominated by the polynomial simplification step, resulting in O(n^2).

Space Complexity

O(N) – The algorithm's space complexity is primarily determined by the size of the RPN expression and the intermediate results stored during evaluation. The RPN conversion can, in the worst case, require storage proportional to the length of the input expression string (N). Furthermore, the 'keeping track' of numbers and variables during RPN evaluation, as well as the final result, may also grow linearly with N, particularly if the expression contains many distinct variables or complex terms. Therefore, the overall auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Empty expression string	Return an empty list as there are no terms to evaluate.
Expression with only whitespace	Return an empty list after stripping whitespace since the expression is effectively empty.
Expression with only constants	Evaluate the constant expression and return a list containing the single constant term.
Variables not present in the 'evalvars' list	Treat these variables as zero or undefined, ensuring the expression still evaluates correctly.
Integer overflow during multiplication or addition	Use a larger data type (e.g., long) during calculations or check for overflow before performing the operation to avoid incorrect results.
Expression with very deeply nested parentheses	Ensure the parsing logic handles arbitrary nesting levels without exceeding stack limits or causing performance issues.
Repeated variable names within the 'evalvars' list	Use the last value encountered for each variable name in the 'evalvars' list since it would supersede any prior definitions.
Extremely large coefficients or exponents during symbolic manipulation	Implement techniques to simplify terms and reduce the size of coefficients and exponents to prevent memory exhaustion.