2228 - expresie10

Enunt

Se consideră o expresie formată din numere naturale şi perechi de paranteze drepte. Includerea între paranteze corespunde operației de calcul a câtului împărțirii întregi la 2 a valorii incluse între paranteze, iar alăturarea a două paranteze corespunde operației de adunare a valorilor subexpresiilor. Expresia poate fi calculată doar dacă este corectă, adică nu conține numere care să nu fie incluse între paranteze drepte, nu conține perechi de paranteze care să nu includă nici un număr sau nici o altă subexpresie şi perechile de paranteze se închid corect.

Cerința

Fiind dată o expresie construită conform descrierii să se decidă dacă este corectă şi în caz afirmativ să se calculeze valoarea acesteia.

Date de intrare

Fișierul de intrare expresie10IN.txt conține pe prima linie o expresie formata numai din paranteze drepte şi numere naturale.

Date de ieșire

Fișierul de ieșire expresie10OUT.txt va conține pe prima linie valoarea expresiei în cazul în care aceasta este corectă. Dacă expresia din fişierul de intrare nu este corectă, atunci se va scrie mesajul expresie gresita. În cazul în care restricțiile nu sunt îndeplinite, se va afișa mesajul "Datele nu corespund restrictiilor impuse".

Restricții și precizări

• numerele care apar în expresii sunt întregi şi sunt cuprinse între 0 şi 30000
• expresia din fișierul de intrare este formată din cel mult 200 de caractere

Exemplul 1:

expresie10IN.txt

[[34][23[12][]

expresie10OUT.txt

expresie gresita

Exemplul 2:

expresie10IN.txt

[30001][23[12]]

expresie10OUT.txt

Datele nu corespund restrictiilor impuse

Rezolvare

from typing import List

def verifica_restricții(expresie: str) -> bool:
    if len(expresie) > 200:
        return False
    for c in expresie:
        if c.isdigit():
            if not 0 <= int(c) <= 30000:
                return False
    return True

def proceseaza_expresie(input_file: str, output_file: str):
    with open(input_file, 'r') as f:
        continut = f.read().replace('\n', '')

    if not verifica_restricții(continut):
        with open(output_file, 'w') as f:
            f.write("Datele nu corespund restrictiilor impuse")
        return

    stiva: List[int] = []
    ok = True
    e = False
    nr1 = nr2 = x = sum = 0
    x = -1

    numar_curent = ""
    for c in continut:
        if c == '[':
            nr1 += 1
        elif c == ']':
            nr2 += 1

        if nr1 or nr2:
            e = True

        if c == '[' and x == -1:
            stiva.append(x)
        else:
            if c.isdigit():
                numar_curent += c  # Construim numărul curent
                if len(numar_curent) > 5 or int(numar_curent) > 30000:  # Verificăm lungimea și valoarea numărului
                    with open(output_file, 'w') as f:
                        f.write("Datele nu corespund restrictiilor impuse")
                    return
                x = int(numar_curent)
            else:
                numar_curent = ""  # Resetează numărul curent când întâlnești un non-digit
                if c == ']' and x != -1 and stiva[-1] == -1 and stiva:
                    stiva.pop()
                    stiva.append(x >> 1)
                    x = -1
                    nr1 -= 1
                    nr2 -= 1
                elif c == ']' and stiva and stiva[-1] >= 0 and len(stiva) >= 2:
                    minus = True
                    while minus:
                        a = stiva.pop()
                        if not stiva:
                            break
                        b = stiva.pop()
                        if b != -1:
                            stiva.append(a + b)
                        else:
                            minus = False
                            break
                    stiva.append(a >> 1)
                    nr1 -= 1
                    nr2 -= 1
                    if nr2 > nr1:
                        ok = False
                else:
                    ok = False

    if nr1 or nr2 or not e:
        ok = False

    while stiva and ok:
        if stiva[-1] != -1:
            sum += stiva.pop()
        else:
            ok = False
            break

    with open(output_file, 'w') as f:
        if ok:
            f.write(str(sum))
        else:
            f.write("expresie gresita")

if __name__ == "__main__":
    input_file = 'expresie10IN.txt'
    output_file = 'expresie10OUT.txt'
    proceseaza_expresie(input_file, output_file)