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.

pokaż źródło

drukujpomoc

01.// wykorzystujemy klasę Scanner z pakietu java.util

02.import java.util.*;

03. 

04./**

05. * Sprawdzanie poprawności nawiasów

06. * Wykorzystujemy utworzoną wcześniej klasę Stos

07. *

08. * @author kodatnik.blogspot.com

09. */

10.public class PoprawnoscNawiasow {

11.  

12. // metoda sprawdza czy nawiasy w przekazanym jako parametr wyrażeniu są poprawne

13. // obsługiwane są nawiasy okrągłe, kwadratowe i klamrowe

14. // zwraca true dla poprawnych i false dla niepoprawnych

15. public static boolean czyPoprawne(String wyrazenie) {

16.    

17.  // dwie tablice przechowujące nawiasy otwierające i zamykające

18.  char[] otwierajace  = {'(', '[', '{'};

19.  char[] zamykajace   = {')', ']', '}'};

20.      

21.  // tworzymy stos o rozmiarze naszego wyrażenia

22.  Stos stos = new Stos(wyrazenie.length());

23.         

24.  // pętla dla każdego znaku znajdującego się w wyrażeniu   

25.  for (int i = 0; i < wyrazenie.length(); i++) {

26.    

27.   // jeżeli znak jest nawiasem otwierającym odkładamy go na stos

28.   for (int j = 0; j < otwierajace.length; j++ ){

29.    if ( wyrazenie.charAt(i) == otwierajace[j]) stos.push((int) otwierajace[j]);

30.   }

31.          

32.   // jeżeli znak jest nawiasem zamykającym porównujemy go z wartością ze stosu

33.   for (int j = 0; j < zamykajace.length; j++ ){

34.    if ( wyrazenie.charAt(i) == zamykajace[j]) {

35.     // jeśli stos jest pusty zwracamy fałsz

36.     if (stos.czyPusty()) return false;

37.     // jeśli nawiasy nie są tego samego typu zwracamy fałsz

38.     if (((char) stos.pop()) != otwierajace[j]) return false;

39.    }

40.   }        

41. 

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

43. 

44.   }

45.  // zwracamy true albo false (stos pusty - wszystkie nawiasy są poprawne)

46.  return stos.czyPusty();

47. }

48.  

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

50.         

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

52.  System.out.print ("Podaj wyrażenie z nawiasami: ");

53.  

54.  // pobieramy od użytkownika wyrażenie z nawiasami

55.  String wyrazenie = sc.nextLine();

56.         

57.  // wyświetlamy informacje o poprawności wyrażenia z nawiasami

58.  System.out.println("Wyrażenie jest " + (czyPoprawne(wyrazenie) ? "poprawne." : "niepoprawne."));

59. }

60.}

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.