[C] Sprawdzanie poprawności sekwencji nawiasów

Dla specjalistów Programowanie
#1

Witam,

Uczę się języka od niedawna i mam problem z pewnym zdaniem

Zamieszam kod:

#include

#define LENGTH 1000000

main(){

    int i;

    int parenthesis;

    i=0;

    parenthesis=0;

printf("Podaj sekwencje nawiasow\n");

    char tab[LENGTH];

    gets(tab+1);

    while(i++){

        switch(tab[i]){

        case '(': parenthesis++; break;

        case ')': parenthesis--; break;

        }

        if(parenthesis<0) break;

    }

    if(parenthesis){

    printf("Zapis jest niepoprawny!");

    }

    else

            printf("Zapis jest poprawny");

    return 0;

}

Wszystko działa tylko nie odróżnia zapisu poprawnego od niepoprawnego. Mógłby ktoś mi pomóc i wskazać błąd?

#2

Jeżeli parenthesis jest 0 i masz zamknięcie nawiasu przerwij i powinno być git :slight_smile:

#3

Chodzi o

while(i++){

        switch(tab[i]){

        case '(': parenthesis++; break;

        case ')': parenthesis--; break;

        }

        if(parenthesis=0) break;

    }

    if

?

Jeżeli tak to bez zmian.

@ Edit

No widocznie się nie rozumiemy. Więc prosze ładnie, mógłbyś mi to jakoś wyjaśnić?

#4

Czego nie rozumiesz w tej wypowiedzi ? Chyba, że nie rozumiesz własnego kodu.

#5

Są potrzebne dwa założenia, warunki.

Pierwszy:

Pętla: licz (w ten sposób, który masz w kodzie; inkrementalna stanu nawiasów (zmienna “parenthesis”), przy otwierającym i dekrementacja przy zamykającym) dopóki nie osiągnięto (zbadano, przeliczono) wszystkich znaków (nawiasów) sekwencji. Musisz znać długość łańcucha znaków (strlen()) i sprawdzać, czy przypadkiem już się on nie skończył (liczenie dotarło do ostatniego znaku).

I drugi, który już jest,

if (parenthesis<0) break; [/code]

To przerywa pętle, jeżeli stan nawiasów spadł poniżej 0, czyli napotkało nawias zamykający, a nie było otwierającego.

Wtedy po zakończeniu faktycznie, jeżeli stan nawiasów (zmienna “parenthesis”) jest równy zero, to sekwencja jest prawidłowa, w innym przypadku nie.

Ja bym pętle while zamienił na for, wypełniając założenia pierwszego warunku.

Inne uwagi:

[code=php]if(parenthesis=0) break;

To jest przypisanie. Operatorem porównania jest ==.

    parenthesis=0;printf("Podaj sekwencje nawiasow\n");    char tab[LENGTH];[/code] 
[quote]
nawiasy.c|error: ISO C90 forbids mixed declarations and code [-pedantic]|
[/quote]
 Nie wolno tak. Najpierw deklaracje zmiennych, później reszta kodu.



[code=php]main() 



[quote]
warning: return type defaults to 'int' [-Wreturn-type]|
[/quote]
 Musi być int main(). Nie main(). Absolutnie nie void main().


Wersja po mojemu:





#include
#6

Dzięki wielkie za pomoc i wytłumaczenie.

– Dodane 17.12.2011 (So) 19:36 –

Mam problem z drugim zadaniem

#include

#include


int main(){

    int i;

    int parenthesis;

    int square_bracket;

    int length;


    parenthesis=0;

    square_bracket=0;

    char tab[256];


    printf("Podaj sekwencje nawiasow\n");

    scanf("%s", tab);

    for(i = 0, length = strlen(tab); i
        switch(tab[i]){

        case '(': parenthesis++; break;

        case ')': parenthesis--; break;

        case '[': parenthesis++; break;

        case ']': parenthesis--; break;

        }

        if(parenthesis<0 || square_bracket<0) break;


    }

    if(parenthesis)

        printf("Zapis jest niepoprawny!");

    else

        printf("Zapis jest poprawny!");


return 0;

}

Jednak dla kombinacji (][) wypisuje poprawne. Co zrobić z tym fantem? Siedze nad tym drugi dzień

#7

To na początek tak jak wcześniej. Liczysz, ile jest nawiasów, każdego typu. Jeżeli spadnie na minus od razu przerywasz, wiadomo, że jest źle.

Dodatkowo, Jeżeli ma być taka zasada jak matematyce to nawias kwadratowy nie może wystąpić, jeżeli nie zostały zamknięte te okrągłe (czyli aktualny stan jest różny od 0). Należy ten dodatkowy warunek uwzględnić w instrukcji switch. Jako, że nie da się w prosty sposób ze środka tej instrukcji przerwać pętli, należy wprowadzić dodatkową zmienna “przerwij”, której stan zostaje zmieniony na “prawda” (czyli 1), jeżeli taka sytuacja wystąpi.

#include
#8

twoje rozwiązanie nie zadziała dla wszystkich przypadków. Przykład: ([])

( //okrąłe =1

[ //case ‘[’ i okrągłe !=0 przerwij

a przecież nawiasowanie jest poprawne.

Te zadania są książkowym przykładem na użycie struktury stosu.

Jeśli trafiamy na nawias otwierający wrzucamy go na stos.

Jeśli natrafiamy na nawias zamykający, zdejmujemy ze stosu odpowiadający mu nawias otwierający. Używając stosu mamy wgląd tylko na ostatnio dodany element.

W przypadku jakiejś nie dozwolonej akcji przerywam i piszemy że nawiasowanie jest niepoprawne (próba zdjęcia nie odpowiadającego nawiasu, próba zdjęcia z pustego stosu lub po zakończeniu wczytywania danych na stosie pozostały jakieś elementy - czyli nie domknięte nawiasy).

#9

Fakt. wtedy tak by było. Ale … hm, napisałem tak celowo. Bo wg mnie ([]) jest niepoprawne :slight_smile:

W matematyce można tak zgrupować? No chyba, że pominie się tą kwestię, albo przyjmie założenie, że to nieistotne.

Czy może się mylę?

edit: w sumie, ok. Zostawmy to tak, a program trzeba napisać zgodnie z algorytmem, który opisałeś.

edit2: Tak, w ramach treningu.

#include
#10

W praktyce często spotykałem się z takim nawiasowaniem:

( [( )] )

bądź tak:

[( [] ) ]

ponieważ łatwiej znaleźć właściwą parę niż w ( ( ( ) ) ).

Natomiast czy jest to jakoś “prawnie” oznaczone jako nie dozwolone? Ja przynajmniej się nie spotkałem.