Odwrotna notacja polska - Google

Odwrotna notacja polska

Z Wikipedii

Skocz do: nawigacji, szukaj

Odwrotna notacja polska (ang. Reverse Polish Notation, RPN) – jest sposobem zapisu wyrażeń arytmetycznych, w którym znak wykonywanej operacji umieszczony jest po operandach (zapis postfiksowy), a nie pomiędzy nimi jak w konwencjonalnym zapisie algebraicznym (zapis infiksowy), lub przed operandami jak w zwykłej notacji polskiej (zapis prefiksowy). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.

RPN bardzo ułatwia wykonywanie na komputerze obliczeń z nawiasami i zachowaniem kolejności działań. Zarówno algorytm konwersji notacji konwencjonalnej (infiksowej) na odwrotną notację polską (postfiksową), jak i algorytm obliczania wartości wyrażenia danego w RPN są bardzo proste i wykorzystują stos.

Odwrotna notacja polska została opracowana przez australijskiego naukowca Charlesa Hamblina jako "odwrócenie" beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Hamblin sugerował aby notację tą nazwać "Azciweisakul notation" (Notacja Azciweisakuł – "Łukasiewicza" pisane od tyłu).

Jest używana w niektórych językach programowania (np. FORTH, Postscript) oraz w niektórych kalkulatorach naukowych (np. Hewlett-Packard, National Semiconductor). Programy komputerowe kompilujące program dokonują analizy wyrażenia arytmetycznego, przekształcając je na ciąg instrukcji odpowiadający odwrotnej notacji polskiej. Wyrażenie to jest obliczane podczas wykonywania programu.

Spis treści

[edytuj] Przykłady zapisu

Przykładowy konwencjonalny zapis:

 (2+3)*5

w RPN wygląda tak:

 2 3 + 5 *

natomiast:

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

zapiszemy następująco:

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

[edytuj] Algorytm obliczenia wartości wyrażenia RPN

  • Wyzeruj stos.
  • Dla wszystkich symboli z wyrażenia RPN wykonuj:
    • jeśli i-ty symbol jest liczbą, to odłóż go na stos,
    • jeśli i-ty symbol jest operatorem to:
      • zdejmij ze stosu jeden element (ozn. a),
      • zdejmij ze stosu kolejny element (ozn. b),
      • odłóż na stos wartość b operator a.
    • jeśli i-ty symbol jest funkcją to:
      • zdejmij ze stosu oczekiwaną ilość parametrów funkcji(ozn. a1...an)
      • odłóż na stos wynik funkcji dla parametrów a1...an
  • Zdejmij ze stosu wynik.

[edytuj] Algorytm konwersji z notacji infiksowej do RPN (rekurencyjny)

  • Funkcja ONP:
    • Zdefiniowanie zmiennych char a, c.
(należy zdefiniować zmienne w funkcji ONP, tak, aby za każdym razem gdy funkcja ONP się wykona,
nastąpiło zapisanie wartości tych zmiennych w innym miejscu w pamięci. Gdyby zdefiniować te zmienne
jako globalne, to nastąpiłoby błędne zastępowanie ich wartości, wartościami poprzednimi.
  • Wczytaj znak z wejścia do zmiennej (c) i:
  • Jeżeli przeczytany znak jest lewym nawiasem:
  • Wywołaj funkcję ONP.
  • Wczytaj znak z wejścia do zmiennej (a). (to zawsze powinien być operator)
  • Wywołaj funkcję ONP.
  • Ściągnij znak z wejścia nie zapisując go. (to zawsze powinien być prawy nawias)
  • Wypisz zmienną (a) na wyjście.
  • W przeciwnym wypadku wypisz wczytany znak (c).
Ten algorytm działa poprawnie jedynie dla wyrażeń, które mają pełne nawiasowanie np. (a+(b*c)).
Nie działa poprawnie, jeśli w wyrażeniu znajduje się unarny minus: (-a).
Przykład
(notacja infixowa):
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))
Po zamianie (w odwrotnej notacji polskiej):
abc*+
ab+zx+*
at+bac++cd+^*

[edytuj] Algorytm konwersji z notacji infiksowej do RPN

Edsger Dijkstra wymyślił algorytm nazywany "stacją rozrządową", ponieważ jest w działaniu bardzo podobny do kolejowej stacji rozrządowej. Tak jak algorytm liczący wartość wyrażenia RPN, ten także działa na bazie stosu. Do konwersji używane są dwie zmienne (typu ciągu znakowego) – wejście oraz wyjście. Jest także stos przechowujący operatory nie dodane jeszcze do wyjścia. W uproszczeniu, program czyta po kolei każdą literę i wykonuje operację zależną od tej litery.

[edytuj] Szczegóły algorytmu

  • Póki zostały symbole do przeczytania wykonuj:
Przeczytaj symbol.
  • Jeśli symbol jest liczbą dodaj go do kolejki wyjście.
  • Jeśli symbol jest funkcją włóż go na stos.
  • Jeśli symbol jest znakiem oddzielającym argumenty funkcji (np. przecinek):
  • Dopóki najwyższy element stosu nie jest lewym nawiasem, zdejmij element ze stosu i dodaj go do kolejki wyjście. Jeśli lewy nawias nie został napotkany, to znaczy, że znaki oddzielające zostały postawione w złym miejscu lub nawiasy są źle umieszczone.
  • Jeśli symbol jest operatorem, o1, wtedy:
