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