Informatyka dla klas III - Odwrotna Notacja Polska

Obliczanie wartości wyrażenia ONP

Odwrotną notację polską ONP (ang. RPN – Reverse Polish Notation), zwana często również notacją Postfix, wymyślono w celu zapisywania dowolnych wyrażeń arytmetycznych bez nawiasów. W normalnym zapisie arytmetycznym operatory znajdują się pomiędzy argumentami:

 

2 + 2     6 - 4     3 * 5     12 / 3

 

Operatory posiadają priorytety, czyli "ważność". Jeśli w wyrażeniu wystąpią operatory o różnych priorytetach, to najpierw zostaną wykonane te ważniejsze:

 

3 + 5 * 2 = 3 + 10 = 13

 

Jeśli chcemy zmienić kolejność wykonywania działań, musimy używać nawiasów:

 

(3 + 5) * 2 = 8 * 2 = 16

 

W ONP problem ten nie występuje. Operator zawsze występuje po swoich argumentach:

 

2 2 +     6 4 -     3 5 *     12 3 /

 

Dzięki tej prostej zasadzie nawiasy stają się zbędne:

 

3 + 5 * 2 → 3 5 2 * + = 3 10 + = 13

(3 + 5) * 2 → 3 5 + 2 * = 8 2 * = 16

 

Do obliczenia wartości wyrażenia zapisanego w ONP potrzebujemy stosu. Zasada jest następująca:

 

Wyrażenie ONP przeglądamy od strony lewej do prawej. Jeśli napotkamy liczbę, to umieszczamy ją na stosie. Jeśli napotkamy operator, to ze stosu pobieramy dwie ostatnie liczby, wykonujemy na nich działanie zgodne z napotkanym operatorem i wynik umieszczamy z powrotem na stosie. Gdy wyrażenie zostanie przeglądnięte do końca, na szczycie stosu będzie znajdował się jego wynik.

 

Przykład:

 

Wyrażenie ONP Element Operacja Stos
 3  5  2  *  +     ---
 3  5  2  *  +  3  na stos

3
---

 3  5  2  *  +  5  na stos

5
3
---

 3  5  2  *  +  2  na stos

2
5
3
---

 3  5  2  *  +  * 

pobierz 2 i 5
mnóż 5 * 2
wynik na stos

10
3
---

 3  5  2  *  +  + 

pobierz 10 i 3
dodaj 3 + 10
wynik na stos

13
---

 

Notacja ONP jest szeroko wykorzystywana w kompilatorach języków wysokiego poziomu. Istnieją również języki, które do obliczeń stosują jedynie ONP – np. Forth.

Przed przystąpieniem do zaprojektowania algorytmu ONP musimy poczynić pewne ustalenia. Dla prostoty umawiamy się, że używać będziemy tylko czterech operatorów arytmetycznych:

Wyrażenie musi być poprawne – algorytm nie sprawdza jego poprawności.

Każdy element będzie wprowadzany w osobnym wierszu – w ten sposób pozbędziemy się problemu analizowania tekstu pod kątem zawartości w nim liczb i operatorów. W rzeczywistości wyrażenie zawarte w wierszu zostałoby najpierw rozbite na elementy składowe – liczby i operatory – a następnie elementy te zostałyby użyte do obliczenia wartości wyrażenia wg naszego algorytmu.

Liczby muszą mieć postać akceptowaną przez dany język programowania.

Ostatnim elementem wyrażenia jest znak "=". Powoduje on zakończenie obliczeń i wyprowadzenie wyniku ze stosu.

W algorytmie będziemy musieli rozpoznawać, czy wprowadzony element jest liczbą, czy też operatorem lub znakiem "=". W języku C++  można to zrobić następująco:

 

Wykorzystujemy własność strumienia, który przy złej konwersji daje wartość 0. Wypróbuj poniższy program dla strumienia cin:

 

#include <iostream>

using namespace std;

int main()
{
    double x;

    cout << (cin >> x) << endl;
    return 0;
}
 

