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

<syntaxhighlight lang="python3" line="1"> 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.")

</syntaxhighlight>