Sprawdzenie czy wyrażenie jest nawiasowe

Odpowiedz Nowy wątek
2019-05-26 20:47

Rejestracja: 1 rok temu

Ostatnio: 11 miesięcy temu

0

Mam napisać taki program , a nie mam kompletnie pomysłu na to :

Wyrażeniem nawiasowym nazwiemy niepusty ciąg składający się z nawiasów otwierających i zamykających. Powiemy, że wyrażenie jest poprawne, jeżeli każdy nawias otwierający można sparować z zamykającym, występującym po nim, tak aby ciąg nawiasów znajdujących się pomiędzy nimi również był poprawnym wyrażeniem nawiasowym. Na przykład (()())() jest poprawnym wyrażeniem nawiasowym , ale )( i ()( już nie. Innymi słowy poprawne wyrażenie nawiasowe ma tyle samo nawiasów otwierających i 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 nawiasowego (nie więcej niż 30 znaków) a następnie sprawdzi czy wczytany ciąg jest poprawnym wyrażeniem nawiasowym i wypisze odpowiedni komunikat na ekranie.

Koledzy z grupy pytali o to samo zadanie przed kilkoma miesiącami, zaspałeś? - AnyKtokolwiek 2019-05-26 22:22
Jak pytali to najwidoczniej wiesz jak zrobić :) - Kate321 2019-05-26 22:29

Pozostało 580 znaków

2019-05-26 21:38

Rejestracja: 4 lata temu

Ostatnio: 16 godzin temu

0

Jest to dość proste, po prostu musisz zakodować sprawdzanie warunku:

Innymi słowy poprawne wyrażenie nawiasowe ma tyle samo nawiasów otwierających i 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.

Czyli tworzysz sobie zmienną pomocniczą. Na początek ustawiasz jej wartość na zero. Przy każdym nawiasie otwierającym zwiększasz ją, przy zamykającym zmniejszasz. Na koniec musi być równa zero. W każdej chwili zmienna pomocnicza nie może być ujemna. Z czym dokładnie masz problem?

Kompletnie nwm jak to zapisać. Dałbyś radę jakoś to rozsądnie zapisać :) - Kate321 2019-05-26 21:42

Pozostało 580 znaków

2019-05-26 21:57

Rejestracja: 4 lata temu

Ostatnio: 16 godzin temu

0

Ok, dam wędkę nie rybę. Coś w ten deseń:

int main ()
{
  int temp = 0;
  char *napis = " ()( ";
  for (int i = 0; i < strlen(napis);i++)
  {
    if (napis[i] == '(')
      temp++;
    else if (napis[i] == ')')
      temp--;

    if (temp < 0)
    {
      // bledne nawiasowanie i mozna skonczyc przetwarzanie przed czasem
      break;
    }
  }

  if (temp)
  {
    // nawiasowanie bledne
  }
  else
  {
    // nawiasowanie poprawne
  }
  return 0;
}
edytowany 3x, ostatnio: Mr.YaHooo, 2019-05-26 21:58
Przecież to już prawie całe rozwiązanie. ;) - Silv 2019-05-26 23:12
Pani w szkole mówiła żeby nie stosować nazw "temp". No chyba że piszemy "swap()". - vpiotr 2019-05-27 11:00
@sliv tak wiem, na początku miał być pseudokod, ale jakoś tak wyszło... ;) @vpiotr tak, biję się w pierś. Jednak w przypadku takich snippetów jak ten można używać. Tak samo jak nie powinienem dawać PL nazw zmiennych. - Mr.YaHooo 2019-05-27 21:09
@Mr.YaHooo: ostateczna ocena należy do autorki, czy woli mieć tak, czy same wskazówki. ;) Ja wolałbym same wskazówki, no, chyba żebym piątą godzinę drugiego dnia nad tym ślęczał... wtedy wolałbym gotowe rozwiązanie. - Silv 2019-05-27 21:12
@Silv: też mi się wydaje, że wskazówki są lepsze. Chyba, że pytający już 3 dzień pyta o to samo ;) - Mr.YaHooo 2019-05-27 21:16

Pozostało 580 znaków

2019-05-26 22:07

Rejestracja: 3 lata temu

Ostatnio: 1 minuta temu

0

Standardowo, używa się do tego stosu (LIFO): jak widzi nawias lewy to push, a jak nie to pop. Gdy na końcu zmienna logiczna jest 1 i stos pusty, to True, jak nie to False. Stos Znajdziesz tutaj: https://github.com/lion137/C_[...]ter/FixedCapacityStackChars.c

int bal_checker(char symbol_str []) {
    StackChars * s = new_s(30);
    int bal = 1;
    int i = 0;
    char token;
    while (i < strlen(symbol_str) && bal) {
        token = symbol_str[i];
        if (token == '(') {
            push(s, token);
        }
        else {
            if (isEmpty(s))
                bal = 0;
            else
                pop(s);
        }
        i++;
    }
    if (bal && isEmpty(s))
        return 1;
    else
        return 0;
}

Raczej musimy to zrobić standardowo, takich funkcji jak twoja nie mieliśmy jeszcze wprowadzanych :( - Kate321 2019-05-26 22:13

Pozostało 580 znaków

2019-05-26 22:26

Rejestracja: 3 lata temu

Ostatnio: 1 minuta temu

0

W sumie, to w tak uproszczonym przypadku, można dać licznik zamiast stosu:

int bal_checker(char symbol_str []) {
    int cnt = 0;
    int bal = 1;
    int i = 0;
    char token;
    while (i < strlen(symbol_str) && bal) {
        token = symbol_str[i];
        if (token == '(') {
            cnt++;
        }
        else {
            if (!cnt)
                bal = 0;
            else
                cnt--;
        }
        i++;
    }
    if (bal && !cnt)
        return 1;
    else
        return 0;
}

int main() {
    char str1[] = "()()";
    printf("%d\n", bal_checker(str1));
    return 0;
}

A dla "(())" to działa? - vpiotr 2019-05-27 10:59
U mnie działa:) - lion137 2019-05-27 21:24
U mnie też zaczęło ;-) - vpiotr 2019-05-27 22:09

