Sprawdzanie poprawności nawiasów

Do sprawdzenia poprawności umiejscowienia nawiasów w wyrażeniu posłużymy się przedstawioną wcześniej klasą Stos (Stos - implementacja tablicowa). Sam algorytm jest stosunkowo prosty. Bierzemy element wyrażenia, jeśli jest to nawias otwierający odkładamy go na stos, jeśli nawias zamykający ściągamy ze stosu element i porównujemy czy razem stanowią parę, jeśli tak idziemy dalej, jeśli nie kończymy działanie algorytmu. Znaki nie będące nawiasami ignorujemy. Wyrażenie jest poprawne pod względem nawiasów, jeśli po przejściu przez wszystkie elementy stos będzie pusty. Poniżej krótka aplikacja sprawdzająca pobrane od użytkownika wyrażenie. Obsługiwane są nawiasy okrągłe, kwadratowe oraz klamrowe.

// wykorzystujemy klasę Scanner z pakietu java.util
import java.util.*;

/**
 * Sprawdzanie poprawności nawiasów 
 * Wykorzystujemy utworzoną wcześniej klasę Stos
 *
 * @author kodatnik.blogspot.com
 */
public class PoprawnoscNawiasow {
 
 // metoda sprawdza czy nawiasy w przekazanym jako parametr wyrażeniu są poprawne
 // obsługiwane są nawiasy okrągłe, kwadratowe i klamrowe
 // zwraca true dla poprawnych i false dla niepoprawnych
 public static boolean czyPoprawne(String wyrazenie) {
   
  // dwie tablice przechowujące nawiasy otwierające i zamykające
  char[] otwierajace  = {'(', '[', '{'};
  char[] zamykajace   = {')', ']', '}'};
     
  // tworzymy stos o rozmiarze naszego wyrażenia
  Stos stos = new Stos(wyrazenie.length());
        
  // pętla dla każdego znaku znajdującego się w wyrażeniu    
  for (int i = 0; i < wyrazenie.length(); i++) {
   
   // jeżeli znak jest nawiasem otwierającym odkładamy go na stos
   for (int j = 0; j < otwierajace.length; j++ ){
    if ( wyrazenie.charAt(i) == otwierajace[j]) stos.push((int) otwierajace[j]);
   }
         
   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu
   for (int j = 0; j < zamykajace.length; j++ ){
    if ( wyrazenie.charAt(i) == zamykajace[j]) {
     // jeśli stos jest pusty zwracamy fałsz
     if (stos.czyPusty()) return false;
     // jeśli nawiasy nie są tego samego typu zwracamy fałsz
     if (((char) stos.pop()) != otwierajace[j]) return false;
    } 
   }         

   // ignorujemy znaki, które nie są nawiasami

   }
  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)
  return stos.czyPusty();
 }
 
 public static void main(String[] args) {
        
  Scanner sc = new Scanner(System.in);
  System.out.print ("Podaj wyrażenie z nawiasami: ");
 
  // pobieramy od użytkownika wyrażenie z nawiasami
  String wyrazenie = sc.nextLine();
        
  // wyświetlamy informacje o poprawności wyrażenia z nawiasami
  System.out.println("Wyrażenie jest " + (czyPoprawne(wyrazenie) ? "poprawne." : "niepoprawne."));
 }
}

Przykładowe uruchomienia aplikacji:

Podaj wyrażenie z nawiasami: (a[b{c}d]e)
Wyrażenie jest poprawne.

Podaj wyrażenie z nawiasami: [a(b{c})
Wyrażenie jest niepoprawne.

Podaj wyrażenie z nawiasami: (([a]b)}
Wyrażenie jest niepoprawne.

Modyfikując tablicę z nawiasami możemy sprawdzać poprawność wyrażeń z dowolnymi znakami otwierającymi i zamykającymi.