开发科学计算器：数学表达式验证的阶段选择咨询

Hey there! Let's break down how to tackle input validation for your scientific calculator's infix expressions—since you already have the Shunting-Yard algorithm up and running, this is the next critical piece to make your tool robust and user-friendly. Below’s a deep dive into the three validation stage options you’re considering, plus pros, cons, and practical tips:

1. Validation During Tokenization #

• How it works: As you split the input string into tokens (numbers, operators, parentheses, functions like sin or log), validate each token as you build it.
  • Reject invalid characters (e.g., @, # that don’t belong to any supported token type).
  • Ensure numbers are well-formed (no multiple decimal points like 3.14.5, no empty or partial numbers like . or 5.).
  • Verify function names match your supported list (e.g., flag sine if you only recognize sin).
• Pros: Catches errors early, before you waste cycles on the Shunting-Yard process. You can give precise feedback like, "Invalid character '@' at position 4" to guide users.
• Cons: Can’t catch context-dependent issues (like mismatched parentheses or consecutive operators) since you’re only looking at individual tokens, not their sequence.

2. Validation After Tokenization, Before Shunting-Yard #

• How it works: Once you have a full list of valid tokens, run a separate pass to check the structural logic of the token sequence.
  • Count opening/closing parentheses to ensure balance and proper nesting.
  • Validate operator-operand order:
    • No leading operators (except unary minus/plus, like -5 or +3.2).
    • No consecutive operators unless one is unary (e.g., 3*-4 is okay, but 3++4 isn’t).
    • Ensure functions are immediately followed by an opening parenthesis (e.g., sin( instead of sin5).
    • Make sure the expression ends with an operand or closing parenthesis, not an operator.
• Pros: Separates tokenization logic from structural checks, keeping your code cleaner. You can catch all sequence-based errors in one go with targeted messages.
• Cons: You have to process the entire input first before flagging errors, but feedback can still be specific (e.g., "Mismatched parentheses: extra ')' at position 10").

3. Validation Integrated Into the Shunting-Yard Algorithm #

• How it works: Add validation checks directly into your existing Shunting-Yard logic as you process each token.
  • When pushing operators, confirm the previous token is a valid predecessor (e.g., don’t allow + right after another + unless it’s a unary case).
  • Track parenthesis balance in real time and flag mismatches immediately.
  • For functions, ensure an opening parenthesis follows before proceeding with the algorithm.
• Pros: No need for a separate validation pass—you validate and parse the expression in one step, which can be more efficient.
• Cons: Mixes parsing and validation logic, making your Shunting-Yard code more complex. Debugging edge cases might get trickier as you’re handling two jobs at once.

Bonus: Hybrid Approach (Most Robust) #

Most production calculators use a mix of these strategies to cover all bases:

• Do basic token validation during tokenization (catch invalid characters, malformed numbers).
• Run structural validation after tokenization (check parenthesis balance, operator order).
• Add lightweight checks in Shunting-Yard as a final safety net (in case any edge cases slipped through the first two passes).

Example Pseudocode Snippets #

Tokenization with Validation

def tokenize(input_str):
    tokens = []
    i = 0
    while i < len(input_str):
        c = input_str[i]
        if c.isspace():
            i += 1
            continue
        # Handle operators and parentheses
        if c in '+-*/^()':
            # Check for unary minus/plus
            if c in '+-' and (i == 0 or input_str[i-1] in '+-*/('):
                tokens.append(('UNARY_OP', c))
            else:
                tokens.append(('OP', c))
            i += 1
        # Handle numbers
        elif c.isdigit() or c == '.':
            num_str = c
            i += 1
            has_decimal = c == '.'
            while i < len(input_str) and (input_str[i].isdigit() or input_str[i] == '.'):
                if input_str[i] == '.' and has_decimal:
                    raise ValueError(f"Invalid number: multiple decimals at position {i}")
                if input_str[i] == '.':
                    has_decimal = True
                num_str += input_str[i]
                i += 1
            tokens.append(('NUMBER', float(num_str)))
        # Handle functions
        elif c.isalpha():
            func_str = c
            i += 1
            while i < len(input_str) and input_str[i].isalpha():
                func_str += input_str[i]
                i += 1
            if func_str not in ['sin', 'cos', 'tan', 'log', 'sqrt']:
                raise ValueError(f"Unknown function '{func_str}' at position {i - len(func_str)}")
            tokens.append(('FUNCTION', func_str))
        else:
            raise ValueError(f"Invalid character '{c}' at position {i}")
    return tokens

Post-Tokenization Structural Validation

def validate_tokens(tokens):
    if not tokens:
        raise ValueError("Empty expression")
    
    # Check leading token validity
    first_type = tokens[0][0]
    if first_type == 'OP' and tokens[0][1] not in '+-':
        raise ValueError(f"Expression can't start with operator '{tokens[0][1]}'")
    
    parenthesis_balance = 0
    for idx, (token_type, value) in enumerate(tokens):
        if token_type == 'OP':
            # Ensure operator is preceded by a valid token
            prev_type = tokens[idx-1][0]
            if prev_type in ['OP', 'FUNCTION', '(']:
                if value not in '+-' or prev_type not in ['(', 'FUNCTION']:
                    raise ValueError(f"Invalid operator placement at position {idx}")
        elif token_type == '(':
            parenthesis_balance += 1
        elif token_type == ')':
            parenthesis_balance -= 1
            if parenthesis_balance < 0:
                raise ValueError(f"Extra closing parenthesis at position {idx}")
        elif token_type == 'FUNCTION':
            # Ensure function is followed by (
            if idx + 1 >= len(tokens) or tokens[idx+1][0] != '(':
                raise ValueError(f"Function '{value}' must be followed by '(' at position {idx}")
    
    # Check for unclosed parentheses
    if parenthesis_balance != 0:
        raise ValueError(f"Mismatched parentheses: {parenthesis_balance} unclosed '('")
    
    # Check trailing token validity
    last_type = tokens[-1][0]
    if last_type in ['OP', 'FUNCTION', '(']:
        raise ValueError(f"Expression can't end with '{tokens[-1][1]}'")

内容的提问来源于stack exchange，提问作者carefulnow1