3991 - Modifica Paranteze

Cerința

Fie un șir de paranteze rotunde, deschise sau închise. Putem efectua de câte ori dorim operația de transformare a unei paranteze deschise într-una închisă sau invers. Să se determine numărul minim de operații necesare transformării secvenței inițiale într-una corect parantezată. Dacă acest lucru nu este posibil, se va afișa -1.

Date de intrare

Programul citește de la tastatură șirul de paranteze rotunde, fără spații.

Date de ieșire

Programul va afișa pe ecran numărul minim de operații necesar pentru a transforma șirul într-o secvență corect parantezată. Dacă nu este posibilă parantezarea corectă, se va afișa -1.

Restricții și precizări

• 1 ≤ numărul de paranteze ≤ 1000

Exemplul 1:

Intrare

((((

Ieșire

2

Explicație

O posibilitate este să modificăm ultimele două paranteze deschise în paranteze închise și să obținem (()).

Exemplul 2:

Intrare

(((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((

Ieșire

Datele nu corespund restrictiilor impuse.

Rezolvare

def check_restriction(s):
    num_parentheses = s.count('(') + s.count(')')
    return 1 <= num_parentheses <= 1000

def nr_min_op(s):
    cnt = 0
    nr_op = 0
    n = len(s)

    if not check_restriction(s):
        print("Datele nu corespund restrictiilor impuse.")
        return -1

    if n % 2 == 1:
        return -1

    for i in range(n):
        if s[i] == '(':
            cnt += 1
        else:
            cnt -= 1

        if cnt < 0:
            nr_op += 1
            cnt = 1

    nr_op += cnt // 2
    return nr_op

if __name__ == "__main__":
    s = input("Introduceti un sir cu paranteze: ")

    if check_restriction(s):
        result = nr_min_op(s)
        if result != -1:
            print(result)
    else:
        print("Datele nu corespund restrictiilor impuse.")