Na wejściu dane jest wyrażenie W składające się z nawiasów () oraz []. Poprawność wyrażeń tego typu określona jest za pomocą następujących reguł:
wyrażenie puste jest poprawne,
jeśli A oraz B są poprawne, AB jest poprawne,
jeśłi A jest poprawne, (A) oraz [A] są poprawne.
Napisz program, który przeczyta ze standardowego ciąg napisów reprezentujących opisane powyżej wyrażenia a następnie zweryfikuje ich poprawność. Możesz założyć, że przetwarzane wyrażenia nie będą dłuższe niż 128 znaków.
Wejście
Pierwszy wiersz wejścia zawiera liczbę naturalną N. Kolejnych N wierszy zawiera napisy reprezentujące wyrażenia składające się z nawiasów () oraz [].
Wyjście
Dla każdego poprawnego wyrażenia program powinien wydrukować na standardowym wyjściu TAK, natomiast dla każdego niepoprawnego wyrażenia - NIE.
Przykładowe wejście
3
([])
(([()])))
([()])()
Przykładowe wyjście
TAK
NIE
TAK
#include <iostream>
#include <stack>
#include<string>
using namespace std;
bool nawiasy(char otwarty, char zamkniety)
{
if(otwarty == '(' && zamkniety == ')' ) return true;
else if(otwarty == '[' && zamkniety == ']') return true;
return false;
}
bool czypoprawnynawias(string nw)
{
stack <char> S;
for(int i=0;i<128;i++)
{
if(nw[i] == '(' || nw[i] == '[')
S.push(nw[i]);
else if(nw[i] == ')' || nw[i] == ']')
{
if(S.empty() || !nawiasy(S.top(),nw[i]))
return false;
else
S.pop();
}
}
return S.empty()? true:false;
}
int main()
{
int n;
cout << "Podaj liczbe naturalna ";
cin>> n;
string naw;
cout<< "podaj nawiasy : " ;
cin >> naw;
cout<<n<<"\n";
if (czypoprawnynawias(naw))
cout<<" TAK : " ;
else
cout <<" NIE : ";
return 0;
}