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 paranteze2.in conține pe prima un șir de paranteze rotunde, corect parantezat.

Date de ieșire

Fișierul de ieșire paranteze2.out 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

Exemplu:

paranteze2.in

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

paranteze2.out

3

Rezolvare

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

def adancime_parantezare(sir):

   adancime_maxima = 0 # initializam adancimea maxima cu 0
   adancime_curenta = 0 # initializam adancimea curenta cu 0

   for paranteza in sir: # parcurgem fiecare paranteza din sir
       if paranteza == '(': # daca paranteza este deschisa
           adancime_curenta += 1 # crestem adancimea curenta
           if adancime_curenta > adancime_maxima: # daca adancimea curenta este mai mare decat cea maxima
               adancime_maxima = adancime_curenta # actualizam adancimea maxima
       elif paranteza == ')': # daca paranteza este inchisa
           if adancime_curenta > 0: # daca exista o paranteza deschisa corespunzatoare
               adancime_curenta -= 1 # scadem adancimea curenta
           else:
               return -1 # sirul nu este corect parantezat

   if adancime_curenta != 0: # daca la sfarsitul sirului mai exista paranteze deschise
       return -1 # sirul nu este corect parantezat

   return adancime_maxima # returnam adancimea maxima a parantezarii

sir = '()((()())())' # sirul de intrare print(adancime_parantezare(sir)) # afisam rezultatul functiei

</syntaxhighlight>