0849 - Paranteze2

Cerința

Se dă un șir de paranteze rotunde care se închid corect (corect parantezat). Să se determine adâncimea parantezării.

Pentru un șir de paranteze închise corect S, adâncimea parantezării, D(S) este definită astfel:

dacă șirul S este vid, D(S)=0 dacă S=(T), unde T este un șir de paranteze corect, D(S)=1+D(T) dacă S=AB, unde A și B sunt șiruri de paranteze corecte, D(S)=max{D(A),D(B)}

Date de intrare

Fișierul de intrare paranteze2in.txt conține pe prima un șir de paranteze rotunde, corect parantezat.

Date de ieșire

Fișierul de ieșire paranteze2out.txt va conține pe prima linie un număr M, reprezentând adâncimea parantezării.

Restricții și precizări

• șirul va conține cel mult 254 de paranteze

Exemplul 1:

paranteze2in.txt

1

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

paranteze2out.txt

Datele de intrare corespund restrictiilor impuse.

3

Exemplul 2:

paranteze2in.txt

h

paranteze2out.txt

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

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

def validare(strings): # functia de validare a datelor de intrare

   for sir in strings:
       if len(sir) > 254:
           raise ValueError
   file_out.write("Datele de intrare corespund restrictiilor impuse\n")

def adancime_parantezare(sir): # functia de rezolvare

   adancime_maxima = 0
   adancime_curenta = 0
   for paranteza in sir:
       if paranteza == '(':
           adancime_curenta += 1
           if adancime_curenta > adancime_maxima:
               adancime_maxima = adancime_curenta
       elif paranteza == ')':
           adancime_curenta -= 1
   return adancime_maxima

if __name__ == '__main__':

   file_in = open('paranteze2in.txt', 'r')
   file_out = open('paranteze2out.txt', 'w')

   try:
       n = int(file_in.readline().strip())
       siruri = [file_in.readline().strip() for _ in range(n)]
       validare(siruri)
       rezultate = [adancime_parantezare(sir) for sir in siruri]
       for rezultat in rezultate:
           file_out.write(str(rezultat) + '\n')
   except ValueError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")
   except IndexError:
       file_out.write("Datele de intrare nu corespund restrictiilor impuse")

</syntaxhighlight>