2088 - decodif

Se consideră următorul model (pattern): n[string] care este echivalent cu șirul (string)(string)...(string) (string repetat de de n ori). Pornind de la acest model orice șir de caractere poate fi codificat.

Exemple :

Șir codificat

1[a] 2[ab] 2[a2[b]] 3[b2[ca]]

Șir decodificat

a abab abbabb bcacabcacabcaca

Cerința

Fiind dat un șir de caractere corect codificat să se afișeze decodificarea acestuia.

Date de intrare

Programul citește de la tastatură un șir de caractere S corect codificat.

Date de ieșire

Programul va afișa pe ecran un șir de caractere ce va reprezenta decodificarea șirului S.

Restricții și precizări

3 ≤ lungimea șirului S ≤ 1000
lungimea șirului decodificat ≤ 100000
șirul S va conține doar caractere literă mică ale alfabetului englez

Exemplu:

Intrare

3[a1[b2[c]]]

Ieșire

abccabccabcc

Intrare

3[a2[c]]2[x3[y]]

Ieșire

accaccaccxyyyxyyy

Rezolvare

Funcția care decodifică șirul

def decode_string(s):

   # Inițializăm stiva cu un șir gol și un număr 1
   stack = []
   stack.append(["", 1])
   num = ""
   # Parcurgem fiecare caracter din șir
   for ch in s:
       if ch.isdigit():
           # Dacă caracterul este o cifră, o adăugăm la numărul curent
           num += ch
       elif ch == '[':
           # Dacă întâlnim un '[', adăugăm un nou element în stivă cu șirul curent și numărul curent
           stack.append(["", int(num)])
           num = ""
       elif ch == ']':
           # Dacă întâlnim un ']', scoatem elementul din vârful stivei, îl repetăm de un număr de ori și îl adăugăm la șirul din următorul element din stivă
           st, k = stack.pop()
           stack[-1][0] += st*k
       else:
           # Dacă întâlnim o literă, o adăugăm la șirul din vârful stivei
           stack[-1][0] += ch
   # La sfârșit, returnăm șirul din primul element al stivei
   return stack[0][0]

Citim șirul de la tastatură

s = input("Introduceți șirul codificat: ")

Apelăm funcția și afișăm rezultatul

print(decode_string(s))

</syntaxhighlight>