Expression Evaluator in Python

This challenge asks you to build a simple expression evaluator in Python. Expression evaluators are fundamental components in many applications, from scripting languages to calculators, and understanding how they work provides valuable insight into parsing and computation. Your evaluator should handle basic arithmetic operations and follow the order of operations (PEMDAS/BODMAS).

Problem Description

You are tasked with creating a Python function evaluate_expression(expression) that takes a string representing a mathematical expression as input and returns the result of evaluating that expression. The expression will consist of integers, the operators +, -, *, and /, and parentheses ( and ). The function should correctly parse the expression, respecting operator precedence (PEMDAS/BODMAS) and parentheses.

Key Requirements:

• Operator Precedence: Multiplication and division should be performed before addition and subtraction.
• Parentheses: Parenthesized expressions should be evaluated first.
• Integer Input: The expression will only contain integers and the specified operators.
• Error Handling: The function should raise a ValueError if the expression is invalid (e.g., unbalanced parentheses, division by zero, invalid characters).
• Floating-Point Division: Division (/) should result in floating-point numbers.

Expected Behavior:

The function should return the numerical result of the expression.

Edge Cases to Consider:

• Empty expression string.
• Expression with only a single number.
• Nested parentheses.
• Multiple consecutive operators (e.g., 2++3). These should raise a ValueError.
• Division by zero.
• Unbalanced parentheses.
• Invalid characters in the expression (anything other than digits, operators, and parentheses).

Examples

Example 1:

Input: "2 + 3 * 4"
Output: 14.0
Explanation: Multiplication is performed before addition (3 * 4 = 12, then 2 + 12 = 14).

Example 2:

Input: "(2 + 3) * 4"
Output: 20.0
Explanation: The expression inside the parentheses is evaluated first (2 + 3 = 5, then 5 * 4 = 20).

Example 3:

Input: "10 / 2 - 1"
Output: 4.0
Explanation: Division is performed before subtraction (10 / 2 = 5, then 5 - 1 = 4).

Example 4:

Input: "(1 + (4 + 5 + 2) - 3) + (6 + 8)"
Output: 23.0
Explanation: Demonstrates nested parentheses and multiple operations.

Example 5:

Input: "10 / 0"
Output:
ValueError: Division by zero
Explanation:  Division by zero should raise a ValueError.

Example 6:

Input: "(2 + 3"
Output:
ValueError: Unbalanced parentheses
Explanation: Unbalanced parentheses should raise a ValueError.

Constraints

• The input expression string will have a length between 1 and 100 characters.
• All numbers in the expression will be non-negative integers.
• The expression will only contain the characters 0-9, +, -, *, /, (, and ).
• The function should execute in O(n) time complexity, where n is the length of the expression string. While a perfect O(n) solution is challenging without advanced techniques, strive for efficiency.
• The function must raise a ValueError for invalid expressions as described above.

Notes

• Consider using a stack-based approach to handle operator precedence and parentheses.
• You may find it helpful to tokenize the expression string first.
• Remember to handle potential errors gracefully.
• Testing with a variety of expressions, including edge cases, is crucial to ensure correctness.
• While regular expressions could be used, a more manual parsing approach is generally preferred for this type of problem to better understand the underlying logic.