Sprawdzanie poprawności nawiasów - zadanie

Question

Witam, mam pytanie. Mianowicie napisałem kod do sprawdzania poprawności nawiasów, jednak nie przechodzi mi on przez wszystkie testy. Wiecie może jakiego przypadku mogłem nie uwzględnić?

#include <iostream>
#include <stack>

using namespace std;

stack<char> abc;

int main()
{
    int n;cin >> n;string a;bool ok;
    for(int i=0;i<n;++i){
        cin >> a;
        ok = true;
        for(int j=0;j<a.size();++j){
            switch(a[j]){
            case '(':case '[': case '{':
                abc.push(a[j]);
                break;
            case ')':
                if(abc.empty() || abc.top() != '(') ok=false;
                else abc.pop();
                break;
            case ']':
                if(abc.empty() || abc.top() != '[') ok=false;
                else abc.pop();
                break;
            case '}':
                if(abc.empty() || abc.top() != '{') ok=false;
                else abc.pop();
                break;
            }
            //if(!ok) break;
        }
        if(!ok) cout << "NIE" << '\n';
        else cout << "TAK" << '\n';
    }
    return 0;
}

 

Answer 1

Musisz pisać czytelniej i nie nazywaj stosu abc, nie pisz 5 instrukcji w 1 linii, bo nie da się potem tego debugować.

Wydaje mi się 3 rzeczy:

1 - nie czyścisz stosu abc jak znajdziejsz zły wynik.

2 - Breakujesz, nawet gdy znajdziejsz dobry nawias, a powinieneś tylko gdy znajdziejsz zły.

3 - Bez sensu pisać if(!ok) - NIE, else - TAK, lepiej napisać if(ok) - TAK, else NIE

Wydaje mi się, że o to chodzi. Popraw kod, będzie łatwiej degugować.

Comments

Te rzeczy są przydatne jednak nie wydaje mi się, że są one przyczyną złego wyjścia

---

Ale nie czyści stosu, i przy obiegu kolejnej pętli j korzysta z poprzedniego obiegu i dlatego mu się psuje. Wydaje mi się, że to jest przydatne. Wystarczy, że napisze abc.clear()

---

Rzeczywiście, dzięki za pomoc

---

Pamiętaj, żeby pisać bardziej rzetelnie, lepiej nazywać zmienne i struktury danych, bo tak to się pogubisz przy programie z większą linią kodu, lub nawet w małym i jest też kompletnie nie czytelny dla innych, oraz nie da się debugować czegoś takiego.

---

Zmieniłem trochę kod, jednak dalej nie wchodzi.

#include <iostream>

using namespace std;

char stos[300];
int rozmiar=0;

void dodaj(int x){
    stos[rozmiar] = x;
    ++rozmiar;
}
void zdejmij(){
    --rozmiar;
}
bool valid(string a){
    for(int i=0;i<a.size();++i){
        switch(a[i]){
    case '(':case '[':case '{':
        dodaj(a[i]);
        break;
    case ')':
        if(!rozmiar || a[rozmiar-1] != '(') return false;
        zdejmij();
        break;
    case ']':
        if(!rozmiar || a[rozmiar-1] != '[') return false;
        zdejmij();
        break;
    case '}':
        if(!rozmiar || a[rozmiar-1] != '{') return false;
        zdejmij();
        break;
        }
    }
    if(rozmiar > 0) return false;
    return true;
}

int main()
{
    int n;string a;bool b;
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> a;
        b = valid(a);
        if(b) cout << "TAK" << '\n';
        else cout << "NIE" << '\n';
        rozmiar = 0;
    }
    return 0;
}

 

---

gdy zmienna rozmiar = 0, a ty sprawdzasz stos[rozmiar-1] i odwolujesz sie poza pamiec, bo stos[-1]. Musisz przifować, czy rozmiar == 0.

W sensie linie 22, 26, 30 masz 2 przypadki. Gdy rozmiar = 0, lub rozmiar > 0. Musisz pierwszy warunek. Wyciagnac w if-a wyzej:

if (rozmiar == 0) -> return false;

if (a[rozmiar-1] != '(') -> return false

bo gdy masz to w jednej lini, to on wykona obydwa, i ci sie wywali signal.

Np wejsice ), lub ()), lub ()}

Btw. Poparz jaki masz w zadaniu limit dlugosci ciagu, bo twoj stos ma maksymalnie 300 znaków, a zazwyczaj długość wejście jest większa od 300, popatrz na limity.

---

Moim zdaniem ten stos sam w sobie był spoko, chodziło mi tylko o jego nazwę. zmienna bool ok, też była git.

---

Poprawiłem kod jeszcze bardziej, i wszystko działa.

Z tego co wiem gdy mamy dwa przypadki to jeśli pierwszy jest poprawny to drugi przypadek nie jest sprawdzany, więc nie wyjdzie niżej niż 0. Przesyłam kod ostateczny. Zaznaczyłem na zielono co poprawiłem. Wystarczyło zmienić a[rozmiar-1] na stos[rozmiar-1]. Chciałem też podziękować Ci pasjonacie_algorytmiki za włączenie się do dyskusji i pomoc.

#include <iostream>

using namespace std;

char stos[300];
int rozmiar=0;

void dodaj(int x){
    stos[rozmiar] = x;
    ++rozmiar;
}
void zdejmij(){
    --rozmiar;
}
bool valid(string a){
    for(int i=0;i<a.size();++i){
        switch(a[i]){
    case '(':case '[':case '{':
        dodaj(a[i]);
        break;
    case ')':
        if(!rozmiar || stos[rozmiar-1] != '(') return false;
        zdejmij();
        break;
    case ']':
        if(!rozmiar || stos[rozmiar-1] != '[') return false;
        zdejmij();
        break;
    case '}':
        if(!rozmiar || stos[rozmiar-1] != '{') return false;
        zdejmij();
        break;
        }
    }
    if(rozmiar > 0) return false;
    return true;
}

int main()
{
    int n;string a;bool b;
    cin >> n;
    for(int i=0;i<n;++i){
        cin >> a;
        b = valid(a);
        if(b) cout << "TAK" << '\n';
        else cout << "NIE" << '\n';
        rozmiar = 0;
    }
    return 0;
}

 

---

A to skoro w takiej kolejności sprawdza to spoko.

Przyjemność po mojej stronie :)