3795 - Paranteze4: Difference between revisions

Latest revision as of 12:23, 29 December 2023

Cerinta[edit | edit source]

Să se scrie un program care citește un șir de paranteze rotunde care se închid corect (corect parantezat) în care parantezele deschise sunt numerotate de la stânga la dreapta, începând de la 1, și determină pentru fiecare paranteză închisă numărul de ordine al parantezei deschise corespunzătoare.

Un șir de paranteze rodunde S este corect parantezat dacă:

S este șirul vid, sau
S = (T) și T este corect parantezat, sau
S = AB, iar A și B sunt corect parantezate.

Date de intrare[edit | edit source]

Programul citește de la tastatură șir de paranteze rotunde, corect parantezat.

Date de iesire[edit | edit source]

Programul va afișa pe ecran, pentru fiecare paranteză închisă, poziția în șir a parantezei deschise corespunzătoare.

Restrictii si precizari[edit | edit source]

șirul citit va conține cel mult 254 de caractere, numai ( și );
în șirul dat caracterele sunt numerotate de la 1.

Exemplul 1[edit | edit source]

Intrare: ()((()())())
Iesire

Datele introduse corespund restrictiilor impuse

1 4 5 3 6 2

Exemplul 2[edit | edit source]

Intrare: ( ) b a / .
Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare[edit | edit source]

<syntaxhighlight lang="python3" line="1"> def paranteze_corecte(sir):

   stiva = []
   rezultat = []

   for i, paranteza in enumerate(sir):
       if paranteza == '(':
           stiva.append(i + 1)
       elif paranteza == ')':
           if stiva:
               deschisa = stiva.pop()
               rezultat.append((deschisa, i + 1))
           else:
               print("Parantezele nu sunt corect parantezate.")
               return None

   if stiva:
       print("Parantezele nu sunt corect parantezate.")
       return None

   return rezultat

def verificare_date_intrare(sir):

   return all(caracter in '()' for caracter in sir) and len(sir) <= 254

Citire șir de paranteze rotunde

sir_paranteze = input("Introduceți șirul de paranteze rotunde: ")

Verificare date de intrare

if not verificare_date_intrare(sir_paranteze):

   print("Datele introduse nu corespund restrictiilor impuse")

else:

   # Calcul și afișare rezultate
   rezultate = paranteze_corecte(sir_paranteze)
   if rezultate:
       for deschisa, inchisa in rezultate:
           print(f"Paranteza deschisa la pozitia {deschisa} se inchide la pozitia {inchisa}.")

</syntaxhighlight>

Explicatie[edit | edit source]

1 2 3 4 5 6 ( ) ( ( ( ) ( ) ) ( ) )

 1       4   5 3   6 2

@@ Line 3: / Line 3: @@
 Să se scrie un program care citește un șir de paranteze rotunde care se închid corect (corect parantezat) în care parantezele deschise sunt numerotate de la stânga la dreapta, începând de la 1, și determină pentru fiecare paranteză închisă numărul de ordine al parantezei deschise corespunzătoare.
-Un șir de paranteze rodunde S este corect parantezat dacă:
+Un șir de paranteze rodunde '''S''' este corect parantezat dacă:
 *S este șirul vid, sau
@@ Line 19: / Line 19: @@
 == Restrictii si precizari ==
-*șirul citit va conține cel mult 254 de caractere, numai ( și );
+*șirul citit va conține cel mult '''254''' de caractere, numai ( și );
 *în șirul dat caracterele sunt numerotate de la 1.
@@ Line 26: / Line 26: @@
 :()((()())())
 ;Iesire
-;Datele introduse corespund restrictiilor impuse
+Datele introduse corespund restrictiilor impuse
 :1 4 5 3 6 2
@@ Line 33: / Line 33: @@
 :( ) b a / .
 ;Iesire
-;Datele introduse nu corespund restrictiilor impuse
+Datele introduse nu corespund restrictiilor impuse
 == Rezolvare ==
 <syntaxhighlight lang="python3" line="1">
-def gaseste_paranteza_deschisa(paranteze):
+def paranteze_corecte(sir):
-     stack = []  # Folosim un stack pentru a urmări parantezele deschise
+     stiva = []
-     rezultat = {}  # Dicționar pentru a stoca rezultatele finale
+     rezultat = []
-     for i, paranteza in enumerate(paranteze):
+     for i, paranteza in enumerate(sir):
-         if paranteza == '(':  # Dacă întâlnim o paranteză deschisă, o adăugăm în stack
+         if paranteza == '(':
-             stack.append(i + 1)  # Adăugăm 1 pentru că indexarea începe de la 0, dar parantezele sunt numerotate de la 1
+             stiva.append(i + 1)
-         elif paranteza == ')':  # Dacă întâlnim o paranteză închisă
+         elif paranteza == ')':
-             if stack:  # Verificăm dacă stack-ul nu este gol
+             if stiva:
-                 deschisa = stack.pop()  # Scoatem ultima paranteză deschisă din stack
+                 deschisa = stiva.pop()
-                 rezultat[i + 1] = deschisa  # Adăugăm rezultatul în dicționar
+                 rezultat.append((deschisa, i + 1))
              else:
                  print("Parantezele nu sunt corect parantezate.")
+                return None
+    if stiva:
+        print("Parantezele nu sunt corect parantezate.")
+        return None
      return rezultat
-# Citire șir de paranteze de la tastatură
+def verificare_date_intrare(sir):
-paranteze_input = input("Introduceți șirul de paranteze rotunde corect parantezat: ")
+    return all(caracter in '()' for caracter in sir) and len(sir) <= 254
+# Citire șir de paranteze rotunde
+sir_paranteze = input("Introduceți șirul de paranteze rotunde: ")
+# Verificare date de intrare
+if not verificare_date_intrare(sir_paranteze):
+    print("Datele introduse nu corespund restrictiilor impuse")
+else:
+    # Calcul și afișare rezultate
+    rezultate = paranteze_corecte(sir_paranteze)
+    if rezultate:
+        for deschisa, inchisa in rezultate:
+            print(f"Paranteza deschisa la pozitia {deschisa} se inchide la pozitia {inchisa}.")
-# Rezolvare și afișare rezultat
-rezultat = gaseste_paranteza_deschisa(paranteze_input)
-print("Parantezele deschise corespunzătoare:")
-for inchisa, deschisa in rezultat.items():
-    print(f"{inchisa}: {deschisa}")
 </syntaxhighlight>