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

Odwrotna Notacja Polska

· 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.

Implementacja

Lista kroków algorytmu

  1. Tworzymy stos
  2. Dla każdego elementu w wyrażeniu od lewej do prawej:
    1. Jeśli element jest liczbą to odkładamy go na stos
    2. 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:

  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

Założenia wczytania danych i pokazania wyniku spełnia poniższy kod:

  1. int main(){
  2.   const int BUFFER_SIZE = 256;
  3.   char* c = new char[BUFFER_SIZE];
  4.   cin.getline(c, BUFFER_SIZE);
  5.   cout << 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.

Kod właściwy

Jak już ustaliliśmy dostajemy ciąg znaków. Zakładamy, że wynik to będzie liczba rzeczywista, więc nagłówek funkcji to:

  1. double ONP(char* input){

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.

  1.   Stack* st = createStack();
  2.   int i = 0;
  3.   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.

  1.     if((input[i]>='0' && input[i]<='9') || (input[i]=='-' && input[i]>='0' && input[i]<='9')){

Wprowadźmy dodatkową zmienną minus, która będzie pamiętała czy wczytany napis ma być ujemny czy nie:

  1.       bool minus = false;
  2.       if(input[i]=='-'){
  3.         minus = true;
  4.         i++;
  5.       }

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.

  1.       double a = 0;
  2.       while(input[i]>='0' && input[i]<='9'){
  3.         a *= 10;
  4.         a += (input[i] - '0');
  5.         i++;
  6.       }

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:

  1.       if(minus)
  2.         a *= -1;
  3.       push(st, a);

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:

  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.     }

Na sam koniec pamiętamy o zwiększaniu i i o zamknięciu pętli while:

  1.     i++;
  2.   }

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

  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.

Zadania

Zadanie 1

Dodaj kolejny operator potęgowania ^.

Zadanie 2

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