Odwrotna Notacja Polska - część 2

W poprzedniej części (Odwrotna Notacja Polska - część 1) dokonaliśmy zamiany wyrażenia w formie infiksowej na postać postfiksową (czyli formę w Odwrotnej Notacji Polskiej). W tym wpisie spróbujemy dokonać sprawdzenia poprawności nawiasów występujących w wyrażeniu infiksowym oraz obliczymy wartość wyrażenia postfiksowego. Do sprawdzenia poprawności nawiasów w wyrażeniu infiksowym użyjemy stosu (więcej na ten temat - Sprawdzanie poprawności nawiasów). Jeśli wyrażenie nie będzie poprawne pod wartość wyrażenia postfiksowego podstawimy odpowiedni napis (klasa String - "Niepoprawne nawiasy w wyrażeniu infiksowym"). Nasza metoda sprawdzająca poprawność nawiasów będzie metodą prywatną:

// metoda sprawdza poprawność nawiasów w wyrażeniu infiksowym
private boolean czyPoprawneNawiasy() {
 // tworzymy 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 znak jest nawiasem otwierającym odkładamy go na stos
  if(s.equals("(")) stos.push(s);
  // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu            
  if(s.equals(")")) {
   if (stos.isEmpty()) return false;
   if (!stos.pop().equals("(")) return false;
  }
 }
 // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
 return stos.isEmpty();         
}

Po sprawdzeniu poprawności nawiasów możemy już dokonać obliczenia wartości wyrażenia postfiksowego według następującego algorytmu:

• Inicjalizujemy stos,
• Analizujemy wyrażenie postfiksowe od lewej do prawej strony,
• Jeżeli element jest argumentem to odkładamy go na stos,
• Jeżeli element jest operatorem to ściągamy ze stosu dwie wartości, wykonujemy działanie, odkładamy na stos wynik,
• Jeżeli dotarliśmy do końca wyrażenie postfiksowego, ściągamy wartość ze stosu (jest to obliczona wartość wyrażenia postfiksowego).

Przykład obliczenia wartości wyrażenia postfiksowego:

Wyrażenie infiksowe: (4*2)+(15/3)
Wyrażenie postfiksowe: 4 2 * 15 3 / + 

kolejny znak stos operacja
     4          4       odkładamy na stos
     2          4 2     odkładamy na stos
     *          8       ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(4*2), odkładamy ją na stos
     15         8 15    odkładamy na stos
     3          8 15 3  odkładamy na stos
     /          8 5     ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(15/3), odkładamy ją na stos
     +          13      ściągamy ze stosu dwie wartości i obliczamy
                        wartość wyrażenia(8+5), odkładamy ją na stos
                        ściągamy ze stosu wynik końcowy (13)

Obliczona wartość wyrażenia postfiksowego: 13

Poniżej metoda obliczająca wartość wyrażenia postfiksowego. Operujemy na wartościach typu double.

// metoda oblicza wartość wyrażenia postfiksowego
private double oblicz() {
  
 // tworzymy pusty stos
 Stack<Double> stos = new Stack<Double>();
        
 // dzielimy wyrażenie postfiksowe na elementy na podstawie spacji
 StringTokenizer st = new StringTokenizer(wyrazeniePostfiksowe, " ");
        
 // dopóki są elementy w wyrażeniu wejściowym
 while(st.hasMoreTokens()) {
  // pobieramy element
  String s = st.nextToken();
  
  // jeśli element nie jest operatorem (czyli jest wartością)
  if (!s.equals("+") && !s.equals("*") && !s.equals("-") && !s.equals("/")) {
   // zamieniamy łańcuch na liczbę
   double wartosc = Double.parseDouble(s);
   // odkładamy wartość na stos
   stos.push(wartosc);
  }
  else {
   //  jeśli element jest operatorem ściągamy dwie wartości ze stosu
   double wartosc1 = stos.pop();
   double wartosc2 = stos.pop();
   // w zależności od operatora obliczamy wynik i odkładamy go na stos
   switch(s.charAt(0)) {
    case '*': {stos.push(wartosc2 * wartosc1); break;}
    case '+': {stos.push(wartosc2 + wartosc1); break;}
    case '-': {stos.push(wartosc2 - wartosc1); break;}
    case '/': {stos.push(wartosc2 / wartosc1); break;}
   }
  }
 }
 // zwracamy końcowy wynik
 return stos.pop();
}