Program odczytuje ze strumienia cin ciąg znaków i stara się je zamienić na liczbę zmiennoprzecinkową dla zmiennej x. Jeśli konwersja się powiedzie, to operacja (cin >> x) zwróci jakąś wartość różną od zera. Jeśli ciągu znaków nie da się zamienić na liczbę, to operacja zwróci wartość 0 (w programie wpisz wartość poprawną, np. 12.54, a następnie niepoprawną, np. ABC – za pierwszym razem otrzymasz coś różnego od zera, a za drugim zero). Jeśli operacje takie wykonujemy w pętli, to należy wyczyścić strumień za pomocą ss.str("") oraz wyzerować stan znaczników błędów strumienia za pomocą funkcji cin.clear() – inaczej dostaniemy poprzednią wartość błędu.

Na tym prostym fakcie oprzemy rozpoznawanie, czy wprowadzony łańcuch tekstu reprezentuje liczbę, czy nie. Jako strumień wykorzystamy strumień łańcuchowy. Będzie nam potrzebny plik nagłówkowy sstream, który definiuje klasy strumieni łańcuchowych.

#include <iostream>
#include <sstream>
#include <string>

using namespace std;

int main()
{
    double x;
    stringstream ss;   // strumień łańcuchowy
    string s;          // łańcuch;

    s = "";            // zerujemy łańcuch
    while(s != "=")
    {
      cin >> s;        // czytamy łańcuch znaków
      ss.str("");      // usuwamy wszelki tekst ze strumienia
      ss.clear();      // czyścimy błędy konwersji z poprzednich wywołań
      ss << s;         // odczytany łańcuch umieszczamy w strumieniu
      if(ss >> x)      // konwertujemy na liczbę i sprawdzamy, czy konwersja była poprawna
        cout << "LICZBA " << x << endl;
      else
        cout << "NIE LICZBA " << s << endl;
    }
    return 0;
}

Algorytm obliczania wartości wyrażenia ONP

Wejście:
S    stos liczb zmiennoprzecinkowych

Kolejne elementy wyrażenia odczytujemy ze standardowego wejścia

Wyjście:

Wartość wyrażenia ONP na szczycie stosu S

Elementy pomocnicze:
e  – przechowuje odczytaną informację z wejścia jako łańcuch tekstowy
v1, v2  –  przechowują argumenty operacji
Lista kroków:
K01: Czytaj e ; odczytujemy kolejne elementy wyrażenia ONP
K02: Jeśli e = "=", to zakończ ; znak = kończy wyrażenie ONP
K03: Jeśli e jest liczbą, to idź do K09 ; liczby umieszczamy na stosie
K04: v2 ← S.top()
S.pop()
; pobieramy ze stosu argumenty operacji
K05: v1 ← S.top()
S.pop()
 
K06: Wykonaj operację na v1 i v2 zgodnie z zawartością e.
Wynik umieść w v1
; wykonujemy obliczenia zgodnie ze znakiem operatora
K07: S.push(v1) ; wynik trafia na stos
K08: Idź do K01 ; kontynuujemy przetwarzanie wyrażenia
K09: Przekształć e na liczbę w v1  
K10: Idź do K07 ; liczbę umieszczamy na stosie

 

Przekształcanie wyrażeń na ONP

W wyrażeniu symbolicznym zamiast wartości liczbowych występują symbole:  (a + b) * c

Gdy obliczaliśmy wartość wyrażenia ONP, stos był używany do przechowywania wyników częściowych obliczeń – czyli był to stos liczbowy. Przy konwersji wyrażenia arytmetycznego na postać ONP również wykorzystujemy stos, jednakże tutaj będzie on przechowywał nie liczby, a operatory. Zasada jest następująca:

 

Wyrażenie arytmetyczne odczytujemy od strony lewej do prawej.

Jeśli dojdziemy do końca wyrażenia, to ze stosu operatorów pobieramy operatory i przenosimy je kolejno na wyjście aż do wyczyszczenia stosu. Algorytm kończymy.
Jeśli odczytanym elementem jest symbol zmiennej, to przenosimy go na wyjście.
Jeśli odczytanym elementem jest nawias otwierający, to umieszczamy go na stosie.
Jeśli odczytanym elementem jest nawias zamykający, to ze stosu przesyłamy na wyjście wszystkie operatory, aż do napotkania nawiasu otwierającego, który usuwamy ze stosu.
Jeśli odczytanym elementem jest operator, to ze stosu na wyjście przesyłamy wszystkie operatory o priorytecie wyższym od priorytetu odczytanego operatora. Po tej operacji operator umieszczamy na stosie.
Kontynuujemy od początku z następnym elementem.

 

