I'm asking help for the following program, with which I've struggled several hours this afternoon.
I'd like to create a function that receives an array of character (Which belongs to the alphabet A = {a,b,c}) and its dim and return 1 in case the character belongs to language L, or 0 if not.
The language was : a^k b^n c^m, such that k,m>=0 and n>0.
I tried very hard and i'm going to post what I've accomplished but my method seems extremely long (besides its lack of functioning)
And I'd like to know how could I think in terms of improving my code.
#include <stdio.h>
int array(char v[], int dim) {
int i, j, k, trovato = 1;
if (v[0] == 'c') trovato = 0;
if (v[0] == 'a') {
for (i = 1; i < dim; i++) {
while (trovato == 1) {
if (v[i] == 'c')
trovato = 0;
else if (v[i] == 'b') {
trovato = 1;
for (j = i + 1; j < dim; j++) {
while (trovato == 1) {
if (v[j] == 'a') trovato = 0;
if (v[j] == 'b')
trovato = 1;
else if (v[j] == 'c') {
trovato = 1;
for (k = j + 1; k < dim; k++) {
while (trovato == 1) {
if (v[k] == 'c')
trovato = 1;
else
trovato = 0;
}
}
}
}
}
}
}
}
}
if (v[0] == 'b') {
for (i = 1; i < dim; i++) {
while (trovato == 1) {
if (v[i] == 'a') trovato = 0;
if (v[i] == 'b')
trovato = 1;
else if (v[i] == 'c') {
trovato = 1;
for (j = i; j < dim; j++) {
while (trovato == 1) {
if (v[j] != 'c')
trovato = 0;
else
trovato = 1;
}
}
}
}
}
}
return trovato;
}
int main() {
char d;
int DIM, i = 0, k;
scanf("%d", &DIM);
char r[DIM];
scanf("%c", &d);
d = getchar();
while (d != '\n') {
r[i] = d;
i++;
scanf("%c", &d);
d = getchar();
}
k = array(r, DIM);
printf("%d\n", k);
return 0;
}
What i'm really not getting is why the input is going on, like if it was in a while-loop.
I think the problem is my understanding of getchar and scanf on character, so these lines for examples:
scanf("%c",&d);
d=getchar();
And how an array of vector should be initialized?
What I'm really concerned about is efficiency, I'm afraid not to improve so fast and right, that's why I'm asking even strict but constructive critics on my work that I tried to accomplish.
Let's try to make it simpler. We calculate a pointer that is one past the end of the array (v + dim) so that we don't need to use indexing and index variables, but can modify the v pointer itself.
int matches(const char *v, size_t dim) {
const char *end = v + dim;
size_t k = 0, m = 0, n = 0;
// count consecutive 'a's.
// for as long as `v` is positioned before the end
// and points to an 'a', increment `v` and increment `k`.
while (v < end && *v == 'a') {
k ++;
v ++;
}
// count consecutive 'b's
while (v < end && *v == 'b') {
m ++;
v ++;
}
// count consecutive 'c's
while (v < end && *v == 'c') {
n ++;
v ++;
}
// we didn't meet the end yet, something else was seen!
if (v < end) {
// not just aaa...bbbbb....cccc...
return 0;
}
// there were only a's, b's, c's in that order
else {
check that k, m, n matches the constraints
and return a result based on that.
}
}
So the first loop moves the pointer forward for as long as it is pointing to an 'a', the second for a 'b', and third for a 'c' - then we ensure that we actually did come to the end, and not just a case of abca for example; we're incrementing k, m and n in the loops, so by the time the else clause is hit, it is true that L = a^k b^m c^n and you just need to check k, m, n.
No nested loops are required.
As for the input,
scanf("%c",&d);
d=getchar();
you're reading characters twice. You only need getchar():
int c; // getchar returns an *int*
while ((c = getchar()) != EOF && c != '\n') {
r[i ++] = d;
}
this is all that is required to read the input until end of file or newline.