Parentesi Bilanciate¶

Consideriamo la seguente espressione aritmetica.

\((5+6)*(7+8)/(4+3)\)

Le parentesi sono usate per ordinare l’esecuzione delle operazioni. Le parentesi devono apparire in modo bilanciato. Parentesi bilanciate significa che ogni simbolo di apertura ha un corrispondente simbolo di chiusura e le coppie di parentesi sono correttamente annidate. Consideriamo la seguente stringa correttamente bilanciata di parentesi:

(()()()())

(((())))

(()((())()))

Confrontiamola con la seguente, che invece non è bilanciata:

((((((())

()))

(()()(()

L’abilità di riconoscere se le parentesi sono bilanciate o no è alla base del riconoscimento e esecuzione di molti linguaggi di programmazione.

La sfida è quindi quella di scrivere un algoritmo che legge una stringa di parentesi da sinistra verso destra e decide se i simboli sono bilanciati o no. Per risolvere questo problema dobbiamo fare alcune osservazioni. Dal momento che processiamo simboli da sinistra a destra, la prossima parentesi chiusa deve corrispondere alla parentesi aperta più recentemente (vedi Figura 4). Inoltre, il primo simbolo di apertura dovrebbe aspettare fino all’ultimo simbolo per trovare la corrispondenza. I simboli di chiusura corrispondono a simboli di apertura nell’ordine inverso di apparizione. Questo ci suggerisce che possiamo usare le pile per risolvere questo problema.

Figura 4: Trovare corrispondenze tra parentesi

Partendo da una pila vuota, processiamo le parentesi da sinistra verso destra. Se un simbolo è una parentesi aperta, lo mettiamo sulla pila come segnale che un simbolo di chiusura corrispondente deve apparire più tardi. Se il simbolo è una parentesi chiusa, facciamo pop sulla pila. Finché è possibile fare pop sulla pila per trovare una corrispondenza per il simbolo di chiusura, le parentesi rimangono bilanciate. Se a un certo punto non c’è un simbolo di apertura sulla pila che corrisponde al simbolo di chiusura che stiamo leggendo in quel momento, la stringa non ha le parentesi bilanciate. Alla fine della stringa, quando tutti i simboli sono stati processati, la pila deve essere vuota. Il codice Python per implementare questo algoritmo è mostrato in ActiveCode 1.

from pythonds.basic.stack import Stack

def parChecker(symbolString):
    s = Stack()
    balanced = True
    index = 0
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol == "(":
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                s.pop()

        index = index + 1

    if balanced and s.isEmpty():
        return True
    else:
        return False

print(parChecker('((()))'))
print(parChecker('(()'))

Soluzione del problema di riconoscere parentesi bilanciate (parcheck1)

Questa funzione, parChecker, assume che una classe Stack sia disponibile e restituisce un valore booleano. Notiamo che la variabile balanced è inizializzata a True. Se il simbolo corrente è (, allora questo viene messo sulla pila (linee 9–10). Notiamo anche che a riga 15 pop semplicemente rimuove un elemento dalla pila. Il valore ritornato non è più usato dal momento che sappiamo che è una parentesi aperta vista precedentemente. In conclusione, (linee 19–22), finché l’espressione è bilanciata e la pila è stata completamente pulita, la stringa rappresenta una sequenza bilanciata di parentesi.

Next Section - Il tipo di dato astratto Coda