Esercizio 8controllo delle parentesi con una pila

Idea

Le parentesi aperte "attendono" di essere chiuse nell'ordine inverso a quello di apertura: l'ultima aperta deve essere la prima chiusa. È esattamente il comportamento LIFO di una pila.

Si scorre la stringa carattere per carattere:

• parentesi aperta (, [, { → push;
• parentesi chiusa → la pila non deve essere vuota (altrimenti c'è una chiusa senza aperta) e il carattere estratto con pop deve essere dello stesso tipo; altrimenti l'uso è scorretto;
• qualunque altro carattere → ignorato;
• a fine stringa la pila deve essere vuota (nessuna parentesi rimasta aperta).

Una tabella chiusa → aperta corrispondente evita una serie di if.

Traccia su 4*{2/(6-4)+1]/8}:

Per 4*{[2/(6-4)+1]/8} la pila si svuota esattamente alla } finale. Altri casi che il programma deve gestire: ( (resta aperta: pila non vuota), ) (chiusa a pila vuota), ([)] (annidamento incrociato), la stringa vuota (corretta).

Python

COPPIE = {")": "(", "]": "[", "}": "{"}       # chiusa -> aperta corrispondente

def parentesi_ok(espr):
    pila = []                                  # lista usata come pila: append e pop
    for c in espr:
        if c in "([{":
            pila.append(c)
        elif c in COPPIE:
            if not pila or pila.pop() != COPPIE[c]:   # vuota, oppure tipo diverso
                return False
    return not pila                            # nessuna parentesi rimasta aperta


if __name__ == "__main__":
    espr = input()                             # una riga dallo standard input
    print("uso corretto delle parentesi" if parentesi_ok(espr) else "uso NON corretto delle parentesi")

Con l'ingresso 4*{[2/(6-4)+1]/8} stampa uso corretto delle parentesi; con 4*{2/(6-4)+1]/8} stampa uso NON corretto delle parentesi.

Il not pila or pila.pop() != ... sfrutta il cortocircuito: pila.pop() su una lista vuota solleverebbe IndexError, ma non viene eseguito se not pila è vero (Logica booleana e istruzione ifValori di verità, operatori di confronto e logici con valutazione a corto circuito, leggi di De Morgan, truthiness; if/elif/else, espressione condizionale e match.Logica booleana e istruzione if →).

C

In C non c'è una pila predefinita: basta un array di char e un indice n (la cima è pila[n-1]). La capacità deve bastare per il numero di parentesi aperte contemporaneamente; qui 256, con controllo del riempimento.

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

/* true se le parentesi tonde, quadre e graffe di s sono bilanciate */
bool parentesi_ok(const char *s) {
    char pila[256];                       /* cima = pila[n-1] */
    size_t n = 0;
    for (; *s != '\0'; s++) {
        char c = *s;
        if (c == '(' || c == '[' || c == '{') {
            if (n == sizeof pila) return false;   /* troppo annidata per questa pila */
            pila[n++] = c;
        } else if (c == ')' || c == ']' || c == '}') {
            if (n == 0) return false;             /* chiusa senza aperta */
            char a = pila[--n];
            if ((c == ')' && a != '(') || (c == ']' && a != '[') || (c == '}' && a != '{'))
                return false;                     /* tipo sbagliato */
        }
    }
    return n == 0;                                /* non devono restare aperte */
}

int main(void) {
    char riga[512];
    if (fgets(riga, sizeof riga, stdin) == NULL) return 1;
    riga[strcspn(riga, "\n")] = '\0';
    puts(parentesi_ok(riga) ? "uso corretto delle parentesi" : "uso NON corretto delle parentesi");
    return 0;
}

Con echo '4*{[2/(6-4)+1]/8}' | ./parentesi stampa uso corretto delle parentesi; con 4*{2/(6-4)+1]/8} stampa uso NON corretto delle parentesi. fgets tiene il '\n', che si toglie con strcspn (vedi Input e output in Cprintf con larghezza e precisione, scanf con indirizzi e valore di ritorno, lettura di righe con fgets, file con FILE*, fopen, fclose, fprintf, fscanf, controllo degli errori e della fine del file.Input e output in C →).

Costo. Una passata sulla stringa, ogni carattere con operazioni $O(1)$: $O(n)$ tempo; la pila contiene al più $n$ caratteri: $O(n)$ spazio.

Verifica

casi = [("4*{[2/(6-4)+1]/8}", True), ("4*{2/(6-4)+1]/8}", False), ("", True),
        ("(", False), (")", False), ("([)]", False), ("((()))", True),
        ("a(b]c", False), ("{[()()]}", True), ("(()", False), ("())", False)]
for e, atteso in casi:
    assert parentesi_ok(e) == atteso, e
print("11 casi verificati")

Il programma C è stato compilato e provato sugli stessi esempi del testo (corretta, scorretta) e su ( e sulla riga vuota.

Errori comuni

• Contare soltanto le parentesi aperte e chiuse (un contatore): ([)] avrebbe lo stesso numero di aperte e chiuse ma è scorretta; serve la pila per ricordare il tipo e l'ordine.
• Non controllare che la pila sia vuota alla fine ((() verrebbe accettata).
• Fare pop su pila vuota quando arriva una chiusa per prima () da sola).
• In C, non togliere il '\n' o non limitare la profondità della pila.