3795 - Paranteze4: Difference between revisions

Revision as of 11:31, 27 December 2023

Cerinta

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

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

Date de iesire

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

Restrictii si precizari

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

Exemplul 1

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

Datele introduse corespund restrictiilor impuse

1 4 5 3 6 2

Exemplul 2

Intrare: ( ) b a / .
Iesire

Datele introduse nu corespund restrictiilor impuse

Rezolvare

<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

Citire șir de paranteze rotunde

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

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

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ă
+# Citire șir de paranteze rotunde
-paranteze_input = input("Introduceți șirul de paranteze rotunde corect parantezat: ")
+sir_paranteze = input("Introduceți șirul de paranteze rotunde: ")
-# Rezolvare și afișare rezultat
+# Calcul și afișare rezultate
-rezultat = gaseste_paranteza_deschisa(paranteze_input)
+rezultate = paranteze_corecte(sir_paranteze)
-print("Parantezele deschise corespunzătoare:")
+if rezultate:
-for inchisa, deschisa in rezultat.items():
+    for deschisa, inchisa in rezultate:
-    print(f"{inchisa}: {deschisa}")
+        print(f"Paranteza deschisa la pozitia {deschisa} se inchide la pozitia {inchisa}.")
 </syntaxhighlight>