🟡 String Algorithms: Valid Number

[stemaway]

Mathematics: Valid Number

Difficulty: Medium

---

Problem Statement

Validate if a given string can be interpreted as a valid decimal number.

Some examples of valid numbers:

• "0"
• " 0.1 "
• "2e10"
• "-90E3"
• "3.1416"
• "+6e-1"
• "53.5e93"
• "-123.456e789"

Examples of invalid numbers:

• "abc"
• "1a"
• "1e"
• "e3"
• "99e2.5"
• "--6"
• "-+3"
• "95a54e53"

---

Implementation Details

Implement the following function:

def is_number(s: str) -> bool:
    """
    Determine if the string s represents a valid decimal number.

    Args:
        s (str): The input string.

    Returns:
        bool: True if s is a valid number, False otherwise.
    """
    pass  # Your implementation here

Constraints

• String Length: (1 \leq \text{len(s)} \leq 20)
• String Content: s may contain spaces, digits (0-9), signs (+, -), decimal point (.), and exponent (e or E).

---

Example Usage

print(is_number("0"))          # Expected Output: True
print(is_number(" 0.1 "))      # Expected Output: True
print(is_number("abc"))        # Expected Output: False
print(is_number("1 a"))        # Expected Output: False
print(is_number("2e10"))       # Expected Output: True
print(is_number("-90E3"))      # Expected Output: True
print(is_number(" 6e-1"))      # Expected Output: True
print(is_number("99e2.5"))     # Expected Output: False
print(is_number("--6"))        # Expected Output: False
print(is_number("-+3"))        # Expected Output: False
print(is_number("95a54e53"))   # Expected Output: False

---

Test Cases

def test_is_number():
    # Test Case 1: Simple integer
    assert is_number("0") == True

    # Test Case 2: Decimal number
    assert is_number(" 0.1 ") == True

    # Test Case 3: Invalid with letters
    assert is_number("abc") == False

    # Test Case 4: Invalid space between number and letter
    assert is_number("1 a") == False

    # Test Case 5: Exponential notation
    assert is_number("2e10") == True

    # Test Case 6: Negative exponent
    assert is_number("-90E3") == True

    # Test Case 7: Leading and trailing spaces
    assert is_number(" 6e-1") == True

    # Test Case 8: Exponent with decimal point
    assert is_number("99e2.5") == False

    # Test Case 9: Double signs
    assert is_number("--6") == False

    # Test Case 10: Mixed signs
    assert is_number("-+3") == False

    # Test Case 11: Invalid letters in number
    assert is_number("95a54e53") == False

    # Test Case 12: Valid negative decimal
    assert is_number("-123.456e789") == True

    # Test Case 13: Empty string
    assert is_number("") == False

    # Test Case 14: Just a sign
    assert is_number("+") == False

    # Test Case 15: Dot without digits
    assert is_number(".") == False

    # Test Case 16: Leading/trailing spaces with valid number
    assert is_number("   .1  ") == True

    print("All test cases pass!")

---

Expected Solution Approach

This problem requires careful parsing of the input string, following the rules of valid decimal numbers.

Algorithm Steps

1. Trim Spaces:

   • Remove leading and trailing spaces from the string.

2. Check for Sign:

   • Optional + or - at the beginning.

3. Process Main Number Part:

   • Digits Before Decimal Point:
     • Zero or more digits.
   • Decimal Point:
     • Optional ..
   • Digits After Decimal Point:
     • Zero or more digits.
   • At least one digit must exist before or after the decimal point.

4. Process Exponent Part:

   • If an e or E is present:
     • Must have digits before e (i.e., cannot start with e).
     • Exponent can have an optional + or - sign.
     • Exponent must have at least one digit.

5. Ensure No Extra Characters:

   • After processing, ensure that all characters have been consumed.

Implementation Details

• Use indices to traverse the string.
• Validate each part step by step.
• Be cautious with edge cases like . without digits, multiple signs, or invalid placements of e.

Time Complexity

• Time Complexity: (O(N)), where (N) is the length of the string.
• Space Complexity: (O(1))

---

Implementation Hint

Here’s a skeleton to help you start:

def is_number(s: str) -> bool:
    s = s.strip()
    if not s:
        return False

    i = 0
    n = len(s)

    # Check sign
    if i < n and s[i] in ('+', '-'):
        i +=1

    is_numeric = False
    # Check digits before decimal point
    while i < n and s[i].isdigit():
        i +=1
        is_numeric = True

    # Check decimal point
    if i < n and s[i] == '.':
        i +=1
        # Check digits after decimal point
        while i < n and s[i].isdigit():
            i +=1
            is_numeric = True

    # Check exponent
    if is_numeric and i < n and s[i] in ('e', 'E'):
        i +=1
        if i < n and s[i] in ('+', '-'):
            i +=1
        is_exp_numeric = False
        while i < n and s[i].isdigit():
            i +=1
            is_exp_numeric = True
        if not is_exp_numeric:
            return False

    return is_numeric and i == n

---

Learning Objectives

1. Understand String Parsing Techniques:

   • Carefully process input strings character by character.
   • Handle optional and mandatory components.

2. Implement Finite State Machines:

   • Model parsing logic as a set of states and transitions.
   • Ensure correct transitions based on input characters.

3. Handle Complex Edge Cases:

   • Recognize ambiguous or tricky inputs.
   • Validate all possible valid and invalid formats.

4. Optimize for Efficiency:

   • Avoid unnecessary string operations or data structures.
   • Ensure constant space complexity.

---

Real-World Applications

• Input Validation: Ensure user inputs conform to expected numerical formats.
• Compiler Design: Parse and validate tokens in programming languages.
• Data Processing Pipelines: Validate numerical data before processing.
• Scientific Computing: Interpret and handle numbers in different notations (e.g., exponential).

---