Evaluarea formei postfixate dă rezultat greșit la - și /: operanzii scoși din stivă în ordine inversă
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
a = stiva.pop()
b = stiva.pop()
stiva.append(a - b)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
stiva.append(a // b)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ă 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.
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)7 4 14
Indiciu
Primul pop() dă operandul din dreapta.
Reparația
def evalueaza(expresie):
stiva = []
for t in expresie.split():
if t in '+-*/':
b = stiva.pop()
a = 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)De ce merge
Pentru 10 3 -, stiva conține [10, 3]. Primul pop() dă 3, iar varianta veche îl folosea ca operand din stânga și calcula 3 - 10. Inversând ordinea atribuirilor, b primește operandul din dreapta (3), iar a pe cel din stânga (10), deci a - b e 7 și a / b pentru 8 2 / e 4. Adunarea și înmulțirea dau același rezultat în ambele variante.
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
IndexError: pop from empty list Ai apelat stiva.pop() pe o stivă goală. La verificarea parantezelor înseamnă de obicei o paranteză închisă fără pereche. Verifică înainte cu if not stiva: (și tratează cazul) sau pune condiția în while stiva and ... Verificarea parantezelor returnează True pentru „((” (stiva rămâne nevidă) Funcția verifică doar parantezele închise, dar la final nu verifică dacă au rămas paranteze deschise în stivă. Înlocuiește return True de la final cu return not stiva (sau len(stiva) == 0). TypeError: list indices must be integers or slices, not float Ai calculat poziția cu împărțirea obișnuită /, care dă mereu un număr zecimal (2.0, 2.5), iar indicii de listă trebuie să fie întregi. Folosește împărțirea întreagă: mijloc = (stanga + dreapta) // 2. Î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.
