Strona główna » Algorytmy » Artykuły » Notacja infiksowa na postfiksową
 

Notacja infiksowa na postfiksową

https://mattomatti.com/a30

Postać infiksowa, a postfiksowa

Postać infiksowa jest powszechnie wykorzystywana w matematyce. Jednak dla komputerów o wiele wygodniejsze jest wczytać dwa argumenty i zastosować operator czyli skorzystać z postaci postfiksowej. W notacji postfiksowej nie ma potrzeby używania nawiasów co zdecydowanie skraca czas obliczeń i złożoność kodu je wykonującego.

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ą lub stałą to wypisujemy go na wyjście
    2. Jeśli element to ( to odkładamy go na stos
    3. Jeśli element to ) to zdejmujemy wszystkie operatory i wypisujemy na wyjście do (, który też zdejmujemy, ale nie wypisujemy na wyjście
    4. Jeśli element jest operatorem to:
      • dopóki istnieją elementy o priorytecie niższym na wierzchołku stosu to je zdejmujemy i wypisujemy na wyjście
      • odkładamy wczytywany operator na stos
  3. Zdejmujemy wszystkie operatory i je wypisujemy na wyjście

Implementacja

Przygotowanie

W kodzie będę 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 dyrektywy include:

  1. #include "stos.h"

Założenia

Zakładamy, że otrzymujemy od użytkownika napis, który zawiera liczby, stałe, operatory i znaki nawiasów. Między nimi mogą się pojawić spacje. Przykładowo dla:

  1. 1+(2+ 3)*(4/5)
  2. 1 2 3 + 4 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.   char* d = InfixToPostfix(c);
  6.   cout << d;
  7.   system("pause");
  8.   return 0;
  9. }

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.

Rozpoznawanie operatorów

Żeby algorytm dobrze działał musimy wiedzieć czy dany znak jest operatorem, a jeśli tak to jaki jest jego priorytet. Funkcja priorytet() dla podanego znaku zwróci -1 jeśli to nie jest operator lub odpowiednią wartość między 0, a 3 jeśli jest to operator. Użyjemy do tego funkcji switch:

  1. int priorytet(char c){
  2.   switch(c){
  3.     case '(':
  4.       return 0;
  5.     case '+':
  6.     case '-':
  7.     case ')':
  8.       return 1;
  9.     case '*':
  10.     case '/':
  11.     case '%':
  12.       return 2;
  13.     case '^':
  14.       return 3;
  15.     default:
  16.       return -1;
  17.   }
  18. }

Kod właściwy

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

  1. char* InfixToPostfix(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 wprowadza prawidłowy napis do konwersji.

  1.   char* c = new char[512];
  2.   int i = 0;
  3.   int ic = 0;
  4.   while(input[i]){

Na początku (2.) tworzymy stos na którym będziemy odkładać operatory. Dalej tworzymy nową zmienną c, która będzie przechowywać napis wyjściowy. Potrzebujemy zadeklarować dwie zmienne: (4.) i, która posłuży do iteracji napisu wejściowego oraz ic, która będzie wskazywała, który znak napisu wyjściowego aktualnie nadpisujemy. (6.) I rozpoczynamy iterację napisu wejściowego.

  1.     if(input[i]>='0' && input[i]<='9' || input[i]>='a' && input[i]<='z'){
  2.       while(input[i]>='0' && input[i]<='9' || input[i]>='a' && input[i]<='z'){
  3.         c[ic] = input[i];
  4.         ic++;
  5.         i++;
  6.       }
  7.       c[ic++] = ' ';

Liczby i stałe zostaję przepisane od razu na wyjście, dlatego (8.) po sprawdzeniu, że mamy literę lub cyfrę rozpoczynamy (9. - 13.) przepisywanie na wyjście, aż będzie cyfra lub litera. Na sam koniec (14.) dopisujemy spację. Następnie sprawdzamy czy podany znak nie jest nawiasem. Jeśli jest to go dopisujemy na stos.

  1.     } else if(input[i]=='(') {
  2.       push(st, input[i]);
  3.       i++;

Należy pamiętać, aby zwiększyć zmienną i. Inaczej będziemy w kółko rozpatrywać ten sam znak. Zgodnie z listą kroków dalej sprawdzimy czy wczytany znak nie jest nawiasem zamykającym:

  1.     } else if(input[i]==')') {
  2.       char t = '\0';
  3.       while((t = pop(st)) != '('){
  4.         c[ic++] = t;
  5.         c[ic++] = ' ';
  6.       }
  7.       i++;

Jeśli jest to (18.) deklarujemy zmienną char, która będzie przechowywać operator zdjęty ze stosu. Wyjaśnienia wymaga tu kolejna linijka (19.). Zdejmuje ze stosu operator i go przypisujemy zmiennej t. Po tym sprawdzamy czy nie jest to (. Jeśli tak to pętla zostanie przerwana, a ( będzie zdjęty ze stosu i nie wypisany. Linijki (20. - 21.) to wypisywanie operatora i znaku spacji do wyjścia.

Przedostatni przypadek dotyczy pobrania operatora z wejścia:

  1.     } else if(priorytet(input[i])!=-1){
  2.       while(!isEmpty(st) && (priorytet(input[i]) <= priorytet(st->element->value))){
  3.         c[ic++] = pop(st);
  4.         c[ic++] = ' ';
  5.       }
  6.       push(st, input[i]);
  7.       i++;

Najpierw (28.) upewniamy się, że wczytujemy operator. Możemy to zrobić sprawdzając wartość funkcji prorytet(), która dla znaków nie operatora zwróci -1. Przed (29.) wrzuceniem wczytanego operatora do stosu musimy sprawdzić czy na stosie nie ma operatorów o niższym priorytecie niż wczytywany operator. Jeśli takie operatory są to wpierw (27. - 28.) musimy je wypisać.

Jeśli jednak znak nie spełnia żadnego wcześniejszego warunku to możliwe, że to np. znak spacji, który nie ma większego dla nas znaczenia, dlatego pominiemy interpretowanie go zwiększając zmienną i:

  1.     } else {
  2.       i++;
  3.     }
  4.   }

Po ostatnim warunku kończy się nasza pętla while, więc zamykamy ją.

  1.   while(!isEmpty(st)){
  2.     c[ic++] = pop(st);
  3.     c[ic++] = ' ';
  4.   }
  5.   st = NULL;
  6.   c[ic] = '\0';
  7.   return c;
  8. }

Przed zwróceniem napisu wyjściowego musimy (36. - 37.) dopisać wszystkie operatory znajdujące się na stosie, aż (35.) będzie pusty. (39.) Zwalniamy pamięć, (40.) dopisujemy znak końca napisu i (41.) zwracamy napis.

Zadania

Zadanie 1

Dodaj alias operatora dzielenia ":".

Zadanie 2

Dodaj alias nawiasów okrągłych ( ), aby na tej samej zasadzie były interpretowane nawiasy kwadratowe [ ].