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

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()