Poprawność Nawiasów

Wstęp

Każdy nawias, który został otwarty musi zostać zamknięty. Nie zamknięcie nawiasu może skutkować błędem obliczeń, a w przypadku programowania błędem kompilacji. Istnieje jednak szybka metoda, która pozwala na sprawdzenie czy nie brakuje jakiegoś nawiasu. Sposób implementacji różni się w zależności od tego co przyjmiemy, że może występować jako nawias.

Tylko jeden rodzaj nawiasu

Przyjmijmy, że w równaniu może występować tylko jeden rodzaj nawiasu. W celu sprawdzenia czy dane wyrażenie jest poprawne należy sprawdzic czy każdemu nawiasowi '(' został przyporządkowany nawias ')'. Niezależnie od tego jak zostaną ustawione wystarczy sprawdzić czy jest tyle samo lewych nawiasów co prawych. Weźmy przykładowo "a(b+c)". Jest to poprawne wyrażenie, bo jest jeden nawias taki i jeden taki, ale już "((())))" nie jest poprawne, ponieważ zostały otwarte tylko 3 nawiasy, a zostały zamknięte 4.

Funkcja czyPoprawne() sprawdza czy w przekazanym łańcuchu znaków wszystkie nawiasy zostały otwarte oraz zamknięte i zwraca wynik jako wartość logiczną.

1. bool czyPoprawne(string slowo) {
2.   int ile = 0;
3.   for (int i = 0; i < slowo.length(); i++) {
4.     switch (slowo[i]) {
5.       case '(': ile++; break;
6.       case ')': ile--; break;
7.       default: break;
8.     }
9.   }
10.   return ile == 0;
11. }

(2.) Na początku inicjalizowana jest zmienna ile - jest to licznik, który posłuży do zliczania nawiasów. Następnie w pętli (3. - 9.) sprawdzane są kolejne znaki. (4.) W zależności od tego, który nawias znajduje się pod i-tym indeksem to (5.) licznik jest zwiększany, albo (6.) zmniejszany. Na koniec (10.) zwracany jest wynik porównania licznika do zera, ponieważ jeśli tyle wynosi to znaczy, że wystąpiło tyle samo nawiasów otwierających co zamykających.

Różne nawiasy

Sprawdzanie poprawności kiedy dopuszczamy różne nawiasy dalej ma tę samą ideę co poprzednio to znaczy każdy nawias oddzielnie musi mieć dokładnie tyle samo początków i zakończeń. Prawidłowy jest np. zapis "([])", ale już nie "([)]", ponieważ niewiadomo, który nawias zinterpretować, a jeśli nawet zostanie podjęta decyzja to jak potraktować obcy nawias.

Rozpatrzmy bliżej przykład "([])". Na początku napotykamy '(', więc oczekujemy później znaleźć ')'. Jednak następny znak to '[', więc tym razem oczekujemy wczytać ']'. Oznacza to, że trzeba pamiętać jakie znaki powinny zostać wczytane (w dalszej części). Do tego można wykorzystać listę, albo stos. Dalej postępowanie polega na tym, że należy zapamiętać nawias otwierający i zdjąć go jeśli natrafimy na jego odpowiednik zamykający. Należy jednak pamiętać, że jeśli natrafimy na nawias zamykający, ale nie jest on ostatnim elementem na liście to znaczy, że nawiasy są nieprawidłowo. Oczywiście warunkiem końcowym jest to, że lista po przeszukaniu tekstu jest pusta.

W celu rozpoznania nawiasów początkowych i końcowych potrzebne jest przekazanie programowi par znaków, które razem tworzą nawias. Ze względu na to, że nawiasów jest wiele rodzajów to pisanie warunków dla każdego oddzielnie byłoby bardzo czasochłonne i możnaby popełnić błąd. Przypuśćmy, że funkcja czyPoprawne() dodatkowo będzie posiadać słowo w którym będą kolejne zapisane pary nawiasów. Każdy znak na pozycji parzystej oznaczałby nawias początkowy, a następny w słowie byłby nawias końcowy (czyli pod indeksami nieparzystymi).

Funkcja czyPoprawne() przyjmuje dwa argumenty: slowo - wyrażenie do sprawdzenia poprawności oraz arg - słowo zawierające kolejne pary nawiasów, domyślnie przyjmuje cztery rodzaje nawiasów, ale można też zdefiniować własne. Wynikiem działania funkcji jest wartość logiczna czy dane wyrażenie jest poprawne.

1. bool czyPoprawne(string slowo, string arg = "()[]{}<>") {
2.   vector<char> lista;
3.   for (int i = 0; i < slowo.length(); i++) {
4.     int poz = arg.find(slowo[i]);
5.     if (poz == string::npos)
6.       continue;
7.     if (poz % 2 == 0) {
8.       lista.push_back(arg[poz + 1]);
9.     } else {
10.       if (lista.size() == 0 || lista.back() != slowo[i])
11.         return false;
12.       lista.pop_back();
13.     }
14.   }
15.   return lista.size() == 0;
16. }

(2.) Początkowo lista jest pusta. Potem (3.) dla każdego kolejnego znaku (4.) szukamy jego pozycji w argumencie z podanymi nawiasami. (5.) Jeśli znak ten nie występuje to (6.) pomijamy go. Jeśli jest to znaczy, że jest początkiem lub końcem nawiasu. (7.) Jeśli indeks jest parzysty to znaczy, że (8.) wrzucamy na stos znak, który jest końcem danego początku nawiasu. (9.) Dla nieparzystych: (10.) sprawdzamy czy lista nie jest pusta oraz czy nie jest to inne zakończenie nawiasu niż oczekiwaliśmy. Jeśli którykolwiek warunek zostanie spełniony to należy zwrócić, że wyrażenie jest niepoprawne. W przeciwnym razie (12.) pozostaje zdjęcie znaku z listy i przejście dalej.

Testowanie funkcji

Poniższy fragment wczytuje od użytkownika wyrażenie do sprawdzenia, wywołuje sprawdzenie i wypisuje komunikat zrozumiały dla użytkownika.

1. int main() {
2.   string s = "";
3.   cout << "Podaj wyrazenie:" << endl;
4.   getline(cin, s);
5.   bool w = czyPoprawne(s);
6.   cout << "Wyrazenie jest " << (w ? "" : "nie") << "poprawne";
7.   system("pause");
8.   return 0;
9. }

• Kod źródłowy Jeden rodzaj nawiasu
• Kod źródłowy Różne nawiasy