Editing 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>