Program Benny: Mam taką wskazówkę: Warto utożsamić nawias ( z liczbą 1 oraz ) z liczbą −1. Jak mam utożsamić znak z liczbą?

jc: Do czego to jest wskazówka?

Benny: Mam napisać pewien program, który sprawdza wyrażenia nawiasowe. Wyrażeniem nawiasowym nazywamy niepusty ciąg składający się z nawiasów otwierających i zamykających. Powiemy, że wyrażenie nawiasowe jest poprawne, jeżeli każdy nawias otwierający można sparować z nawiasem zamykającym, występującym po nim, tak aby ciąg nawiasów znajdujących się pomiędzy nimi był poprawnym ciągiem nawiasowym. Na przykład (()())() jest poprawnym wyrażeniem nawiasowym, ale )( i ()( już nie są poprawne. Innymi słowy poprawne wyrażenie nawiasowe ma tyle samo nawiasów otwierających co zamykających oraz licząc od początku wyrażenia nawiasowego, liczba nawiasów otwierających jest cały czas nie mniejsza od liczby nawiasów zamykających. Napisz program, który poprosi użytkownika o wprowadzenie ciągu nawiasów, a następnie wszystkie poprawne wyrażenia nawiasowe utworzone z podanego ciągu wypisze do pliku o nazwie nawiasy.txt, tak aby wybrane wyrażenie nawiasowe było wydzielone znakiem |. Dla przykładu (()())() plik nawiasy.txt będzie wyglądał np. tak (kolejność wypisywanych wyrażeniem nawiasowym nie ma znaczenia): (|()|())() (()|()|)() (()())|()| (|()()|)() |(()())|() |(()())()| wsk1. Warto utożsamić nawias ( z liczbą 1 oraz ) z liczbą −1.

jc: Kto to pisał? Czy jesteś w stanie czytać tak okropny tekst? Ja czuję jakiś ucisk w brzuchu. O co tu chodzi? Napisz program, który poprosi użytkownika o wprowadzenie ciągu nawiasów, a następnie wszystkie poprawne wyrażenia nawiasowe utworzone z podanego ciągu wypisze do pliku o nazwie nawiasy.txt, tak aby wybrane wyrażenie nawiasowe było wydzielone znakiem |.

Benny: To pisał pewien prowadzący na AGH−u.

Benny: Coś z tym się da zrobić?

jc: Spojrzałem na przykład. Myślę, że trzeba w danym ciągu nawiasów, należy na wszelkie możliwe sposoby postawić pionowe kreski tak, aby nawiasy pomiędzy kreskami tworzyły poprawny schemat. Poradzisz sobie, zadanie nie jest trudne. Faktycznie wygodnie przetłumaczyć ciąg nawiasów na ciąg z łożony z liczb 1, −1: ( → +1 ) → −1.

jc: Nie skasowałem słowa. Spojrzałem na przykład. Myślę, że w danym ciągu nawiasów, należy na wszelkie możliwe sposoby postawić pionowe kreski tak, aby nawiasy pomiędzy kreskami tworzyły poprawny schemat. Powtórzę, pomyśl sam, na pewno sobie poradzisz

Benny: Nie rozumiem tego utożsamienia. Mam zrobić podstawienie?

jc: Chodzi o to, że dla prawidłowego rozstawienia nawiasów, na każdym etapie suma początkowych znaków jest liczbą nieujemną. Przykład ((()())()) + + + − + − − + − − 1 2 3 2 3 2 1 2 1 0

Benny: Jak mam wczytywać z konsoli te nawiasy, aby sprawdzić czy jest to ) czy (?

jc: Najpier przetestuj. Wpisz dane na stałe. char we [ ] = "((()())())"; // to mozesz latwo zmienic Jak juz program bedzie dzialal, pomyslisz, jak wczytywac. Nie musisz zamieniać nawiasów na +/−. Po prostu będziesz w programie pisał if( we[ i ] == '(' ) s ++; else if( we[ i ] == ')' ) s −−; else jakies bledne dane; Czy coś podobnego

Benny: Z tym ifem to tak chciałem zrobić tylko zastanowiło mnie to wczytywanie.

Benny: Tylko z tą tablicą jest kłopot. Muszę określić jej długość.

Benny: char tab[100]; printf("Podaj ciąg nawiasów"); scanf("%s", tab[100]); printf("%s", tab[100]); Czemu po wpisaniu czegokolwiek nie wyświetla mi tego tylko wyskakuje mi błąd?

jc: tab[100] oznacza 100 wyraz tablicy. Wpisz samo słowo tab tab oznacza adres początku tablicy.

jc: Oczywiście w deklaracji musi być 100. char tab[100];

Benny: char tab[100]; printf("Podaj ciąg nawiasów"); scanf("%s", tab); printf("%s", tab); tak jest ok tab[100] musi być, bo muszę określić rozmiar tej tablicy. Jak mam niby zdefiniować nieskończoną tablicę?

jc: Tak, w deklaracji musi być tab[100]

Benny: Dodatkowo trzeba dać warunek, aby przy s<0 wychodziło z programu.

Benny: Jak możesz to sprawdź tą część. Na razie wydaje mi się że wszystko ok wyświetla.

Benny: #include<stdio.h> #include<string.h> main() { char tab[100]; int s=0; printf("Podaj ciąg nawiasów\n"); scanf("%s", tab); for(int i=0; i<strlen(tab);i++) { if(tab[i]=='(') s++; else { if(tab[i]==')') s−−; else return 0; } if(s<0) break; } if(s==0) printf("%s", tab); else printf("Wyrażenie nawiasowe nie jest poprawne"); return 0; }

jc: Napisz tak: if(tab[i]=='(') s++; else if(tab[i]==')') s−−; else return 0; To jest to samo, ale czytelniej

Benny: Przyzwyczaiłem się dawać więcej nawiasów niż mniej, bo zawsze coś mi umykało

b.: Takie coś: char tab[100]; scanf("%s", tab); jest niebezpieczne, zob. np. http://crasseux.com/books/ctutorial/String-overflows-with-scanf.html Chodzi o to, że wczytywany napis może być dłuższy niż 100 znaków. Można też użyć switcha zamiast ifów.

Benny: b, wiem, że napis może być dłuższy niż 100 znaków, lecz nie wiem jak zadeklarować nieskończoną tablicę. Mój angielski nie jest na dobrym poziomie i nie rozumiem w większości tych publikacji.

jc: Benny, tym się nie przejmuj. Ryzyko istnieje, kiedy program ma uprawnienia administratora, a z komputera korzystają obcy użytkownicy. fgets() czyta linię, ale nie więcej niż dana liczba znaków. Potem czytasz z tablicy funkcją sscanf().

asdf: Benny, angielski jest równie istotny dla programisty jak umiejętność programowania, really W prosty sposób możesz się go uczyć − czytając / oglądając tutoriale po angielsku Nie szukaj niczego po polsku...to jest droga przez mękę, po 2) i tak nie znajdzeisz za wiele.

Benny: Ja nie jestem programistą

Dziadek Mróz: Użyj stosu

Dziadek Mróz: typedef struct Elem { char nawias; } Elem; typedef struct Stack { Elem *first; Elem *next; } Stack; void push(Stack *stack); void pop(Stack *stack); Elem *top(Stack *stack);

Benny: Nie miałem czegoś takiego.

asdf: Benny, raczej chodziło mi o to, że jak chcesz uczyć się programowania to przy okazji DOBRZE JEST znac angielski. Co do zadania − zrobiłbym to przez rekurencję.

Benny: Jak?

Programista: Ciąg nawiasów od pozycji l...r jest poprawny, jeżeli: a_l ≥ 0 a_l + a_l+1 ≥ 0 ... a_l + a_l+1 + ... + a_r−1 ≥ 0 a_l + a_l+1 + ... + a_r = 0 (tak, równa się) przy czym "a" to ciąg, w którym a_i jest równe 1 jeżeli i'ty znak to ( a −1 jeżeli ). Stąd sprawdź wszystkie możliwe pary (l, r) gdzie l < r (jest ich O(n²), n to liczba nawiasów), i jeżeli odpowiadają poprawnemu nawiasowaniu przepisz je do pliku. Pesymistyczna złożoność wynosi O(n³), jednak nie da się dostać lepszej, dla nawiasów ()()()...() mamy O(n²) poprawnych nawiasowań, więc przepisując je wszystkie do pliku dostajemy O(n³).

Dziadek Mróz: Rozkminiłem ale dopiero pod Pythonem, nie babrałem się w C, to już tam kwestia konwersji: http://ideone.com/9v8BVq

Programista: W takim razie trzymaj mój kod z zaimplementowanym algorytmem o którym pisałem (kod w C++, jeżeli potrzebujesz w C łatwo przerobisz ). Program na standardowe wejście przyjmuje ciąg nawiasów, wynik jego działania jest w pliku ,,result.txt". http://pastebin.com/GpxuhMzV

Dziadek Mróz: Przerobiona wersja @Programista: http://pastebin.com/7RdJ8d2M

Benny: Dzięki bardzo, ale jakoś bardzo skomplikowane jak dla mnie

Dziadek Mróz: a gdzie tam, pętla podwójna na napisie generujące wszystkie możliwe podciągi, funkcja sprawdzająca te podciągi i pętla zapisująca do pliku

Benny: typedef enum { false, // domyslnie = 0 true // = 1 } bool; Typ bool zwraca 0 lub 1 to wiem, ale nie rozumiem co to jest. Czy to co ja pisałem da się jakoś pociągnąć dalej?

jc: Benny, nie zawracaj sobie głowy czymś takim. W języku C wielkość różna od zera oznacza prawdę, a zero fałsz. Są jednak sytuacje, gdzie wyliczenia bardzo rozjaśniają kod.