Pozostało 580 znaków

2019-05-27 20:03

Rejestracja: 1 rok temu

Ostatnio: 1 tydzień temu

0

Uśmiecham się za każdym razem, kiedy widzę kod liona137.

Życzę dużo uśmiechu w nadchodzącym lecie, mam nadzieję, że czas mi pozwoli udzielać się na 4p:) - lion137 2019-05-27 21:22
Nice, ale to jeszcze nie piąteczek:) - lion137 2019-05-27 22:15

Pozostało 580 znaków

2019-05-29 14:45

Rejestracja: 1 rok temu

Ostatnio: 1 tydzień temu

4
int is_balanced(char *expr)
{
    size_t left = 0;
    for ( ; *expr; ++expr) {
        if (*expr == '(') {
            ++left;
        } else if (left > 0) {
            --left;
        } else {
            return 0;
        }
    }
    return left == 0;
}

Pozostało 580 znaków

2019-05-31 18:42

Rejestracja: 1 rok temu

Ostatnio: 11 miesięcy temu

0

Udało mi się napisać , ale nwm czy do końca poprawnie

include <stdio.h>
#include <string.h>
#include <conio.h>

int main(){
int suma=0;
char ciag[31];
printf("Wprowadz ciag nawiasowy (max 30 znakow):");
while (( getchar()) != '\n');

int i;
int dlugosc;
dlugosc=strlen(ciag);
 for(i=0; i<=dlugosc; i++){
            if(ciag[i]=='('){
               suma++;}
        else {suma--;}
        if(suma<0)
            printf("Wyrazenie jest poprawne");
            else
            printf("Wyrazenie nie jest poprawne");
        }
       getch();
    }
Pokaż pozostałe 4 komentarze
@lion137: nwm czy to jakis mój błąd , ale wpisałam w twoim programie "()())" i wyszedło, że jest on poprawny - Kate321 2019-06-01 21:24
Sprawdź jeszcze raz, bo mi zwraca 0. - lion137 2019-06-01 21:31
Ale jak wpisze "()()" też zwraca 0 - Kate321 2019-06-01 21:33
Mi 1, Sprawdź, czy Masz dobrze skpiowane. - lion137 2019-06-01 21:36
Rzeczywiście miałam pomylone znaki , przepraszam za zamieszanie. A potrafisz dokończyć ten mój sposób , prowadzący tak nam kazał zrobić , a ja juz nie mam pomysłu na to , a siedzę nad tym kolejny dzień - Kate321 2019-06-01 21:41

Pozostało 580 znaków

2019-05-31 18:58

Rejestracja: 5 lat temu

Ostatnio: 1 miesiąc temu

Lokalizacja: Warszawa

0

@Kate321: sprawdź na stronie https://ideone.com/. Czy pokazane są jakieś błędy, wyjątki, np. "Compilation error" lub inne?


edytowany 1x, ostatnio: Silv, 2019-05-31 18:58

Pozostało 580 znaków

2019-05-31 19:26

Rejestracja: 3 lata temu

Ostatnio: 10 godzin temu

0

Poprawna implementacja jest na stosie ;)
//my bad, jesli w gre wchodza tylko nawiasy okragle to zliczanie jest wystarczajace*
Stosem moze byc zwykla tablica ze wskaznikiem na head

edytowany 3x, ostatnio: stivens, 2019-05-31 19:54
Pokaż pozostałe 2 komentarze
Na 100% naiwne zliczanie jest niepoprawne. Zliczanie z mnostwem ifow... nie wiem, zalezy jak duzo tych ifow. Ale zrobienie arr[buffer_size] i powiedzenie ze to stos (dostep przez inkrementacje i dekrementacje wskaznika na gore stosu) jest easy - stivens 2019-05-31 19:39
@stivens: OK, zamieszczę konkretne przykłady, to będzie łatwiej porównać. - Silv 2019-05-31 19:42
dobra zeby sprostowac to z jakiegos powodu w mojej glowie uwzglednialem wszystkie nawiasy (tj. () [] {}). I w takiej sytuacji faktycznie stos jest uzyteczny. A jak mamy tylko () to wydaje mi sie ze sprawdzenie (w trakcie) czy mozna zamknac nawias i na koncu czy jest parzyscie moze byc wystarczajace. My bad. Ale w takim razie to nudna ta wersja zadania :p - stivens 2019-05-31 19:51
@stivens: ale przykłady nadal mogę zamieścić? ;) "Nawias" w języku polskim to trochę co innego niż w angielskim ("parenthesis" vs "bracket"). I pewnie dlatego tak Ci wyszło. - Silv 2019-05-31 20:46
PS. Jednak nie będę zamieszczać przykładów, ponieważ @Kate321 napisała post i pewnie będzie chcieć, by się do niego odnosić, a nie do naszych wątpliwości. Ogólnie dzięki, podsunąłeś mi pomysł na rozbudowę mojego programu. - Silv 2019-05-31 20:48

Pozostało 580 znaków

2019-06-01 21:28

Rejestracja: 1 rok temu

Ostatnio: 11 miesięcy temu

0

Potrafi ktoś sformułować te dodatkowe warunki , bo program nadal działa źle już próbowałam modyfikować , ale nadal nic. Np. pokazuje mi, że taki ciąg "())" jest poprawny

Pozostało 580 znaków

Odpowiedz

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