Strona główna » Algorytmy » Artykuły » Odwrotna Notacja Polska
 

Odwrotna Notacja Polska

https://mattomatti.com/a28
· Wprowadzanie · Rozszerzenie ·

Odwrotna Notacja Polska (ONP)

Przy zapisie obliczeń w odwrotnej notacji polski wykorzystujemy zapis prefiksowy, a nie tradycyjnie infiksowy. Różnica polega na ustawieniu liczb oraz operatorów. Tradycyjny zapis infiksowy to np. 2 + 3 - operator znajduje się pomiędzy dwoma liczbami (lub wyrażeniami). W przypadku postaci prefiksowej najpierw podajemy liczby, potem operator: 2 3 +. Na pierwszy rzut oka wydaje się to mało intuicyjne, ale taki zapis ułatwia komputerowi obliczenia, ponieważ w ONP nie występują nawiasy, ale kolejność wykonywania działań zostaje zachowana. Implementację ONP najlepiej oprzeć o zasadę działania stosu.

Przykład

W celu zobrazowania zasady obliczania takich wyrażeń przeanalizujmy poniższy przykład, który wyjaśnia jak obliczyć wyrażenie "8 4 2 + 3 - *".

StosWejścieOperacja
(pusty)8Kładziemy liczbę na stosie
{8}4Kładziemy liczbę na stosie
{8, 4}2Kładziemy liczbę na stosie
{8, 4, 2}+Operator dodawania jest dwuargumentowy. Zdejmujemy dwie wartości ze stosu 2 i 4. I ich sumę odkładamy z powrotem na stos.
{8, 6}3Kładziemy liczbę na stosie
{8, 6, 3}-Operator odejmowania. Zdejmujemy wartości ze stosu: 3 i 6. I na stos odkładamy wynik działania.
{8, 3}*Operator mnożenia. Zdejmujemy wartości ze stosu, kolejno 3 i 8. Wynik odkładamy na stos.
{24}(brak)Jako wynik zwracamy wartość na stosie

W notacji nawiasowej obliczane wyrażenie miałoby postać: ((2 + 4) - 3)·8 = (6 - 3)·8 = 3·8 = 24.

Implementacja

Lista kroków algorytmu

  1. Tworzymy stos
  2. Dla każdego elementu w wyrażeniu od lewej do prawej: Jeśli element jest liczbą to odkładamy go na stos. Jednak jeśli element jest operatorem to zdejmuje ze stosu dwie liczby - a i b - i odkładamy na stos wartość b operator a
  3. Ze stosu zdejmujemy wynik

Dodatkowa biblioteka

Implementacja kodu będzie korzystać ze stosu, który został przeze mnie opisany tutaj. Istnieje możliwość dołączenia mojego rozwiązania do swojego projektu pobierając i dołączając do swojej aplikacji biblioteke stos.h, którą dołączamy do aplikacji przy pomocy include:

C++
C#
  1. #include "stos.h"

Założenia

Tym razem zaczniemy od funkcji main. Wczytamy od użytkownika wyrażenie, a następnie wywołamy jeszcze nienapisaną funkcję ONP i wyświetlimy wynik. Zakładamy, że napis będzie składał się z liczb, operatorów oraz spacji.

Przykładowo dla:

  1. 2 3 +
  2. 5

Kod właściwy

Jak już ustaliliśmy dostajemy ciąg znaków. Zakładamy, że wynik to będzie liczba rzeczywista. Nasz program będzie iterował każdy znak i odpowiednio go interpretował. Nie będziemy sprawdzać poprawności wejścia. Możemy założyć, że użytkownik umie korzystać z ONP bezbłędnie.

C++
C#
  1. double ONP(char* input){
  2.   Stack* st = createStack();
  3.   int i = 0;
  4.   while(input[i]){

Na początku tworzymy nowy stos na który będziemy odkładać liczby. (3.) Zmienna i będzie nam wskazywała, który znak aktualnie interpretujemy. Interpretacja będzie odbywała się (4.) w pętli while.

Załóżmy, że chcemy wczytać liczbę. Musimy rozpatrzeć dwa przypadki: kiedy liczba jest ujemna - zaczyna się wtedy od znaku "-", potem cyfry. W drugim przypadku same cyfry.

C++
C#
  1.     if((input[i]>='0' && input[i]<='9') || (input[i]=='-' && input[i]>='0' && input[i]<='9')){
  3.       bool minus = false;
  4.       if(input[i]=='-'){
  5.         minus = true;
  6.         i++;
  7.       }

Wprowadźmy dodatkową zmienną minus, która będzie pamiętała czy wczytany napis ma być ujemny czy nie. Domyślnie minus = false, ponieważ zakładamy, że liczba jest dodatnia. Bardzo ważna jest linijka (7.) gdzie zwiększamy i. Bez niej nasz program dalej przestałby wczytywać liczbę ponieważ znalazłby znak "-" zamiast cyfr.

Dalsza część to wczytywanie liczby dopóki znajdujemy jakiekolwiek cyfry.

C++
C#
  1.       double a = 0;
  2.       while(input[i]>='0' && input[i]<='9'){
  3.         a *= 10;
  4.         a += (input[i] - '0');
  5.         i++;
  6.       }
  8.       if(minus)
  9.         a *= -1;
  10.       push(st, a);

Zmienna a przechowuje wczytywaną liczbę, ale bez znaku. Przed położeniem jej na stosie musimy pomnożyć przez -1 jeśli ma być ujemna.

Jeśli okazuje się, że to nie wczytujemy liczby to zakładamy, że mamy do czynienia z operatorem. W tej części pobierzemy do zmiennych t1 i t2 dwie liczby z wierzchu stosu, a przy użyciu switch'a wybierzemy odpowiednią operację do wykonania:

C++
C#
  1.     } else {
  2.       double t1 = pop(st), t2 = pop(st);
  3.       switch(input[i]){
  4.         case '+':
  5.           push(st, t2 + t1);
  6.         break;
  7.         case '-':
  8.           push(st, t2 - t1);
  9.         break;
  10.         case '*':
  11.           push(st, t2 * t1);
  12.         break;
  13.         case '/':
  14.           push(st, t2 / t1);
  15.         break;
  16.       }
  17.     }
  18.     i++;
  19.   }

Na sam koniec zwracamy wynik zdejmując wynik ze stosu:

C++
C#
  1.   double wynik = pop(st);
  2.   st = NULL;
  3.   return wynik;
  4. }

Wynik (39.) musimy pobrać przed (40.) usunięciem stosu, bo inaczej stracimy do niego dostęp, a stos wraz z wynikiem będzie zalegał w pamięci. Na sam koniec funkcji (42.) zwracamy wynik.

Testowanie funkcji

Działanie funkcji można sprawdzić przy pomocy poniższego fragmentu kodu:

C++
C#
  1. int main(){
  2.   const int BUFFER_SIZE = 256;
  3.   char* c = new char[BUFFER_SIZE];
  4.   cin.getline(c, BUFFER_SIZE);
  5.   cout << "Wynik dzialania to " << ONP(c);
  6.   system("pause");
  7.   return 0;
  8. }

Zmienna BUFFER_SIZE jest opcjonalna. Wygodniej się zmienia rozmiar buforu w jednym, a nie w dwóch miejscach kiedy uznamy, że użytkownik powinien móc wprowadzić dłuższy ciąg znaków.

Zadania

Zadanie 1

Dodaj kolejny operator potęgowania ^.

Zadanie 2

Dodaj intepretację liczb, które mają na początku +, np. +123.