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

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