Flabra: tylko nie rekurencyjnie. Już takie coś kiedyś o ile pamiętam Sheitar robił, ja potem próbowałem udoskonalić na własne potrzeby, ale było strasznie nieelastyczne. Wykorzystując stos i ONP rozszerza się na dowolne operatory/funkcje raz dwa.
Tutaj fragment (bardzo nieciekawego, ale jednak) opisu ONP i wyliczania wyrażenia ze skryptu pewnego pana (na którego patrzeć nie mogę, bo to *** nie wykładowca):
17.1.1. Notacja polska
Notacja ta bywa zwana też - od nazwiska jej twórcy-
NOTACJĄ ŁUKASIEWICZA
Notacja infiksowa Notacja polska Odwrotna notacja polska
x+y + x y x y +
2*(2-4)/5 / *2 -2 4 5 2 2 4 - * 5 /
Cechy notacji polskiej
umożliwia zapis dowolnego wyrażenia bez konieczności użycia nawiasów
ułatwia kontrole poprawności wyrażenia
jest to notacja często stosowana w wiekszości kolkulatorów
wymusza konieczność rozróżnienia operatorów binarnych i unarnych (np. + - )
skomplikowany zapis
17.1.2. Zamiana notacji infiksowej na odwrotną notacje polska
Potrzebne są nam trzy stosy.
• Stos wejściowy (WE)
• Stos wynikowy (WY)
• Stos pomocniczy (POM)
Założmy, że na stosie WE dane mamy wyrażenie rozbite na atomy i ułożone w takiej kolejmości aby pobieranie z niego danych odpowiadało kolejności pojawiania się atomów w wyrażeniu. Mogła by tu być użyta kolejka.
Np. 2*(3+7) 2 * ( 3 + 7 )
- Przetwarzamy wyrazenie pojawiające na stosie WE
- Jeśli atom jest:
a) Liczbą to „wrzycamy” ja na stos (WY)
b) Nawiasem „(” to „wrzycamy” ja na stos (POM)
c) Nawiasem „)” to ze stos (POM) zdejmujemy operator i kładziemy go na stos (WY)
operacje tą powtarzamy az do momentu zdjęcia ze stosu (POM) atomu „)”-tego atomu nie kładziemu na stosie
d) Operatorem O sprawdzamy jaki operator jest na stosie (POM)
-jeśli stos jest pusty to kładziemy operator O na stos (POM)
-jeśli operator na stosie ma wyższy priorytet to kładziemy go z powrotem na stos (POM) i nastepnie dokładamy operator O
- jeśli operator na stosie ma niższy bądź równy priorytet to kładziemy na stos (WY)
nastepnie powtarzamy operację dla kolejnego poeratora na stosie (POM)
na koniec kładziemy operator O na sios (POM)
- Gdy stos (WE) jest już pusty to przekładamy wszystkie pozostałe operatory ze stosu (POM) na stos (WY)
- Otrzymujemy stos (WY) z wyrażeniem w odwrotnej notacji polskiej, ale od jego końca westarczy go tyklo odwrócić
- Zamiast punktu 3) można przenieść dane ze stosu (WY) na stos (POM). Wtedy wynikiem jest stos (POM).
17.1.3. Kalkulator stosowy
Potrzebne są nam dwa stosy.
• Stos wejściowy (WE)
• Stos wynikowy (WY)
Założmy, że na stosie WE dane mamy wyrażenie w odwrotnej notacji polskiej rozbite na atomy.
-
Przetwarzamy wyrazenie pojawiające na stosie WE
-
Jeśli atom jest:
a) Liczbą to „wrzycamy” ja na stos (WY)
b) Operatorem O to ze stosu (WY) pobiaramy arg2
następnie ze stosu (WY) pobiaramy arg1
i na stos (WY) wkładamy wynik wyrażenia
arg1 O arg2 (zapis w notacji infiksowej)
-
Wynikiem jest liczba na stosie WE
-
Jeśli na stosie WE zabraknie argumentów, bądź jeśli zostanie więcej niż jedna liczba, oznacze to sytuację błędną.
Możliwa jest zatem kontrola poprawności wprowadzonego wyrażenia.
Przykład:
3- (45)(6+7)/8 = -29.5
Napisałbym to IMHO troszkę czytelniej, ale czasu teraz nie mam.
Mogę dać kod w C kalkulatorka lub dwa w Delphi (jeden właśnie z wykorzystaniem rekurencji, a drugi na stosach i to dostępnych od razu w Delphi).