Rust Compile-Time Expression Evaluator

This challenge involves building a simple, robust expression evaluator that operates entirely at compile time within Rust. This kind of engine is fundamental for enabling compile-time computations, such as defining complex constants, generating lookup tables, or performing optimizations that would otherwise require runtime execution.

Problem Description

Your task is to create a Rust library component that can evaluate a subset of arithmetic expressions represented as strings. The evaluator should be designed to be usable within a const fn context, meaning all computations must be resolvable at compile time.

Key Requirements:

• Supported Operations: Implement evaluation for addition (+), subtraction (-), multiplication (*), and division (/).
• Operator Precedence: Correctly handle operator precedence (multiplication and division before addition and subtraction).
• Parentheses: Support arbitrary nesting of parentheses for grouping expressions.
• Integer Arithmetic: All operations should be performed on signed 32-bit integers (i32).
• Compile-Time Execution: The evaluation logic must be implementable within Rust's const fn constraints, ensuring no runtime dependencies.
• Error Handling: Gracefully handle invalid input, such as division by zero, malformed expressions, or invalid tokens, by returning an appropriate error type.

Expected Behavior:

The evaluator will take a string representing an expression and return either the computed i32 result or a descriptive error.

Edge Cases to Consider:

• Expressions with only numbers.
• Expressions with only operators (should be an error).
• Expressions starting or ending with operators (should be an error).
• Consecutive operators (e.g., 2 + + 3) should be an error.
• Empty input string.
• Division by zero.
• Integer overflow (for simplicity in this challenge, we can assume standard i32 behavior, but a robust solution might explicitly handle this).
• Invalid characters within the expression.

Examples

Example 1:

Input: "1 + 2 * 3"
Output: Ok(7)
Explanation: Multiplication has higher precedence. 2 * 3 = 6. Then 1 + 6 = 7.

Example 2:

Input: "(1 + 2) * 3"
Output: Ok(9)
Explanation: Parentheses are evaluated first. 1 + 2 = 3. Then 3 * 3 = 9.

Example 3:

Input: "10 / (5 - 5)"
Output: Err("Division by zero")
Explanation: The expression inside the parentheses evaluates to 0, leading to division by zero.

Example 4:

Input: "5 * 2 + 8 / 4 - 1"
Output: Ok(11)
Explanation: Precedence: 5 * 2 = 10, 8 / 4 = 2. Then: 10 + 2 - 1 = 11.

Example 5:

Input: "((2 + 3) * (4 - 1)) / 3"
Output: Ok(5)
Explanation: Innermost parentheses first: (2+3)=5, (4-1)=3. Then: (5 * 3) / 3 = 15 / 3 = 5.

Example 6:

Input: "1 + "
Output: Err("Malformed expression: unexpected end of input")
Explanation: The expression is incomplete.

Constraints

• The input expression string will contain only digits (0-9), the operators +, -, *, /, and parentheses ( ). Whitespace may be present and should be ignored.
• The maximum length of the input expression string will be 256 characters.
• Intermediate and final results must fit within an i32.
• The evaluation engine must be implementable using const fn.

Notes

A common approach for expression evaluation involves parsing the expression into an Abstract Syntax Tree (AST) or using a stack-based algorithm (like the Shunting-Yard algorithm for conversion to Reverse Polish Notation, followed by RPN evaluation, or direct stack-based evaluation). Consider how to manage operator precedence and parentheses efficiently. The const fn constraint means you cannot use String::parse or standard library functions that are not themselves const. You'll likely need to implement custom parsing and tokenization logic. For error handling, define a clear enum that captures the different types of errors.