Cała klasa OdwrotnaNotacjaPolska:

// wykorzystujemy klasy Scanner, Stack<E> 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; 
 private double wynik;   
 
 // konstruktor dokonuje przypisania polom wyrażeń
 public OdwrotnaNotacjaPolska(String wyrazenie) {
  this.wyrazenieInfiksowe = wyrazenie;
  wyrazeniePostfiksowe = "";
  wynik = 0.0;
  if(!czyPoprawneNawiasy())
   wyrazeniePostfiksowe = "Niepoprawne nawiasy w wyrażeniu infiksowym";
  else {
   // wywołujemy metodę dokonującą konwersji
   infiksNaPostfiks();
   wynik = oblicz();
  }   
 }

 // metoda zwraca wyrażenie w formie infiksowej
 public String pobierzWyrazenieInfiksowe() {
  return wyrazenieInfiksowe;
 }

 // metoda zwraca wyrażenie w formie postfiksowej
 public String pobierzWyrazeniePostfiksowe() {
  return wyrazeniePostfiksowe;
 }
 
 // metoda zwraca obliczoną wartość wyrażenia postfiksowego
 public double pobierzWynik() {
  return wynik;
 }
 
 // metoda sprawdza poprawność nawiasów w wyrażeniu infiksowym
 private boolean czyPoprawneNawiasy() {
  // tworzymy 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 znak jest nawiasem otwierającym odkładamy go na stos
   if(s.equals("(")) stos.push(s);
   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu            
   if(s.equals(")")) {
    if (stos.isEmpty()) return false;
    if (!stos.pop().equals("(")) return false;
   }
  }
  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
  return stos.isEmpty();         
 }

 // 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("/")) {
    // sprawdzamy 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 oblicza wartość wyrażenia postfiksowego
 private double oblicz() {
  
  // tworzymy pusty stos
  Stack<Double> stos = new Stack<Double>();
        
  // dzielimy wyrażenie postfiksowe na elementy na podstawie spacji
  StringTokenizer st = new StringTokenizer(wyrazeniePostfiksowe, " ");
        
  // dopóki są elementy w wyrażeniu wejściowym
  while(st.hasMoreTokens()) {

   // pobieramy element
   String s = st.nextToken();
  
   // jeśli element nie jest operatorem (czyli jest wartością)
   if (!s.equals("+") && !s.equals("*") && !s.equals("-") && !s.equals("/")) {
    // zamieniamy łańcuch na liczbę
    double wartosc = Double.parseDouble(s);
    // odkładamy wartość na stos
    stos.push(wartosc);
   }
   else {
    //  jeśli element jest operatorem ściągamy dwie wartości ze stosu
    double wartosc1 = stos.pop();
    double wartosc2 = stos.pop();
    // w zależności od operatora obliczamy wynik i odkładamy go na stos
    switch(s.charAt(0)) {
     case '*': {stos.push(wartosc2 * wartosc1); break;}
     case '+': {stos.push(wartosc2 + wartosc1); break;}
     case '-': {stos.push(wartosc2 - wartosc1); break;}
     case '/': {stos.push(wartosc2 / wartosc1); break;}
    }
   }
  }
  // zwracamy końcowy wynik
  return stos.pop();
 }
 
 // metoda zwraca nam łańcuch tekstowy z wyrażeniem 
 // w formie postfiksowej, oraz wynik
 public String toString() {
  return wyrazeniePostfiksowe + "\nWynik: " + wynik;
 }
}

Poniżej przykład wykorzystania klasy.

public class TestONP {
 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);
 }
}

Wyniki działania aplikacji:

Podaj wyrażenie infiksowe: (4*2)+(15/3)
Wyrażenie postfiksowe: 4 2 * 15 3 / + 
Wynik: 13.0

Podaj wyrażenie infiksowe: (3+4)*2)
Wyrażenie postfiksowe: Niepoprawne nawiasy w wyrażeniu infiksowym

Podaj wyrażenie infiksowe: ((1+2)-2.5)*8/2
Wyrażenie postfiksowe: 1 2 + 2.5 - 8 * 2 / 
Wynik: 2.0

Nasza klasa nie obsługuje poprawnie sytuacji wyjątkowych oraz ma małą liczbę operatorów (można się pokusić o dodanie operacji potęgowania, pierwiastkowania czy też funkcji trygonometrycznych).