py-05-calc

# Arithmetic Expression Evaluator

Implement a file **`solution.py`** containing a function:

```python
def evaluate(expr: str) -> float:
    ...
```

Evaluate an arithmetic expression given as a string and return its value as a
`float`.

Supported syntax:

- Binary operators `+`, `-`, `*`, `/` with standard precedence
  (`*` and `/` bind tighter than `+` and `-`) and left-to-right associativity.
- Parentheses `(` ... `)` for grouping.
- Unary plus and minus, e.g. `-3`, `-(2 + 1)`, `2 * -3`.
- Integer and float literals, e.g. `42`, `3.14`, `.5`, `10.`.
- Arbitrary surrounding / internal whitespace, which is ignored.

Requirements:

- Return the numeric result as a `float`. For example
  `evaluate("1 + 2 * 3") == 7.0` and `evaluate("(1 + 2) * 3") == 9.0`.
- Implement a real parser/evaluator that respects precedence and parentheses.
  **Do not** use `eval`, `exec`, or similar (the harness may inspect for this).
- Raise `ValueError` on malformed input. Malformed includes: empty / whitespace-only
  input, unbalanced parentheses, a missing operand or operator (e.g. `"1 +"`,
  `"1 2"`, `"* 3"`), and unexpected characters.
- Division by zero should raise an error (a `ZeroDivisionError` or `ValueError`
  is acceptable).

Examples:

```python
evaluate("2 + 3 * 4")      # 14.0
evaluate("(2 + 3) * 4")    # 20.0
evaluate("10 / 4")         # 2.5
evaluate("-3 + 2")         # -1.0
evaluate("2 * (1 + -1.5)") # -1.0
```

import pytest

from solution import evaluate


def test_simple_addition():
    assert evaluate("1 + 2") == 3.0


def test_precedence():
    assert evaluate("2 + 3 * 4") == 14.0
    assert evaluate("1 + 2 * 3") == 7.0


def test_parentheses_override_precedence():
    assert evaluate("(2 + 3) * 4") == 20.0
    assert evaluate("(1 + 2) * 3") == 9.0


def test_division_is_float():
    assert evaluate("10 / 4") == 2.5
    assert isinstance(evaluate("4 / 2"), float)


def test_unary_minus():
    assert evaluate("-3 + 2") == -1.0
    assert evaluate("2 * -3") == -6.0
    assert evaluate("-(2 + 1)") == -3.0


def test_float_and_whitespace():
    assert evaluate("  3.14 + .86 ") == pytest.approx(4.0)
    assert evaluate("10. / 4") == 2.5


def test_left_associativity():
    assert evaluate("10 - 2 - 3") == 5.0
    assert evaluate("100 / 5 / 2") == 10.0


def test_nested_parens():
    assert evaluate("2 * (1 + (3 - 1) * 2)") == 10.0


def test_malformed_raises_value_error():
    for bad in ["", "   ", "1 +", "* 3", "1 2", "(1 + 2", "1 + 2)", "1 + * 2", "3 $ 4"]:
        with pytest.raises(ValueError):
            evaluate(bad)


def test_division_by_zero_raises():
    with pytest.raises((ValueError, ZeroDivisionError)):
        evaluate("1 / 0")

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
from typing import List, Tuple

def tokenize(expr: str) -> List[str]:
    """Tokenize the expression string into a list of tokens."""
    tokens = []
    i = 0
    n = len(expr)
    
    while i < n:
        c = expr[i]
        
        # Skip whitespace
        if c.isspace():
            i += 1
            continue
        
        # Check for number (integer or float)
        if c.isdigit() or c == '.':
            j = i
            has_dot = False
            while j < n and (expr[j].isdigit() or expr[j] == '.'):
                if expr[j] == '.':
                    if has_dot:
                        raise ValueError("Multiple dots in number")
                    has_dot = True
                j += 1
            
            # Validate number format
            if j == i:
                raise ValueError("Invalid number format")
            
            # Must have at least one digit
            if not any(expr[k].isdigit() for k in range(i, j)):
                raise ValueError("Invalid number format")
            
            tokens.append(expr[i:j])
            i = j
            continue
        
        # Check for operators and parentheses
        if c in '+-*/()':
            tokens.append(c)
            i += 1
            continue
        
        # Unknown character
        raise ValueError(f"Unexpected character: '{c}'")
    
    return tokens


