Nawiasy - pomoc w poprawieniu algorytmu

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;
}

• https://www.cs.cmu.edu/~gilpin/tutorial/
• https://lldb.llvm.org/tutorial.html
• https://tutorials.visualstudio.com/vs-get-started/debugging
• http://wiki.codeblocks.org/index.php?title=Debugging_with_Code::Blocks

Co to znaczy, że A jest poprawne, znaczy poprawnie znawiasowane?

Napiszę Ci w Ruscie by nie było za łatwo:

fn parse(input: &[u8]) -> bool {
    // Zgodnie z treścią zadania nie zdarzy się by było więcej niż 128 symboli w zdaniu
    let mut stack = [0; 128];
    let mut pos = 0;

    for &c in input {
        match c {
            b'(' | b'[' => {
                stack[pos] = c;
                pos += 1;
            }
            b')' if pos != 0 && stack[pos - 1] == b'(' => pos -= 1,
            b']' if pos != 0 && stack[pos - 1] == b'[' => pos -= 1,
            _ => return false,
        }
    }
    pos == 0
}

Playground gdzie możesz to przetestować. Nie przełożysz tego 1:1 na C++, ale daje Ci pogląd jak całość działa.

Poniższy pseudokod (Python) realizuje zadanie (potrzeba CI jeszcze stosu, ale ten w C++ i nie tylko jest):

def match(left, right):
	left_pars = "(["
	right_pars = ")]"
	return left_pars.index(left) == right_pars.index(right)

def checker(expr):
	s = Stack()
	is_balanced = True
	i = 0
	while i < len(expr) and is_balanced:
		token = expr[i]
		if token in "([":
			s.push(token)
		else:
			t = s.pop()
			if not match(t, token):
				is_balanced = False
		i += 1
	if is_balanced and s.is_empty():
		return True
	else:
		return False

Jak to działa, widząc nawias lewy wrzucamy na stos; widząc prawy zrzucamy i sprawdzamy czy typy pasują (czy zamykamy właściwy nawias), jak tak, to dalej, a jak nie to is_balanced staje się False. Na końcu jeśli stos jest pusty i zmienna logiczna jest True, zwracamy True, w przeciwnym wypadku False.