0848 - Paranteze1

Cerința

Se dau n șiruri de paranteze rotunde. Să se stabilească, despre fiecare șir, dacă este corect parantezat – adică dacă parantezele se închid corect.

Un șir de paranteze S rotunde este corect parantezat dacă:

• S este șirul vid, sau
• S = (T) și T este corect parantezat, sau
• S = AB, iar A și B sunt corect parantezate.

Date de intrare

Fișierul de intrare paranteze1.in conține pe prima linie numărul n, pe următoarele n linii câte un șir de paranteze rotunde.

Date de ieșire

Fișierul de ieșire paranteze1.out va conține n linii: fiecare linie va conține valoarea 1, dacă șirul corespunzător de paranteze este corect parantezat și 0 în caz contrar.

Restricții și precizări

• 1 ≤ n ≤ 100
• fiecare șir va avea cel mult 255 de paranteze

Exemplu:

paranteze1.in

4

(())

)(()

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

()(

paranteze1.out

1

0

1

0

Rezolvare

<syntaxhighlight lang="python" line="1" start="1">

1. Functia care verifica daca un sir de paranteze este corect parantezat

def este_corect_parantezat(s):

   # Initializam o stiva goala
   stiva = []
   # Parcurgem fiecare paranteza din sir
   for paranteza in s:
       # Daca paranteza este deschisa, o adaugam in stiva
       if paranteza == '(':
           stiva.append(paranteza)
       # Daca paranteza este inchisa
       elif paranteza == ')':
           # Daca stiva este goala, inseamna ca sirul nu este corect parantezat
           if len(stiva) == 0:
               return 0
           # Altfel, scoatem o paranteza deschisa din stiva
           stiva.pop()
   # Daca la final stiva este goala, sirul este corect parantezat
   return 1 if len(stiva) == 0 else 0

1. Functia principala

def main():

   # Deschidem fisierul de intrare si citim datele
   with open('paranteze1.in', 'r') as fin:
       n = int(fin.readline().strip())  # Numarul de siruri
       siruri = [fin.readline().strip() for _ in range(n)]  # Sirurile de paranteze

   # Verificam daca fiecare sir este corect parantezat
   rezultate = [este_corect_parantezat(sir) for sir in siruri]

   # Scriem rezultatele in fisierul de iesire
   with open('paranteze1.out', 'w') as fout:
       for rezultat in rezultate:
           fout.write(str(rezultat) + '\n')

1. Apelam functia principala

if __name__ == '__main__':

   main()

</syntaxhighlight>