Odwrotna Notacja Polska - część 1

Odwrotna Notacja Polska to sposób zapisu wyrażeń arytmetycznych za pomocą notacji postfiksowej. Standardowa notacja, z której korzystamy na codzień to notacja infiksowa, argument operator argument (np. 3 + 4). Notacja postfiksowa nie zmienia kolejności argumentów, natomiast zmienia położenie operatorów (występują one po argumentach, których dotyczą). Przykładowy zapis w notacji postfiksowej wyglada tak: 3 4 +. Taki sposób zapisu jest o wiele łatwiejszy do analizy poprawności wyrażenia jak i do jego obliczenia. Wykorzystując stos w prosty sposób możemy dokonać zamiany wyrażenia z postaci infiksowej na postać postfiksową. Algorytm zamiany jest następujący:

• Inicjalizujemy stos,
• Analizujemy wyrażenie infiksowe od lewej do prawej strony,
• Jeżeli element jest argumentem to dodajemy go do wyrażenia postfiksowego,
• Jeżeli element jest operatorem i stos jest pusty to odkładamy go na stos,
• Jeżeli element jest operatorem i stos nie jest pusty to sprawdzamy co jest na wierzchołku stosu i porównujemy z odczytanym elementem. Jeśli operator ze stosu ma mniejszy lub równy priorytet z naszym znakiem to wstawiamy odczytany element na stos, jeśli nie to ściągamy operator ze stosu i dodajemy go do wyrażenia postfiksowego oraz odkładamy odczytany element na stos.
• Jeśli nie ma więcej elementów w wyrażeniu infiksowym to ściągamy ze stosu (o ile nie jest pusty)znajdujące się tam operatory i dodajemy je do wyrażenia postfiksowego.

Przykład zamiany wyrażenia infiksowego na postfiksowe:

Wyrażenie infiksowe: 4 * 2 + 7 / 8

Kolejny znak       Stos      Wyrażenie postfiksowe
     4                                 4
     *             *                   4
     2             *                   4 2
     +             +                   4 2 *
     7             +                   4 2 * 7
     /             + /                 4 2 * 7
     8             + /                 4 2 * 7 8
                                       4 2 * 7 8 / +

Wyrażenie postfiksowe: 4 2 * 7 8 / +

Dla wyrażeń posiadających nawiasy postępujemy według następującego algorytmu:

• Jeżeli odczytany znak jest nawiasem otwierającym to umieszczamy go na stosie,
• Jeżeli odczytany znak jest nawiasem zamykającym to ściągamy ze stosu, aż do napotkania nawiasu otwierającego operatory i dodajemy do wyrażenia postfiksowego,
• Ściągamy ze stosu nawias otwierający.

Przykład zamiany wyrażenia infiksowego z nawiasami na wyrażenie postfiksowe:

Wyrażenie infiksowe: ( 1 + 2 ) * 3

Kolejny znak       Stos      Wyrażenie postfiksowe 
     (             (
     1             (                   1
     +             ( +                 1
     2             ( +                 1 2
     )                                 1 2 +
     *             *                   1 2 +
     3             *                   1 2 + 3
                                       1 2 + 3 *

Wyrażenie postfiksowe: 1 2 + 3 *

Poniżej prosta klasa dokonująca konwersji wyrażeń z postaci infiksowej na postfiksową z wykorzystaniem powyższego algorytmu. Jako stos wykorzystałem klasę biblioteczną Stack. Podział danych wejściowych odbywa się za pomocą klasy StringTokenizer (więcej o tej klasie tu Podział łańcucha na części). Dodatkowo metoda priorytet(String) zwraca priorytet dla poszczególnych operatorów.

// wykorzystujemy klasy Scanner, Stack oraz StringTokenizer z pakietu java.util
import java.util.*;  
/**
 * Odwrotna Notacja Polska
 * Zamiana wyrażeń infiksowych na postfiksowe
 * @author kodatnik.blogspot.com
 */
public class OdwrotnaNotacjaPolska {
 // pola klasy
 private String wyrazenieInfiksowe;
 private String wyrazeniePostfiksowe; 
 
 // konstruktor dokonuje przypisania polom wyrażeń
 public OdwrotnaNotacjaPolska(String wyrazenie) {
  wyrazenieInfiksowe = wyrazenie;
  wyrazeniePostfiksowe = "";
  // wywołujemy metodę dokonującą konwersji
  infiksNaPostfiks();
 }

 // metoda konwertuje wyrażenie w postaci infiksowej na postfiksową
 // wynik operacji jest zapisywany w polu wyrazeniePostfiksowe
 private void infiksNaPostfiks() {
        
  // tworzymy pusty stos
  Stack<String> stos = new Stack<String>();
        
  // dzielimy wyrażenie infiksowe na części na podstawie separatorów
  StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "+-*/()", true);
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {

   // pobieramy element
   String s = st.nextToken();
         
   // jeżeli element jest operatorem
   if( s.equals("+") || s.equals("*") || s.equals("-") || s.equals("/")) {
    // sprawdzemy priorytety
    while(!stos.empty() && priorytet(stos.peek()) >= priorytet(s)) 
     wyrazeniePostfiksowe += stos.pop()  + " ";
     // odkładamy operator na stos
    stos.push(s);
   }
   // jeżeli element jest nawiasem otwierającym
   else if(s.equals("(")) stos.push(s);
   // jeżeli element jest nawiasem zamykającym
   else if(s.equals(")")) {
    // ściągamy operatory ze stosu, aż do nawiasu otwierajęcego
    while(!stos.peek().equals("(")) wyrazeniePostfiksowe += stos.pop() + " ";
    // ściągamy nawias otwierający
    stos.pop();
   }
   // jeżeli element nie jest operatorem ani nawiasem dodajemy go do wyrażenia postfiksowego
   else wyrazeniePostfiksowe += s  + " ";
  }
  // ściągamy ze stosu pozostałe operatory i dodajemy je do wyrażenia postfiksowego
  while(!stos.empty()) wyrazeniePostfiksowe += stos.pop()  + " ";
 } 
  
 // metoda zwraca priorytet operatora
 public static int priorytet(String operator) {
  // dla + i - zwracamy 1
  if(operator.equals("+") || operator.equals("-")) return 1;
  // dla * i / zwracamy 2
  else if(operator.equals("*") || operator.equals("/")) return 2;
  // dla pozostałych 0
  else return 0;
 }
 
 // metoda zwraca nam łańcuch tekstowy z wyrażeniem w formie postfiksowej
 public String toString() {
  return wyrazeniePostfiksowe;
 }

 public static void main(String args[]) {

  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie infiksowe: " );
 
  // pobieramy od użytkownika wyrażenie
  String wyrazenie = sc.nextLine();

  // tworzymy nowy obiekt klasy OdwrotnaNotacjaPolska 
  // i przekazujemy do konstruktora pobrane od użytkownika wyrażenie
  OdwrotnaNotacjaPolska onp = new OdwrotnaNotacjaPolska(wyrazenie);

  // wyświetlamy wyrażenie w postaci postfiksowej
  System.out.println ("Wyrażenie postfiksowe: " + onp);
 }
}

Wynik działania aplikacji:

Podaj wyrażenie infiksowe: (4+2)*(3-1)
Wyrażenie postfiksowe: 4 2 + 3 1 - * 

Dodatkowo możemy jeszcze sprawdzać poprawność nawiasów w podanym przez użytkownika wyrażeniu infiksowym (zobacz: Sprawdzanie poprawności nawiasów). W kolejnej części spróbujemy obliczyć wartość wyrażenia w postaci postfiksowej.