class Parser:
    def __init__(self, tokens: List[str]):
        self.tokens = tokens
        self.pos = 0
    
    def current(self) -> str:
        if self.pos < len(self.tokens):
            return self.tokens[self.pos]
        return None
    
    def consume(self) -> str:
        token = self.current()
        self.pos += 1
        return token
    
    def parse(self) -> float:
        result = self.parse_expression()
        if self.pos < len(self.tokens):
            raise ValueError("Unexpected token at end of expression")
        return result
    
    def parse_expression(self) -> float:
        """Parse addition and subtraction (lowest precedence)."""
        left = self.parse_term()
        
        while self.current() in ('+', '-'):
            op = self.consume()
            right = self.parse_term()
            if op == '+':
                left = left + right
            else:
                left = left - right
        
        return left
    
    def parse_term(self) -> float:
        """Parse multiplication and division (higher precedence)."""
        left = self.parse_unary()
        
        while self.current() in ('*', '/'):
            op = self.consume()
            right = self.parse_unary()
            if op == '*':
                left = left * right
            else:
                if right == 0:
                    raise ZeroDivisionError("Division by zero")
                left = left / right
        
        return left
    
    def parse_unary(self) -> float:
        """Parse unary plus and minus."""
        if self.current() == '-':
            self.consume()
            return -self.parse_unary()
        elif self.current() == '+':
            self.consume()
            return self.parse_unary()
        else:
            return self.parse_primary()
    
    def parse_primary(self) -> float:
        """Parse primary expressions: numbers and parenthesized expressions."""
        token = self.current()
        
        if token is None:
            raise ValueError("Unexpected end of expression")
        
        if token == '(':
            self.consume()
            result = self.parse_expression()
            if self.current() != ')':
                raise ValueError("Missing closing parenthesis")
            self.consume()
            return result
        elif token == ')':
            raise ValueError("Unexpected closing parenthesis")
        elif token in ('+', '-', '*', '/'):
            raise ValueError(f"Unexpected operator: {token}")
        else:
            # It's a number
            self.consume()
            try:
                return float(token)
            except ValueError:
                raise ValueError(f"Invalid number: {token}")


def evaluate(expr: str) -> float:
    """Evaluate an arithmetic expression string and return the result as float."""
    if not expr or expr.isspace():
        raise ValueError("Empty or whitespace-only expression")
    
    tokens = tokenize(expr)
    if not tokens:
        raise ValueError("Empty or whitespace-only expression")
    
    parser = Parser(tokens)
    return parser.parse()
```

The task is to implement an arithmetic expression evaluator that:
1. Supports +, -, *, / with standard precedence (* and / bind tighter than + and -)
2. Supports parentheses for grouping
3. Supports unary plus and minus
4. Supports integer and float literals (including .5, 10.)
5. Handles whitespace
6. Raises ValueError on malformed input
7. Raises ZeroDivisionError on division by zero
8. Cannot use eval/exec

I'll implement a proper parser using the shunting-yard algorithm or recursive descent parsing. Recursive descent is cleaner for this case.

Let me design the parser:

1. Tokenize the input string into tokens (numbers, operators, parentheses)
2. Parse using recursive descent with proper precedence handling

For precedence:
- Level 1: +, - (lowest)
- Level 2: *, / (higher)
- Unary operators need special handling

Let me write a recursive descent parser:

```python
def evaluate(expr: str) -> float:
    # Tokenize
    tokens = tokenize(expr)
    
    # Parse
    pos = [0]  # Use list to allow modification in nested functions
    parser = Parser(tokens)
    result = parser.parse_expression()
    
    # Check if all tokens were consumed
    if pos[0] < len(tokens):
        raise ValueError("Unexpected token at end of expression")
    
    return result
```

For the tokenizer, I need to handle:
- Numbers (integers and floats, including .5, 10.)
- Operators: +, -, *, /
- Parentheses: (, )
- Whitespace (skip)

For the parser, I'll use recursive descent:
- parse_expression() handles + and - (lowest precedence)
- parse_term() handles * and / (higher precedence)
- parse_unary() handles unary + and -
- parse_number() handles numeric literals

Let me implement this step by step:


```python
def tokenize(expr: str) -> List[str]:
    tokens = []
    i = 0
    while i < len(expr):
        c = expr[i]
        
        # Skip whitespace
        if c.isspace():
            i += 1
            continue
        
        # Check for number
        if c.isdigit() or c == '.':
            j = i
            has_dot = False
            while j < len(expr) and (expr[j].isdigit() or expr[j] == '.'):
                if expr[j] == '.':
                    if has_dot:
                        raise ValueError("Multiple dots in number")
                    has_dot = True
                j += 1
            
            # Check if we have a valid number
            if j == i or (j == i + 1 and not expr[i].isdigit()):
                # This is just a dot, which is invalid
                raise ValueError("Invalid number format")
            
            tokens.append(expr[i:j])
            i = j
            continue
        
        # Check for operators and parentheses
        if c in '+-*/()':
            tokens.append(c)
            i += 1
            continue
        
        # Unknown character
        raise ValueError(f"Unexpected character: {c}")
    
    return tokens
```

I'm realizing the number parsing needs more careful handling. The current approach might not correctly identify all valid number formats. I need to ensure I'm capturing numbers like `.5` and `10.` correctly while preventing invalid formats.

The key challenge is distinguishing between valid number formats and invalid ones. I'll need to add more robust validation to ensure only legitimate numeric tokens are created.

My next step is to refine the number parsing logic to handle edge cases more precisely.