Algorytm w C++ - liczenie stopnia zagnieżdżenia nawiasów

0

Witajcie :) Już raz zwracałem się do Was o pomoc - liczę, że i tym razem mnie odpowiednio nakierujecie. Ostatnio dla sportu zacząłem myśleć o programie, który liczy stopień zagnieżdżenia nawiasów. Chodzi o wymyślenie odpowiedniego algorytmu, działającego oczywiście dla wszystkich przypadków. Zupełnie nie rozumiem dlaczego program po wpisaniu '( ) ( ( ) ) )' (bez spacji) wypluwa stopień równy 1. Byłem przekonany, że algorytm działa w porządku, jednak teraz nie jestem już taki pewien...

 #include <iostream>

using namespace std;

int main()
{
char nawias[100];
int i=0, j=0, level = 0, n = 0;

cout << "Podaj szesc nawiasow: " << endl;

for(i=0;i<6;i++) {
    cin >> nawias[i];
}


for(i=0;i<1000;i++)
{
    if ( nawias[i]=='[' || nawias[i]=='(' || nawias[i]=='{' )
    {
        n=1;
        j++;
        level++;
    }
    else if ( nawias[i]==']' )
    {
        if(nawias[ j - n ] == '[')
        {
            nawias[ j - n ] = 1;
            n++;
            break;
        }
        else if (nawias[ j - n ] == 1) n++;
        else {cout << "NIE ]" << i << endl; break;}
    }
    else if ( nawias[i]==')' )
    {
        if(nawias[ j - n ] == '(')
        {
            nawias[ j - n ] = 1;
            n++;
            break;
        }
        else if (nawias[ j - n ] == 1) n++;
        else {cout << "NIE )" << i << endl; break;}
    }
    else if ( nawias[i]=='}' )
    {
        if(nawias[ j - n ] == '{' )
        {
            nawias[ j - n ] = 1;
            n++;
            break;
        }
        else if (nawias[ j - n ] == 1) n++;
        else {cout << "NIE }" << i << endl; break;}
    }

    else break;
}

cout << "Poziom zagniezdzenia nawiasow to: "<< level << " "<< endl;

return 0;
}

Czy ktoś widzi, dlaczego tak jest? Ja już spędziłem wystarczająco dużo czasu nad tym problemem. Proszę o pomoc. Dzięki wielkie! :)

PS: Program w domyśle będzie korzystał z funkcji, jednak obecnie jest to zaledwie szkic. Dlatego część kodu się powtarza aż trzy razy :)

0

Algorytm jest absolutnie bezsensowny. Zastanów się jeżeli masz początek "({[" to teraz n u ciebie powinna być 1, 2 czy 3?
Stwórz sobie stos (nawet możesz użyć do tego celu tej samej tablicy).
Jak przychodzi nawias otwierający to wrzucasz go na stos.
Jak przychodzi nawias zamykający to pobierasz nawias ze stosu, jeżeli stos pusty to błąd, jeżeli to odpowiedni nawias to zwiększasz poziom, jeżeli nie odpowiedni - błąd
Jak skończyli się znaki w napisie to, jeżeli stos jest pusty to wyświetlasz poziom, jeżeli nie - błąd.

Np coś w stylu:

#include <iostream>
#include <cstring>
using namespace std;
 
int main()
  {
   const char pr[]="(){}[]";
   char bufor[1000],stack=bufor,*ptr;
   unsigned level=0;
 
   cout<<"Wyrażenie z nawiasami: ";
   while((ptr=strchr(pr,cin.get()))!=0)
     {
      unsigned pos=ptr-pr;
      if(pos&1)
        {
         if(stack--<bufor)
           {
            cout<<"Nadmiar zamkniętych nawiasów"<<endl;
            break;
           }
         if(*stack!=*ptr)
           {
            cout<<"Zamknięty nieodpowiedni nawias"<<endl;
            break;
           }
         ++level;
        }
      else *(stack++)=*(ptr+1);
     }
   if(ptr)
     {
      if(stack!=bufor) cout<<level<<endl;
      else cout<<"Nie domknięte nawiasy"<<endl;
     }
   return 0;
  }
0

Właśnie zmienna n od początku miała wynosić 1, gdy pojawia się na drodze nawias otwierający - rośnie tylko zmienna j. Zmienna n miała pomagać w wyznaczaniu różnicy między nawiasem zamykającym, a otwierającym. Jak pewnie zauważyłeś, zmienna n rośnie, gdy liczba zamykających się po sobie nawiasów się zwiększa. Na "papierze" miało to sens i cóż, działało. Rozpatrywałem ręcznie różne przypadki, algorytm każdy z nich rozwiązywał bez problemu. Tylko po przeniesieniu do C++ pewnie gdzieś jest błąd, jednakże zastanawiam się, gdzie.

0

Użyj debuggera to sprawdzisz co się dzieje.

1 użytkowników online, w tym zalogowanych: 0, gości: 1