## Evaluate Dependent Variable Assignments ### Problem Implement `evaluate_assignments(expressions)`. Each input string assigns one variable to a sum of integer literals and other variables. Assignments may refer to variables defined later in the array. Evaluate every variable and return the results in the original assignment order. ### Function Contract ```text evaluate_assignments(expressions) -> evaluated ``` `evaluated` is a JSON array of `[variable_name, value]` pairs. Pair `i` must contain the variable assigned by `expressions[i]` and its final integer value. ### Expression Grammar - A variable name matches `[a-z][a-z0-9_]{0,31}`. - Each string has the form `variable = term + term + ...` with one or more terms. - A term is either a nonnegative decimal integer or a variable name. - ASCII spaces may appear around `=` and `+`; there are no other operators or parentheses. - Every variable is assigned exactly once. - Every referenced variable has an assignment somewhere in the input. - The dependency graph is acyclic, so every value is well defined. ### Examples ```text expressions = ["foo = bar + 5", "bar = 2", "abc = 3"] result = [["foo", 7], ["bar", 2], ["abc", 3]] ``` ```text expressions = ["g = abc + foo", "foo = bar + 5", "bar = 2", "abc = 3"] result = [["g", 10], ["foo", 7], ["bar", 2], ["abc", 3]] ``` ```text expressions = ["total=left+right+4", "right=6", "left=base+1", "base=2"] result = [["total", 13], ["right", 6], ["left", 3], ["base", 2]] ``` ### Requirements - `1 <= expressions.length <= 200,000`. - The total number of characters across all strings is at most `2,000,000`. - The total number of terms is at most `400,000`. - Every integer literal is at most `1,000,000,000`. - Every final value is at most `9,000,000,000,000,000`, so all arithmetic is exact in signed 64-bit integers and JavaScript safe integers. - Do not mutate `expressions`. - Target `O(C + V + E)` time and `O(C + V + E)` space, where `C` is the input character count, `V` the number of variables, and `E` the number of variable references. - An implementation must not rely on recursive call depth proportional to `V` when the language runtime has a shallow recursion limit. ```hint Do not trust input order A variable can depend on a line that appears later. Preserve output order separately from the order in which values become known. ``` ### Discussion Requirements 1. Explain why evaluating each line once from left to right fails on the second example. 2. Describe how memoized dependency evaluation or an equivalent topological method avoids repeated work. 3. Explain how to distinguish a numeric literal from a variable token without evaluating arbitrary code. 4. State how an iterative traversal can avoid stack overflow on a long dependency chain.