Przykład:

 

Wyrażenie Element Operacja Stos Wyjście
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =  start   ---  
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
---

 
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   a

na wyjście

(
---

 a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
---

a
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   b

na wyjście

+
(
---

a  b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   *

na stos

 * 
+
(
---

a b
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   c

na wyjście

*
+
(
---

a b  c
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   -

ze stosu na wyjście
na stos

-
+
(
---

a b c *
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   d

na wyjście

-
+
(
---

a b c *  d
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   )

ze stosu na wyjście
ze stosu na wyjście
usuń ze stosu

---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   /

na stos

 / 
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   (

na stos

 ( 
/
---

a b c * d - +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   e

na wyjście

(
/
---

a b c * d - +  e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   +

na stos

 + 
(
/
---

a b c * d - + e
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  =   f

na wyjście

+
(
/
---

a b c * d - + e  f
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )   )

ze stosu na wyjście
usuń ze stosu

/
---

a b c * d - + e f +
 (  a  +  b  *  c  -  d  )  /  (  e  +  f  )  koniec

ze stosu na wyjście

---

a b c * d - + e f + /

 

Przed zaprojektowaniem algorytmu ustalamy co następuje:

Symbole są zbudowane z pojedynczych liter. Chodzi tutaj o uproszczenie analizy wyrażenia. Gdy napotkamy literę, to traktujemy ją jako symbol.
W wyrażeniu dozwolone są tylko operacje +, -, *, / i ^ (potęgowanie).
Wyrażenie wejściowe musi być poprawne – algorytm nie sprawdza tego.
Operacje posiadają priorytety zgodne z zasadami arytmetyki – najwyższy priorytet ma potęgowania, później mnożenie i dzielenie, a na końcu dodawanie i odejmowanie.
Wyrażenie kończy się znakiem "=".

 

Algorytm przekształcania wyrażenia na postać ONP

Wejście:

symboliczne wyrażenie arytmetyczne

Wyjście:

wyrażenie ONP

Zmienne i funkcje pomocnicze:
S  – stos operatorów
c  –  znak odczytany z wejścia
p(c)  –  funkcja zwracająca priorytet:
(    = 0
+ - = 1
* /  = 2
^    = 3
Lista kroków:
K01: Utwórz pusty stos S  
K02: Czytaj c ; odczytujemy znak z wejścia
K03: Jeśli c ≠ '=', to idź do K08 ; sprawdzamy, czy koniec wyrażenia
K04: Dopóki S.empty() = false, wykonuj K05...K06  
K05:     Pisz S.top() ; na wyjście przesyłamy operatory ze stosu
K06:     S.pop() ; przesłany operator usuwamy ze stosu
K07: Zakończ  
K08: Jeśli c ≠ '(', to idź do K11 ; sprawdzamy, czy mamy nawias otwierający
K09: S.push('(') ; nawias otwierający umieszczamy na stosie
K10: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K11: Jeśli c ≠ ')', to idź do K17 ; sprawdzamy, czy mamy nawias zamykający
K12: Dopóki S.top() ≠ '(', wykonuj K13...K14  
K13:     Pisz S.top() ; ze stosu przesyłamy na wyjście operatory
K14:     S.pop() ; aż do napotkania nawiasu otwierającego
K15: S.pop() ; usuwamy ze stosu nawias otwierający
K16: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K17: Jeśli c ≠ operator, to idź do K23 ; sprawdzamy, czy mamy operator
K18: Dopóki S.empty() = false p(S.top()) > p(c), wykonuj K19...K20  
K19:     Pisz S.top() ; na wyjście przesyłamy ze stosu operatory
K20:     S.pop() ; o wyższych priorytetach
K21: S.push(c) ; operator umieszczamy na stosie
K22: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia
K23: Pisz c ; z przesyłamy na wyjście
K24: Idź do K02 ; i kontynuujemy przetwarzanie wyrażenia

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.