Sprawdzenie czy wyrażenie jest nawiasowe

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.

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?

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;
}
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_datastructures/blob/master/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;
}
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;
}
0

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

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



0

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

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

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

0
int i; 
int suma = 0;
int dlugosc;
int isBalanced = 1;
dlugosc=strlen(ciag);
 for(i=0; i<=dlugosc; i++){
            if(ciag[i]=='('){
               suma++;
            }
			else {
				if (!suma)
					isBalanced = 0;
				else
					suma--;
			}
  }
        if(!suma && isBalanced)
            printf("Wyrazenie jest poprawne\n");
        else
            printf("Wyrazenie nie jest poprawne\n");

	return 0;
    }

Musisz dołożyć jeszcze zmienną logiczną isBalanced i jak znak nie jest nawiasem lewym, to, gdy suma nie jest zerowa, to ciąg nie jest poprawnie znawiasowany (isBalanced = 0), a gdy zerowa, to wtedy dekrementujemy sumę. A na końcu suma ma być zerowa i isBalanced prawdziwe.

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