0874 - Atomi

Cerința

Într-o galaxie îndepărtată există doar două elemente chimice. Cercetătorii le-au numit A şi B şi toate substanțele sunt alcătuite din aceste elemente. Mai precis, o substanță este un șir definit astfel:

A și B sunt substanțe, formate din câte un atom; Ax și By sunt substanțe, x și y find numere naturale. Ax este formată din x atomi de tip A, iar By este formată din y atomi de tip B; dacă S este substanță atunci (S)x este substanță, x fiind un număr natural. Dacă în S sunt p atomi, în (S)x vor fi p*x atomi; dacă S şi T sunt substanțe atunci ST este substanță. Dacă în S sunt x atomi, iar în T sunt y atomi, în ST vor fi x+y atomi. Pentru o substanță dată să se determine numărul atomilor de tip A şi numărul atomilor de tip B care o compun.

Date de intrare

Programul citește de la tastatură numărul un şir de caractere reprezentând substanța dată.

Date de ieșire

Programul va afișa pe ecran două numere nA nB, separate printr-un spațiu, reprezentând numărul atomilor de tip A, respectiv numărul atomilor de tip B din substanța dată.

Restricții și precizări

• șirul dat are cel mult 255 de caractere

Exemplu 1

Intrare

(A3B2)2A3(B2)2

Iesire

9 8

Rezolvare

<syntaxhighlight lang="python" line> def numara_atomi(expresie):

   stack = []
   i = 0
   n = len(expresie)
   
   while i < n:
       if expresie[i] == '(':
           stack.append('(')
           i += 1
       elif expresie[i] == ')':
           sub_exp = []
           while stack and stack[-1] != '(':
               sub_exp.append(stack.pop())
           stack.pop()  # scoatem '('
           sub_exp.reverse()
           i += 1
           coef = 0
           while i < n and expresie[i].isdigit():
               coef = coef * 10 + int(expresie[i])
               i += 1
           coef = max(coef, 1)
           for elem in sub_exp:
               stack.append((elem[0], elem[1] * coef, elem[2] * coef))
       elif expresie[i] in 'AB':
           tip = expresie[i]
           i += 1
           numar = 0
           while i < n and expresie[i].isdigit():
               numar = numar * 10 + int(expresie[i])
               i += 1
           numar = max(numar, 1)
           if tip == 'A':
               stack.append(('A', numar, 0))
           else:
               stack.append(('B', 0, numar))
       else:
           i += 1
   
   total_A = 0
   total_B = 0
   for elem in stack:
       total_A += elem[1]
       total_B += elem[2]
   
   return total_A, total_B

def main():

   expresie = input().strip()
   
   # Verificăm restricția privind lungimea expresiei
   assert len(expresie) <= 255, "Expresia trebuie să aibă cel mult 255 de caractere"
   
   nA, nB = numara_atomi(expresie)
   print(f"{nA} {nB}")

if __name__ == "__main__":

   main()

</syntaxhighlight>