Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych. Autor artykułu: mgr Jerzy Wałaszek,  wersja1.0

©2013 mgr Jerzy Wałaszek I LO w Tarnowie

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:

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:

#include <iostream>

using namespace std;

int main()
{
    double x;

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

#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:

Wyjście:

Wartość wyrażenia ONP na szczycie stosu S

Elementy pomocnicze:

Lista kroków:

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:

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:

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

---

I Liceum Ogólnokształcące    im. Kazimierza Brodzińskiego w Tarnowie ©2024 mgr Jerzy Wałaszek

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

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe