Evaluate arithmetic expression with variables

Implement an expression evaluator for a string expr containing non-negative integers, variables (alphabetic names), operators +, -, , /, parentheses '()' and spaces. Given a dictionary mapping variable names to integer values, compute the signed 64-bit result using standard operator precedence (/ before +-), left-to-right associativity, and support unary +/-. Division truncates toward zero. The evaluator must run in O(L) time where L is the length of expr and use O(L) extra space. Return an error for invalid tokens or mismatched parentheses. Follow-ups: extend to exponentiation '^' (right-associative) and a function max(a,b).

Evaluate Arithmetic Expression with Variables

Implement an expression evaluator. You are given a string expr containing non-negative integers, variables (alphabetic names), the operators + - * /, parentheses (), and spaces, together with a dictionary variables mapping each variable name to an integer value.

Compute and return the result as a signed 64-bit integer using:

• Standard operator precedence: * and / bind tighter than + and -.
• Left-to-right associativity for operators of equal precedence.
• Unary + and - (e.g. -a + 5, +-+5).
• Integer division that truncates toward zero (so -7 / 2 == -3, not -4).
• Spaces may appear anywhere and are ignored.

The evaluator must run in O(L) time and O(L) extra space, where L is the length of expr.

If the expression is invalid — an unknown variable, an invalid token, a trailing/dangling operator, or mismatched parentheses — return the string "ERROR" instead of a number.

Return type: the integer result on success, or the string "ERROR" on any invalid input.

Follow-ups to discuss (not graded here): add right-associative exponentiation ^, and a two-argument function max(a, b).

Constraints

• 0 <= len(expr) <= 10^5
• Integer operands are non-negative; the final result fits in a signed 64-bit integer (wrap on overflow).
• Variable names are non-empty alphabetic strings; values are integers.
• Division truncates toward zero (e.g. -7 / 2 = -3).
• Invalid input (unknown variable, invalid token, dangling operator, mismatched parentheses) returns the string "ERROR".

Examples

Example 1

Input: ('a + b * 2', {'a': 3, 'b': 4})
Output: 11

Explanation: b*2 = 8 binds before +, then a + 8 = 11 (precedence).

Example 2

Input: ('(a + b) * 2', {'a': 3, 'b': 4})
Output: 14

Explanation: Parentheses force (3+4)=7 first, then 7*2 = 14.

Hints

1. Use recursive descent with three precedence levels: parse_expr handles + and -, parse_term handles * and /, and parse_factor handles unary signs, parentheses, numbers, and variables.
2. Track a single index into the string and a skip_spaces helper so whitespace never reaches the operator logic.
3. For truncate-toward-zero division, compute abs(a) // abs(b) and negate when the operand signs differ — Python's // floors toward negative infinity, which gives the wrong answer for negatives.
4. After the top-level parse, if the index hasn't reached the end of the string the input had trailing garbage — return ERROR.