1126 - Betisoare

Enunţ

Se presupune că unele dintre primele instrumente de calcul au fost beţişoarele de socotit. În problema noastră vom considera un număr ca fiind o succesiune de unul sau mai multe beţişoare, un beţişor fiind reprezentat de litera I. Într-o expresie, între oricare două numere există semnul + sau semnul *.

Exemple:

Numere

   I
   III
   IIIIIIIIIII

Expresii

   III
   II*III
   I+I*III+IIIIIII

Cerinţă

Scrieţi un program care evaluează astfel de expresii.

Date de intrare

Fișierul de intrare betisoare.in conține pe prima linie o valoare naturală n, care indică numărul de expresii care trebuie evaluate. Fiecare dintre următoarele n linii conţine un şir de maximum 1.000.000 caractere care reprezintă expresia ce trebuie evaluată.

Date de ieșire

Fișierul de ieșire betisoare.out va conține pe fiecare linie i dintre primele n linii câte un număr întreg care reprezintă rezultatul evaluării expresiei de pe linia i+1 din fişierul de intrare.

Restricții și precizări

• 1 ≤ n ≤ 10
• O expresie poate avea cel puţin 1 caracter şi cel mult 1.000.010 de caractere.
• Valorile calculate pe parcurs şi valoarea finală au maximum 18 cifre.
• Dintre teste, 26% conţin numai operaţii de adunare, 22% numai operaţii de înmulţire, iar restul de 52% conţin ambele operaţii.

Exemplul 1

betisoare.in

1

I+I*III+IIIIIII

betisoare.out

11

Exemplul 2

betisoare.in

1

I+I*III+IIIIIII

betisoare.out

4

2

Exemplul 3

betisoare.in

II2+3*II

betisoare.out

Date de intrare invalide!

Rezolvare

<syntaxhighlight lang="python" line>

1. 1126 Betisoare

def verificare_date_intrare(expresie):

 caractere_permise = {'I', '+', '*'}
 for caracter in expresie:
   if caracter not in caractere_permise and not caracter.isdigit():
     return False
 return True

def evaluare_expresie(expresie):

 stiva = []
 numar = 0
 for caracter in expresie:
   if caracter == 'I':
     numar += 1
   elif caracter == '+':
     stiva.append(numar)
     stiva.append('+')
     numar = 0
   elif caracter == '*':
     stiva.append(numar)
     stiva.append('*')
     numar = 0
   elif caracter.isdigit():
     numar = numar * 10 + int(caracter)

 # Adăugăm ultimul număr la stivă
 stiva.append(numar)

 rezultat = 0
 operatie = '+'
 while stiva:
   element = stiva.pop()
   if isinstance(element, int):
     if operatie == '+':
       rezultat += element
     elif operatie == '*':
       rezultat *= element
   else:
     operatie = element

 return rezultat

def main():

 with open("betisoare.in", "r") as f:
   n = f.readline().strip()
   try:
     n = int(n)
   except ValueError:
     with open("betisoare.out", "w") as fout:
       fout.write("Date de intrare invalide!\n")
     return

   expresii = [f.readline().strip() for _ in range(n)]

 rezultate = []
 for expresie in expresii:
   if not verificare_date_intrare(expresie):
     rezultate.append("Date invalide")
     continue
   rezultat = evaluare_expresie(expresie)
   rezultate.append(rezultat)

 with open("betisoare.out", "w") as f:
   for rezultat in rezultate:
     f.write(str(rezultat) + "\n")

if __name__ == "__main__":

 main()

</syntaxhighlight>