Python: risolvere un semplice esercizio di programmazione

In questo articolo vedremo una possibile soluzione ad un semplice esercizio di programmazione in Python.

Data una stringa s contenente solo i caratteri '(', ')', '{', '}', '[' e ']', stabilire se la stringa di input è valida.

Una stringa di input è valida se:

1. Le parentesi aperte devono essere chiuse dallo stesso tipo di parentesi.
2. Le parentesi aperte devono essere chiuse nell'ordine corretto.
3. Ogni parentesi chiusa ha una corrispondente parentesi aperta dello stesso tipo.

Esempio 1:

Input: s = "()"
Output: true

Esempio 2:

Input: s = "()[]{}"
Output: true

Esempio 3:

Input: s = "(]"
Output: false

La stringa di input non deve avere più di 104 caratteri e deve essere costituita solo dalle parentesi '()[]{}'.

Si tratta sostanzialmente di effettuare la scansione della stringa carattere per carattere tenendo traccia del carattere corrente e del carattere immediatamente successivo.

def is_valid(s = None):
    if s is None:
        return False
        
    length_s = len(s)
        
    if length_s == 0 or length_s > 104:
        return False
    allowed_chars = ['(', ')', '{', '}', '[', ']'] 
    valid = True

    for c in s:
        if not c in allowed_chars:
            valid = False
    i = 0
    while i < length_s:
        ch = s[i]
        next_i = i + 1
        next_ch = s[next_i] if next_i < length_s else None
        if not next_ch:
            break
        match ch:
            case '(':
                if next_ch != ')':
                    valid = False
            case '{':
                if next_ch != '}':
                    valid = False
            case '[':
                if next_ch != ']':
                    valid = False
            case _:
                break                        
        i += 1        
    return valid