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).

Kodatnik