Evaluate Ordered Variable Definitions with Addition and Subtraction

Evaluate a requested variable from an ordered list of definitions. A definition may be a number, a reference to an earlier variable, or an expression containing addition and subtraction.

Implement evaluate_definitions(definitions: string[], target: string) -> int.

Constraints & Assumptions

The report emphasizes an implicit directional and ordered-definition assumption. This practice contract makes it explicit: every variable is defined exactly once, and every reference on a right-hand side refers to an earlier definition. Definitions are assignments, not symmetric equations to solve. There are no cycles, forward references, or multiple definitions.

• Between 1 and 10000 definitions; target is defined.
• Variable names match [a-z][a-z0-9]*.
• Grammar: name = term ((+|-) term)*; a term is a variable name or an unsigned decimal integer. Optional ASCII spaces may surround tokens. Unary signs, parentheses, multiplication, and division are excluded.
• Terms are evaluated left to right. Literal values, intermediate results, and final results fit signed 32-bit integers; negative results are allowed.
• Total input length is at most 200000 characters.

The first reported part permits one term per definition. The full function also handles the reported plus/minus extension.

Examples

definitions = ["x1=1","x2=x1","x3=x2+x1","x4=x3-5"]
target = "x4"
result = -3

definitions = ["a=8","b=a","c=a","d=b-c"]
target = "d"
result = 0

Explain why a symbol table is sufficient under this contract and why input such as x1=x2; x1=1; query x2 violates it. Discuss how forward references, conflicting assignments, or truly symmetric equations would change the problem before choosing a different data structure.

Hint: Direction matters

A definition gives a value to its left-hand name. The ordering guarantee tells you whether every referenced value is already available.

Evaluate Ordered Variable Definitions

Approach

Process assignments in their given order and store each computed value in a symbol table. Remove optional spaces, separate the left name from the expression, and scan maximal terms separated by plus or minus. A term beginning with a digit is a decimal literal; otherwise read its previously stored value. Apply each operator in order. By induction, all earlier names already have their correct values, so every term resolves immediately and the new assignment is correct. The target can then be looked up directly. Java and C++ use wider temporaries so negating an allowed -2147483648 variable during subtraction cannot overflow an intermediate machine operation. The contract guarantees the actual expression values fit 32 bits. The sequence x1=x2; x1=1; query x2 violates both earlier-reference and single-definition guarantees and never defines x2. Forward references would require dependency scheduling or recursive evaluation with cycle checks. Conflicting assignments require a conflict or update policy. Symmetric equations would need equation-solving semantics and could have zero, one, or many solutions; a symbol table alone would not establish them. Let L be total input length. Token scanning and expected hash lookups take O(L) including token characters; stored variable names plus a temporary expression use O(L) space.

• Time complexity: O(L) expected, where L is total definition length
• Space complexity: O(L) including stored names and temporary parsing strings