Evaluate dependent variable expressions

Question

Given a target variable name and a list of assignment strings of the form 'Ti = expression' where the expression is either a number, a single variable, or arithmetic (+, −) over variables/numbers, compute the numeric value of the target variable. Extend to handle expressions that reference other variables recursively; detect cycles or unsolvable references and report an error.

Evaluate Dependent Variable Expressions

You are given a target variable name and a list of assignment strings of the form 'name = expression'. Each expression consists only of integer literals and variable names combined using '+' and '-' with optional whitespace; no parentheses or other operators exist. A unary '+' or '-' may precede any term. Variable names match [A-Za-z_][A-Za-z0-9_]* and are case-sensitive. Evaluate the target variable by recursively resolving dependencies. If a variable is assigned multiple times, the last assignment takes precedence. Return the integer value of the target if it can be computed. Return 'ERROR' if there is a cyclic dependency, if the target or any referenced variable is undefined, or if an expression is syntactically invalid.

Constraints

• 1 <= len(assignments) <= 10^4
• Total length of all assignment strings <= 2 * 10^5
• Variable names match [A-Za-z_][A-Za-z0-9_]*
• Expressions contain only integers, variable names, '+', '-', and spaces; no parentheses
• A leading '+' or '-' may appear before any term (number or variable)
• If a variable is assigned multiple times, the last assignment is used
• Return 'ERROR' on cyclic dependencies or undefined variables

Examples

Example 1

Input: target = "T3", assignments = ["T1 = 5", "T2 = T1 + 3", "T3 = T2 - T1 + 10"]
Output: 13

Explanation: T1 = 5; T2 = 5 + 3 = 8; T3 = 8 - 5 + 10 = 13.

Example 2

Input: target = "A", assignments = ["A = B + 1", "B = A + 2"]
Output: ERROR

Explanation: A depends on B and B depends on A, forming a cycle.

Hints

1. Parse assignments into a map from variable name to its expression; let the last occurrence win.
2. Use DFS with memoization to evaluate each variable once; keep a 'visiting' set to detect cycles.
3. Scan expressions character-by-character: read optional '+'/'-' signs to determine the term's sign, then read either an integer literal or a variable name.

Approach

Build a map from variable names to their expressions (last assignment wins). Evaluate the target using DFS with memoization: to compute a variable, parse and evaluate its expression. During evaluation, when encountering another variable, recursively evaluate it. Maintain a 'visiting' set of variables currently in the recursion stack to detect cycles. The expression parser scans characters, accumulates optional leading '+'/'-' signs as a multiplier, then reads either an integer literal or a variable name. Any reference to an undefined variable or the presence of a cycle raises an error, causing the function to return 'ERROR'.

• Time complexity: O(A + L), where A is the number of assignments and L is the total length of all expressions (each variable evaluated once due to memoization).
• Space complexity: O(A) for the mapping, memoization, and recursion stack.