ODWROTNA NOTACJA POLSKA- definicja

drukuj

Odwrotna notacja polska inaczej RPN (ang. Reverse Polish Notation) - 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). Zapis ten pozwala na całkowitą rezygnację z użycia nawiasów w wyrażeniach, jako że jednoznacznie określa kolejność wykonywanych działań.

Na przykład 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 /

Odwrotna notacja polska powstała z beznawiasowej notacji polskiej Jana Łukasiewicza na potrzeby zastosowań informatycznych. Jest używana w niektórych językach programowania (FORTH, Postscript) oraz w kalkulatorach naukowych firmy Hewlett-Packard. Programy komputerowe dokonując analizy wyrażenia arytmetycznego często przekształcają je na odwrotną notację polską.

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.

Algorytm obliczenia wartości wyrażenia RPN

1. wyzeruj stos
2. dla wszystkich symboli z wyrażenia RPN wykonuj:
   1. jeśli i-ty symbol jest liczbą, to odłóż go na stos
   2. jeśli i-ty symbol jest operatorem to:
      1. zdejmij ze stosu jeden element (ozn. a)
      2. zdejmij ze stosu kolejny element (ozn. b)
      3. odłóż na stos wartość b operator a
3. zdejmij ze stosu wynik

Data dodania: 2005-03-18 17:36:19
Ostatnia modyfikacja: 2005-03-18 17:36:19
Dodane przez: Piotr Łukańko [administrator]

Elementy powiązane: [ukryj]