Odwrotna notacja polska (RPN)

0

Mam pytanko: ma ktos moze namiary albo zrodlo do jakiegos programu wykorzystujacego odwrotna notacje polska ?? najlepiej w Delphi......

konkretnie chodzi mi o sposob zamiany ciagu np. z

((2+7/3)+(14-3)*4)/2

na

7 3 / 2 + 14 3 - 4 * + 2 /

Jesli ktos nie wie co to jest RPN to patrczie tu: http://programowanie.org/wiki/Odwrotna_notacja_polska

0

Gdybyś zajrzał do działu Delphi\Gotowce\Prosty kalkulator, to już byś wiedział jak to działa.

0

moze i tak tylko ze zaden (!) art z dzialu gotowce nie chce sie ladowac... ale coz sproboje pozniej.

ps. o ile pamietam ten kalkulatorek jak kiedys sprawdzalem wcale nie taki prosty :P

0

Tak sobie kombinuję...
0. zakodować w jakis sposób priorytety operatorów

  1. musisz sprawdzic ilość lewych i prawych nawiasów
  2. można dodać () na zewnątrz wyrażenia - zależy tylko od tego jak
    wykonasz ten algorytm

A teraz rekurencyjnie liczenie bloku () od najmniej zagniedżonego:
3. jeżeli wewnątrz są bloki o tym samym stopniu zagnieżdżenia, to
rekurencyjnie do ptk. 3 z tymi blokami po kolei
4. przetłumaczyć wartości na notację polską
zgodnie z przyjętymi priorytetami
5. policzyć
6. zwrócic wartośc i powrócić.

Odwrotna notacja polska ma to do siebie, że bardzo łatwo obrabia się ja potokowo, czyli najpierw ładujemy dane, a potem gdy dostaniemy operator robimy cos z tymi danymi. Potem znowu ładujemy i znowu operator... Ale to pewnie sam zauważyłeś. A rekurencja i kłopoty ze stosem... Ile par () możesz mieć w wyrażeniu? 10? 20? Jeśli nie przesadzisz z danymi lokalnymi, to Ci stosu nie rozsadzi. Stopień zagnieżdżenia to tak jak z begin/end - im głębiej tym większy.

// do postu poniżej.
Tworzyłem tak, bo na taki pomysł przy okazji wpadłem, nie myślałem nad tym głębiej. Ale fakt rekurencja jest marna, tyle że iteracja bywa często trudniejsza w implementacji. Ale dzieki temu człowiek ma teraz kilka wiecej algorytmów do wyboru. :d

0

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 )

  1. Przetwarzamy wyrazenie pojawiające na stosie WE
  2. 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)
  1. Gdy stos (WE) jest już pusty to przekładamy wszystkie pozostałe operatory ze stosu (POM) na stos (WY)
  2. Otrzymujemy stos (WY) z wyrażeniem w odwrotnej notacji polskiej, ale od jego końca westarczy go tyklo odwrócić
  3. 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.

  1. Przetwarzamy wyrazenie pojawiające na stosie WE

  2. 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)

  3. Wynikiem jest liczba na stosie WE

  4. 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).

1 użytkowników online, w tym zalogowanych: 0, gości: 1