...
Eroare Algoritmi și structuri de date · Stive, cozi și liste înlănțuite

Evaluarea formei postfixate dă rezultat greșit la - și /: operanzii scoși din stivă în ordine inversă

Pe scurt

Primul element scos din stivă e operandul din dreapta, nu cel din stânga. Scrie b = stiva.pop(); a = stiva.pop() și calculează a - b sau a / b. La + și * ordinea nu contează, de aceea greșeala apare doar la scădere și împărțire.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

În forma postfixată (notația poloneză inversă), 10 3 - înseamnă 10 - 3. Algoritmul pune numerele în stivă, iar la un operator scoate ultimele două. Stiva e LIFO: ultimul pus (3) iese primul. Așadar primul pop() dă operandul din dreapta, al doilea dă operandul din stânga.

Dacă scrii a = stiva.pop(); b = stiva.pop() și calculezi a - b, obții 3 - 10 = -7. La adunare și înmulțire ordinea nu contează, deci testele cu + și * trec, iar greșeala apare abia la - și /.

Aceeași regulă se aplică la calculatoare cu două stive (algoritmul lui Dijkstra pentru expresii), la evaluarea arborilor de expresii și la orice operație necomutativă: puteri, concatenări, comparații.

De ce apare: cauzele frecvente

1Operanzii scoși în ordinea scrierii

Greșit
PYTHON
a = stiva.pop()
b = stiva.pop()
stiva.append(a - b)
Corect
PYTHON
b = stiva.pop()
a = stiva.pop()
stiva.append(a - b)

Ultimul număr pus în stivă e operandul din dreapta, deci iese primul.

2Împărțirea cu // la numere negative

Greșit
PYTHON
stiva.append(a // b)
Corect
PYTHON
stiva.append(int(a / b))

Multe enunțuri cer trunchiere spre zero. // rotunjește în jos: -7 // 2 e -4, iar int(-7 / 2) e -3.

Repară tu

Repară eroarea, direct în pagină

Funcția evalueaza(expresie) calculează o expresie în formă postfixată. Testul cu assert pică la scădere și împărțire. Repar-o ca să afișeze 7, 4 și 14.

Codul care dă eroarea
PYTHON
def evalueaza(expresie):
    stiva = []
    for t in expresie.split():
        if t in '+-*/':
            a = stiva.pop()
            b = stiva.pop()
            if t == '+':
                stiva.append(a + b)
            elif t == '-':
                stiva.append(a - b)
            elif t == '*':
                stiva.append(a * b)
            else:
                stiva.append(int(a / b))
        else:
            stiva.append(int(t))
    return stiva[0]

for expr, corect in [('10 3 -', 7), ('8 2 /', 4), ('2 3 4 * +', 14)]:
    rez = evalueaza(expr)
    assert rez == corect, f'rezultat gresit: {rez} in loc de {corect}'
    print(rez)
După reparație, programul afișează
7
4
14
Indiciu

Primul pop() dă operandul din dreapta.

Cum o eviți pe viitor

Când scoți doi operanzi dintr-o stivă, numește-i după poziția lor în expresie (dreapta = stiva.pop(), stanga = stiva.pop()), nu a și b. Testează mereu cu operatori necomutativi (10 3 -, 8 2 /) și cu un rezultat negativ. Verifică și ce fel de împărțire cere enunțul.

Întrebări frecvente

De ce testele cu + treceau?

Pentru că 3 + 10 e același lucru cu 10 + 3. Ordinea greșită se vede doar la operațiile necomutative.

Ce fac dacă stiva are mai puțin de doi operanzi?

Expresia e invalidă și primești IndexError: pop from empty list. Verifică len(stiva) >= 2 și dă un mesaj clar.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.