Practice/Google/Leetcode 770. Basic Calculator IV

Leetcode 770. Basic Calculator IV

CodingMust

Problem

Build a symbolic expression evaluator that handles arithmetic expressions containing integers, variables (multi-character identifiers), and the operators +, -, and *. The evaluator must:

1. Parse the expression respecting standard operator precedence (multiplication before addition/subtraction) and parentheses
2. Substitute provided variable values from a mapping
3. Expand all operations by distributing multiplication over addition/subtraction
4. Combine like terms (terms with identical variable sets) by summing their coefficients
5. Remove terms with zero coefficients
6. Return a canonical string representation

The expression string contains space-separated tokens. Variable assignments are given as strings in the format "variable=value".

Requirements

1. Parse and evaluate the expression with correct operator precedence

2. Handle parentheses for grouping operations

3. Substitute only the variables that appear in the evaluation map

4. Expand all products fully (e.g., (a+b)*c becomes a*c + b*c)

5. Combine terms with the same variables (e.g., 2*x + 3*x becomes 5*x)

6. Drop any terms whose coefficient becomes zero

7. Sort output terms by:

   • First, by degree (number of variables) in descending order
   • Then, lexicographically by variable sequence

8. Format each term as coefficient*var1*var2*... (or just coefficient for constants)

Constraints

• Expression length: 1 ≤ length ≤ 200
• Variable names consist of lowercase English letters only
• All intermediate and final coefficient values fit in a 32-bit signed integer
• The expression contains only valid tokens separated by single spaces
• Expected time complexity: O(n × m × k) where n is expression length, m is number of terms, k is term size
• Expected space complexity: O(m × k) for storing the expanded polynomial

Examples

Example 1:

Input: expression = "a + b", evalMap = ["a=5", "b=3"] Output: "8" Explanation: Both variables are substituted, resulting in 5+3=8

Example 2:

Input: expression = "x * y + z", evalMap = [] Output: "x*y+z" Explanation: No substitutions. Two terms: degree-2 term "x*y" comes before degree-1 term "z"

Example 3:

Input: expression = "(a + b) * (c + d)", evalMap = ["a=1"] Output: "b*c+b*d+c+d" Explanation: Expand (1+b)*(c+d) = c + d + b*c + b*d. Sort by degree then lexicographically: b*c, b*d (both degree 2), then c, d (degree 1)

Example 4:

Input: expression = "x - x", evalMap = [] Output: "0" Explanation: The terms cancel out, leaving only the constant 0