1) dopóki na górze stosu znajduje się operator, o2 taki, że:
o1 jest łączny lub lewostronnie łączny i jego kolejność wykonywania jest mniejsza lub równa kolejności wyk. o2, lub
o1 jest prawostronnie łączny i jego kolejność wykonywania jest mniejsza od o2,
zdejmij o2 ze stosu i dołóż go do kolejki wyjściowej;
2) włóż o1 na stos operatorów.
  • Jeżeli symbol jest lewym nawiasem to włóż go na stos.
  • Jeżeli symbol jest prawym nawiasem to zdejmuj operatory ze stosu i dokładaj je do kolejki wyjście, dopóki symbol na górze stosu nie jest lewym nawiasem, kiedy dojdziesz do tego miejsca zdejmij lewy nawias ze stosu bez dokładania go do kolejki wyjście. Teraz, jeśli najwyższy element na stosie jest funkcją, także dołóż go do kolejki wyjście. Jeśli stos zostanie opróżniony i nie napotkasz lewego nawiasu, oznacza to, że nawiasy zostały źle umieszczone.
  • Jeśli nie ma więcej symboli do przeczytania, zdejmuj wszystkie symbole ze stosu (jeśli jakieś są) i dodawaj je do kolejki wyjścia. (Powinny to być wyłącznie operatory, jeśli natrafisz na jakiś nawias, znaczy to, że nawiasy zostały źle umieszczone.)

[edytuj] Przykład

Wejście 3+4*2/(1-5)^2
Przeczytaj "3"
 Dodaj "3" do wyjścia
  Wyjście: 3

Przeczytaj "+"
 Włóż "+" na stos
  Wyjście: 3
  Stos: +

Przeczytaj "4"
 Dodaj "4" do wyjścia
  Wyjście: 3 4
  Stos: +

Przeczytaj "*"
 Włóż "*" na stos
  Wyjście: 3 4
  Stos: + *

Przeczytaj "2"
 Dodaj "2" do wyjścia
  Wyjście: 3 4 2
  Stos: + *

Przeczytaj "/"
 Zdejmij "*" ze stosu i dodaj do wyjścia, włóż "/" na stos
  Wyjście: 3 4 2 *
  Stos: + /

Przeczytaj "("
 Włóż "(" na stos
  Wyjście: 3 4 2 *
  Stos: + / (

Przeczytaj "1"
 Dodaj "1" do wyjścia
  Wyjście: 3 4 2 * 1
  Stos: + / (

Przeczytaj "-"
 Włóż "-" na stos
  Wyjście: 3 4 2 * 1
  Stos: + / ( -

Przeczytaj "5"
 Dodaj "5" do wyjścia
  Wyjście: 3 4 2 * 1 5
  Stos: + / ( - 

Przeczytaj ")"
 Zdejmij "-" ze stosu i dodaj do wyjścia, zdejmij "(" ze stosu
  Wyjście: 3 4 2 * 1 5 -
  Stos: + / 

Przeczytaj "^"
 Włóż "^" na stos
  Wyjście: 3 4 2 * 1 5 -
  Stos: + / ^

Przeczytaj "2"
 Dodaj "2" do wyjścia
  Wyjście: 3 4 2 * 1 5 - 2
  Stos: + / ^

Koniec wyrażenia
 Zdejmij stos na wyjście
  Wyjście: 3 4 2 * 1 5 - 2 ^ / +

Chavez o Merkel: hitlerowska prawica
Znany z niepohamowanego języka prezydent Wenezueli Hugo Chavez atakuje Angelę Merkel. Niemieckiej kanclerz dostało się za przynależność do niemieckiej chadecji - "tego samego prawicowego skrzydła, które popierało Hitlera i faszyzm".
Unia Europejska cieszy się z wyboru Serbów
Tysiące ludzi na belgradzkich ulicach i Unia Europejska ucieszyły się ze zwycięstwa koalicji "O europejską Serbię" pod wodzą Partii Demokratycznej prezydenta Borisa Tadicia, która w przedterminowych wyborach parlamentarnych zdobyła 39 proc. głosów. Ultranacjonalistyczna Serbska Partia Radykalna została w tyle, uzyskując 28,6 proc. głosów.
Sikorski mediuje w Gruzji
Minister spraw zagranicznych Radosław Sikorski, wraz z szefami dyplomacji trzech innych państw Unii Europejskiej, będzie rozmawiał w Tbilisi z gruzińskimi politykami. Celem jest zmniejszenie napięcia na linii Rosja-Gruzja wokół separatystycznej Abchazji.
Prezydent jedzie do Izraela
Miesiąc po wizycie premiera Donalda Tuska do Izraela jedzie prezydent Lech Kaczyński. Głowa polskiego państwa weźmie udział w uroczystych obchodach 60. urodzin państwa. Spotka się też z Georgem W. Bushem.
Nagi futbol
Na wiedeńskim stadionie piłkarskim imienia Ernsta Happela, gdzie zostanie rozegrany mecz finałowy Euro zgromadziło się 1840 kompletnie nagich osób. Nie była to demonstracja nudystów ani protest ekologów, tylko kolejne dzieło znanego artysty Spencera Tunicka, specjalizującego się fotografowaniu nagich scen zbiorowych.
Linki: Strona gwna