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.

pokaż źródło

drukujpomoc

01.// wykorzystujemy klasy Scanner, Stack oraz StringTokenizer z pakietu java.util

02.import java.util.*; 

03./**

04. * Odwrotna Notacja Polska

05. * Zamiana wyrażeń infiksowych na postfiksowe

06. * @author kodatnik.blogspot.com

07. */

08.public class OdwrotnaNotacjaPolska {

09. // pola klasy

10. private String wyrazenieInfiksowe;

11. private String wyrazeniePostfiksowe;

12.  

13. // konstruktor dokonuje przypisania polom wyrażeń

14. public OdwrotnaNotacjaPolska(String wyrazenie) {

15.  wyrazenieInfiksowe = wyrazenie;

16.  wyrazeniePostfiksowe = "";

17.  // wywołujemy metodę dokonującą konwersji

18.  infiksNaPostfiks();

19. }

20. 

21. // metoda konwertuje wyrażenie w postaci infiksowej na postfiksową

22. // wynik operacji jest zapisywany w polu wyrazeniePostfiksowe

23. private void infiksNaPostfiks() {

24.         

25.  // tworzymy pusty stos

26.  Stack<String> stos = new Stack<String>();

27.         

28.  // dzielimy wyrażenie infiksowe na części na podstawie separatorów

29.  StringTokenizer st = new StringTokenizer(wyrazenieInfiksowe, "+-*/()", true);

30.         

31.  // dopóki są elementy w wyrażeniu wejściowym

32.  while(st.hasMoreTokens()) {

33. 

34.   // pobieramy element

35.   String s = st.nextToken();

36.          

37.   // jeżeli element jest operatorem

38.   if( s.equals("+") || s.equals("*") || s.equals("-") || s.equals("/")) {

39.    // sprawdzemy priorytety

40.    while(!stos.empty() && priorytet(stos.peek()) >= priorytet(s))

41.     wyrazeniePostfiksowe += stos.pop()  + " ";

42.     // odkładamy operator na stos

43.    stos.push(s);

44.   }

45.   // jeżeli element jest nawiasem otwierającym

46.   else if(s.equals("(")) stos.push(s);

47.   // jeżeli element jest nawiasem zamykającym

48.   else if(s.equals(")")) {

49.    // ściągamy operatory ze stosu, aż do nawiasu otwierajęcego

50.    while(!stos.peek().equals("(")) wyrazeniePostfiksowe += stos.pop() + " ";

51.    // ściągamy nawias otwierający

52.    stos.pop();

53.   }

54.   // jeżeli element nie jest operatorem ani nawiasem dodajemy go do wyrażenia postfiksowego

55.   else wyrazeniePostfiksowe += s  + " ";

56.  }

57.  // ściągamy ze stosu pozostałe operatory i dodajemy je do wyrażenia postfiksowego

58.  while(!stos.empty()) wyrazeniePostfiksowe += stos.pop()  + " ";

59. }

60.   

61. // metoda zwraca priorytet operatora

62. public static int priorytet(String operator) {

63.  // dla + i - zwracamy 1

64.  if(operator.equals("+") || operator.equals("-")) return 1;

65.  // dla * i / zwracamy 2

66.  else if(operator.equals("*") || operator.equals("/")) return 2;

67.  // dla pozostałych 0

68.  else return 0;

69. }

70.  

71. // metoda zwraca nam łańcuch tekstowy z wyrażeniem w formie postfiksowej

72. public String toString() {

73.  return wyrazeniePostfiksowe;

74. }

75. 

76. public static void main(String args[]) {

77. 

78.  Scanner sc = new Scanner(System.in);

79.  System.out.print ("Podaj wyrażenie infiksowe: " );

80.  

81.  // pobieramy od użytkownika wyrażenie

82.  String wyrazenie = sc.nextLine();

83. 

84.  // tworzymy nowy obiekt klasy OdwrotnaNotacjaPolska

85.  // i przekazujemy do konstruktora pobrane od użytkownika wyrażenie

86.  OdwrotnaNotacjaPolska onp = new OdwrotnaNotacjaPolska(wyrazenie);

87. 

88.  // wyświetlamy wyrażenie w postaci postfiksowej

89.  System.out.println ("Wyrażenie postfiksowe: " + onp);

90. }

91.}

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.