• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Sprawdzanie poprawności nawiasów - zadanie

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
0 głosów
51 wizyt
pytanie zadane 19 stycznia w C i C++ przez Dani Użytkownik (650 p.)
edycja 19 stycznia przez Dani

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

 

1 odpowiedź

0 głosów
odpowiedź 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
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ć.
komentarz 19 stycznia przez Dani Użytkownik (650 p.)
Te rzeczy są przydatne jednak nie wydaje mi się, że są one przyczyną złego wyjścia
1
komentarz 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
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()
komentarz 19 stycznia przez Dani Użytkownik (650 p.)
Rzeczywiście, dzięki za pomoc
komentarz 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
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.
komentarz 19 stycznia przez Dani Użytkownik (650 p.)

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

 

komentarz 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
edycja 19 stycznia przez pasjonat_algorytmiki
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.
komentarz 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
Moim zdaniem ten stos sam w sobie był spoko, chodziło mi tylko o jego nazwę. zmienna bool ok, też była git.
komentarz 19 stycznia przez Dani Użytkownik (650 p.)

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

 

komentarz 19 stycznia przez pasjonat_algorytmiki Gaduła (4,190 p.)
edycja 19 stycznia przez pasjonat_algorytmiki
A to skoro w takiej kolejności sprawdza to spoko.

Przyjemność po mojej stronie :)

Podobne pytania

0 głosów
2 odpowiedzi 4,662 wizyt
pytanie zadane 28 kwietnia 2016 w C i C++ przez drive879 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 253 wizyt
pytanie zadane 1 maja 2015 w C i C++ przez Waszek Gaduła (4,130 p.)
+1 głos
1 odpowiedź 127 wizyt
pytanie zadane 29 kwietnia 2015 w C i C++ przez pulson666 Stary wyjadacz (12,560 p.)

90,298 zapytań

138,894 odpowiedzi

311,080 komentarzy

60,012 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...