Konwertuje wyrażenie matematyczne do ONP za pomocą algorytmu stacji rozrządowej (stos).
Odwrotna notacja polska (ONP, ang. postfix notation) to sposób zapisu wyrażeń arytmetycznych, w którym operator stoi po argumentach. Notacja nie wymaga nawiasów – kolejność działań jest zakodowana w samym układzie wyrażenia.
Przykład: 2 3 5 - 3 * - w zwykłej notacji to 2 - (3 - 5) * 3 = 8.
Algorytm obliczania ONP opiera się na strukturze stosu:
Dla każdego znaku w wyrażeniu jeśli jest to liczba, kładziemy ją na stos. Jeśli jest to operator, zdejmujemy ze stosu dwa argumenty (najpierw b, potem a), wykonujemy działanie a operator b i wynik kładziemy z powrotem na stos. Po przetworzeniu całego wyrażenia na stosie pozostaje jedna liczba – wynik.
Uwaga na kolejność argumentów: dla operacji niesymetrycznych (-, /) b jest drugim argumentem, a a – pierwszym. Czyli operacja to a - b, nie b - a.
Zastosowania: kalkulatory naukowe HP (lata 70.), kompilatory (uproszczona analiza), maszyny wirtualne.
funkcja oblicz_onp(wyrazenie): stos ← pusty stos // przetwarzamy znak po znaku dla każdego tokenu z w wyrazenie: jeżeli z jest liczbą: odłóż z na stos w przeciwnym razie: // z jest operatorem - zdejmij dwa argumenty b ← zdejmij ze stosu a ← zdejmij ze stosu wynik ← wykonaj_dzialanie(a, z, b) odłóż wynik na stos zwróć zdejmij ze stosu
def oblicz_onp(wyrazenie):
stos = []
for token in wyrazenie.split():
if token in ('+', '-', '*', '/'):
b = stos.pop()
a = stos.pop()
if token == '+':
stos.append(a + b)
elif token == '-':
stos.append(a - b)
elif token == '*':
stos.append(a * b)
elif token == '/':
stos.append(a / b)
else:
stos.append(int(token))
return stos.pop()
# Przykład użycia
print(oblicz_onp("2 3 5 - 3 * -"))
# Wynik: 8 (czyli 2 - (3 - 5) * 3)
print(oblicz_onp("4 2 +"))
# Wynik: 6
print(oblicz_onp("10 2 /"))
# Wynik: 5.0O(n)O(n)Zagadnienia z tego samego obszaru matury – warto je powtórzyć razem: