Implement a Rule Parser and Evaluator

Problem: Implement a Rule Parser and Evaluator Given a rule expression as a string and a runtime context (a mapping from variable names to values), implement a parser and evaluator that determines whether the rule evaluates to true or false under that context. You need to build: Parsing: Parse the rule string into an evaluatable structure (e.g., an AST). Evaluation: Evaluate the expression against the provided context and return a boolean. Note: The original post does not provide an exact grammar. This problem asks you to implement a typical boolean rule language that at minimum supports parentheses and logical operators, and can compare variables to constants. Supported Syntax (you may implement with the following conventions) Logical operators: AND, OR, NOT Parentheses: (, ) Comparison operators: ==, !=, >, >=, <, <= Operands: Variable names: alphanumeric/underscore identifiers such as age, country, is_active Literals: Integers such as 18 Strings in double quotes such as "US" Booleans: true / false I/O Implement: evaluate(rule: str, context: dict) -> bool Where: rule is the rule expression string context is a dict like { "age": 20, "country": "US", "is_active": True } Return a boolean result Constraints / Edge Cases 1 <= len(rule) <= 1e5 1 <= len(context) <= 1e5 Ignore extra whitespace Correctly handle parentheses and operator precedence (suggested: NOT > comparisons > AND > OR) If a referenced variable does not exist in context, treat it as false (or raise an error, but be consistent) Examples Example 1: rule: age >= 18 AND country == "US" context: { "age": 20, "country": "US" } output: true Example 2: rule: NOT (country == "US" OR country == "CA") context: { "country": "FR" } output: true Example 3: rule: is_active == true AND age < 30 context: { "is_active": false, "age": 25 } output: false Example Input age >= 18 AND country == "US" age=20 country="US" Output true