Odwrotna Notacja Polska

-- Sebastian Pawlak, 2003.

Najczęściej spotykane funkcje przekształcania wyrażenia zapisanego w notacji nawiasowej do wyrażenia zapisanego w Odwrotnej Notacji Polskiej wykorzystują aglorytm rekurencyjny. W sekcji tej prezentuję inny, bardzo zgrabny, algorytm z wykorzystaniem stosu.

Algorytm przekształcania wyrażenia zapisanego w notacji nawiasowej do tożsamego zapisanego w Odwrotnej Notacji Polskiej:

Krok 1
Jeżeli nie ma więcej znaków w ciągu wejściowym, to realizuj krok 6; w przeciwnym razie, przeczytaj następny element (nawias, operator lub argument) i nazwij go x.

Krok 2
Jeżeli x jest argumentem, to zapisz go w ciągu wyjściowym, umieść po nim spację i przejdź do realizacji kroku 1.

Krok 3
Jeżeli x jest nawiasem otwierającym, wpisz go na stos i realizuj krok 1. Jeżeli x jest nawiasem zamykającym, przejdź do realizacji kroku 4, a w przeciwnym razie - kroku 5.

Krok 4
Jeżeli na wierzchu stosu nie ma nawiasu otwierającego, to wycofaj ten obiekt ze stosu wpisując go do ciągu wyjściowego, a zaraz za nim wpisz spację i przejdź do wykonywania kroku 4. Jeżeli na wierzchołku stosu jest nawias otwierający, to wycofaj go ze stosu i przejdź do realizacji kroku 1.

Krok 5
W przypadku, gdy priorytet elementu wierzchołkowego stosu jest większy lub równy priorytetowi x, wycofaj element z wierzchołka stosu, wpisz go do ciągu wyjściowego, a potem wpisz za nim znacznik i powtórz krok 5. W przeciwnym razie, połóż x na wierzchołek stosu i wróć do wykonywania kroku 1.

Krok 6
Opróżnij stos po jednym elemencie, wpisując każdy z nich do ciągu wyjściowego i wstawiając między nimi spację; i to już koniec.

Oto jak zaimplementowałem przedstawiony algorytm:

Kod źródłowy pliku "onp.c":

/* konwerterONP: przeksztalca wyrazenie zapisane w notacji nawiasowej do
 *               wyrazenia w Odwrotnej Notacji Polskiej;
 *               obslugiwane operatory: ^ * / + -
 *               obsluguje liczby zmiennoprzecinkowe
 *               przyklad: 0.5+3*(2^3)/(2-1)            <- wejscie
 *                         0.5 3 2 3 ^ * 2 1 - / +      <- wyjscie
 *
 *               Algorytm przeksztalcania do ONP:
 *               1. Jezeli nie ma wiecej znakow w ciagu wejsciowym, to realizuj
 *                  kork 6. W przeciwnym razie, przeczytaj nastepny element
 *                  (nawias, operator lub argument) i nazwij go "x".
 *               2. Jezeli "x" jest argumentem, to zapisz go w ciagu wyjsciowym,
 *                  umiesc po nim spacje i przejdz do realizacji kroku 1.
 *               3. Jezeli "x" jest nawiasem otwierajacym, wpisz go na stos
 *                  i realizuj krok 1. Jezeli "x" jest nawiasem zamykajacym,
 *                  przejdz do realizacji kroku 4, a w przeciwnym razie kroku 5.
 *               4. Jezeli na wierzchu stosu nie ma nawiasu otwierajacego, to
 *                  wycofaj ten obiekt ze stosu wpisujac go do ciagu
 *                  wyjsciowego, a zaraz za nim wpisz spacje i przejdz do
 *                  wykonywania kroku 4. Jezeli na wierzcholku stosu jest
 *                  nawias otwierajacy, to wycofaj go ze stosu i przejdz
 *                  do realizacji kroku 1.
 *               5. W przypadku, gdy priorytet elementu wierzcholkowego
 *                  stosu jest wiekszy lub rowny priorytetowi "x", wycofaj
 *                  element z wierzcholka stosu, wpisz go do ciagu wyjsciowego,
 *                  a potem wpisz za nim znacznik i powtorz krok 5. W przeciwnym
 *                  razie, poloz "x" na wierzcholek stosu i wroc do wykonywania
 *                  kroku 1.
 *               6. Oproznij stos po jednym elemencie, wpisujac kazdy z nich do
 *                  ciagu wyjsciowego i wstawiajac miedzy nimi spacje.
 */
void konwerterONP(char *wynik, char *s)
{
    char x, y;

    while (x = *s++) {                                     /* krok 1 */
        if (((x >= '0') && (x <= '9')) || (x == '.')) {    /* krok 2 */
            /* kopiowanie calej liczby z wejscia na wyjscie */
            do
                *wynik++ = x;
            while (x = *s, (((x >= '0') && (x <= '9')) || (x == '.')) && s++);
            *wynik++ = ' ';

	} else if (x == '(')                               /* krok 3 */
            push((double)'(');

	else if (x == ')')                                 /* krok 4 */
            while ((y = (char)pop()) != '(')
                *wynik++ = y, *wynik++ = ' ';

	else {                                             /* krok 5 */
            while (y = (char)pop(),
                   y && ((y == '^') ||
                         ((y == '*') || (y == '/')) && (x != '^') ||
                         ((y == '+') || (y == '-')) && (x != '*') &&
                                           (x != '/') && (x != '^')))
                *wynik++ = y, *wynik++ = ' ';

            push((double)y);
            push((double)x);
        }
    }

    while (x = (char)pop())                                /* krok 6 */
        *wynik++ = x, *wynik++ = ' ';
    
    *wynik = '\0';    /* zakonczenie lancucha wyjsciowego */
}

Kod źródłowy pliku "stos.h":

/* stos.h: plik naglowkowy biblioteki z implementacja stosu.
 * Sebastian Pawlak, 2002
 */

#ifndef _STOS_H
#define _STOS_H

void push(double);
double pop(void);

#endif

Kod źródłowy pliku "stos.c":

/* stos.c: biblioteka z implementacja stosu.
 * Sebastian Pawlak, 2002
 */
#include <stdio.h>
#include "stos.h"

#define MAX_STOS 512 /* maksymalny rozmiar stosu */

double stos[MAX_STOS];
int sp = 0; /* wskaznik kolejnego wolnego miejsca na stosie */


/* push: wstawia element na stos */
void push(double element)
{
    if (sp < MAX_STOS)
        stos[sp++] = element;
    else
	printf("push: Przepelnienie stosu!\n");
}


/* pop: zdejmuje element ze stosu */
double pop(void)
{
    if (sp > 0)
        return stos[--sp];

    return 0;
}