Check if an expression is well formed

Question

I was trying to make a program that checks if an expression is well formed.

Something like {[()()]} is well formed while something like {{())({] is not.

I implemented a bilbioteca "cell. c" from which I take some functions from the program I leave below.

Basically if the read character is "open" it is stacked on the stack. When reading a "lock" character it checks if it is the character that corresponds to the opening character on the top of the stack; if it is, it pops the read character and continues reading. Otherwise the expression is bad form. Could someone tell me what’s wrong there?

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pilha.h"

int bemFormada(char v[]) {
    apontaPilha p = criaPilha(strlen(v) * sizeof(char));
    int i = 0;
    char c;

    for (i = 0; i < strlen(v); i++)
        if (v[i] != '{' || v[i] != '}' || v[i] != '[' || v[i] != ']' || v[i] != '(' || v[i] != ')')
            v[i] = 0;

    for (i = 0; i < strlen(v); i++)
        printf("%d", v[i]);

    while (i < strlen(v) && v[i] != 0) {
        c = v[i];
        if (c == '{' || c == '[' || c == '(') {
            empilha(p, c);
        }
        else {
            if(pilhaVazia(p))
                return 0;
            else if ((c == '}' && eleTopo(p) == '{') || (c == ']' && eleTopo(p) == '[') || (c == ')' && eleTopo(p) == '('))
                c = desempilha(p);
        }
        i++;
    }
    if (!pilhaVazia(0)) {
        destroiPilha(p);
        return 1;
    }
    return 0;
}

int main() {
    char v[100], c;
    int i;

    printf("Informe a sequencia: ");

    for (i = 0; i < 100; i++){
        c = scanf("%s", v);
    }

    if (bemFormada(v))
        printf("\nBem formada!\n");
    else
        printf("\nMal formada!\n");

    return 0;
}

--- Pile. c ---

    #include <stdio.h>
    #include <stdlib.h>
    #include "pilha.h"

    #define tipoDaPilha int
    typedef struct pilha Pilha;

    typedef Pilha * apontaPilha;

   apontaPilha criaPilha(int tamanho);

    struct pilha {
        char *v; /*mudar dependendo do tipo de dado usado*/
        int topo;
        int tamanho;
    };

apontaPilha criaPilha(int tamanho) {
    apontaPilha p = malloc(sizeof(Pilha));
    p->v = malloc(tamanho * sizeof(Pilha));
    p->topo = 0;
    p->tamanho = tamanho;

    return p;
}

tipoDaPilha pilhaCheia(Pilha *p) {
    if (p->topo > p->tamanho)
        return 1;
    return 0;
}

tipoDaPilha pilhaVazia(Pilha *p) {
    return (p->topo == 0);
}

void empilha(Pilha *p, char elemento) {
    if (!pilhaCheia(p)) {
        p->v[p->topo] = elemento;
        p->topo++;
    }
    else
        printf("Pilha cheia!\n");
}

char desempilha(Pilha *p) {
    if (!pilhaVazia(p)) {
        p->topo--;
        return p->v[p->topo];
    }
    else
        return '\0';
}

tipoDaPilha topo(Pilha *p) {
    return p->topo;
}

char eleTopo(Pilha *p) {
    return p->v[p->topo - 1];
}

void destroiPilha(Pilha *p) {
    free(p->v);
    free(p);
}

Answer 1

The first thing that caught my attention was this:

    for (int i = 0; i < strlen(v); i++)
        if (v[i] != '{' || v[i] != '}' || v[i] != '[' || v[i] != ']' || v[i] != '(' || v[i] != ')')
            v[i] = 0;

This is damaging the input string, truncating it by placing a null terminator in the middle of it. I do not recommend doing this. It does not seem to make sense. Perhaps it would be better to ignore the symbols that are not in the group ()[]{} instead of trying to erase them.

Let’s see this part:

    else {
        if(pilhaVazia(p))
            return 0;
        else if ((c == '}' && eleTopo(p) == '{') || (c == ']' && eleTopo(p) == '[') || (c == ')' && eleTopo(p) == '('))
            c = desempilha(p);
    }
    i++;

To better understand, let’s rewrite it like this:

    else {
        if (pilhaVazia(p)) return 0;
        char t = eleTopo(p);
        else if ((c == '}' && t == '{') || (c == ']' && t == '[') || (c == ')' && t == '(')) {
            c = desempilha(p);
        }
    }
    i++;

Well, here you pop if you have found the close symbol corresponding to the one you opened. But, what if you have closed something that has not been opened? In this case, you do nothing, and this is one of the things that is wrong. Also, you assign the pop-up symbol to the variable c, but the value assigned to it will never be used, because in the next iteration of while the c = v[i]; will overwrite this value.

In fact, what you should do is find yourself a )]}, pop at all times the top of the stack (containing the opening) and check if the closure matches the opening.

The if (pilhaVazia(0)) is also suspect. It wasn’t meant to be a p in place of 0?

And then there’s this:

criaPilha(strlen(v) * sizeof(char))

That one sizeof(char) There’s no point in being there. The parameter is the amount of elements to be considered in the stack, the size of each element does not matter as its stack implementation already handles it.

I don’t think that’s cool either:

typedef Pilha * apontaPilha;

This won’t hurt your program, but I don’t think it will help either. This kind of thing masks your types and is confusing. I suggest using only Pilha * directly.

This is weird too:

#define tipoDaPilha int

This also doesn’t help your code at all. Especially considering that the return of functions pilhaCheia and pilhaVazia is of this type, and the ideal would be to use boolean type. Changing the return types of these functions to int or to bool, this defines almost loses the purpose of existing. It is only in the function topo, you should actually call yourself tamanhoPilha and her return has nothing to do with the pile guy, it’s actually an integer and so it should be int.

Actually, the pile guy was supposed to be char, and not int. Because in it, you’re stacking characters. So, the type should be in the places where there are char, that is to say, empilha, desempilha, eleTopo and in the field v of struct.

Based on this, this allocation is wrong:

malloc(tamanho * sizeof(Pilha));

The right thing would be sizeof(char). Or else sizeof(tipoDaPilha). You are allocating enough memory to store a number of elements, so you should multiply the number of elements by the size of each element.

In the most, his pilha.c seems right to me.

Your main it’s not right either:

for (i = 0; i < 100; i++){
    c = scanf("%s", v);
}

You should either read 100 characters and put them in a string or read a string with up to 100 characters. This for does neither one thing nor the other, he is reading 100 different strings without caring about the size and putting them all in the same place on top of each other. What you wanted was this:

scanf("%99s", v);

This 99 is the maximum string size, not counting the null terminator. The null terminator must fit within the 100 positions you reserved for the vector, so its limit is 99 characters plus the null terminator.

I restructured your code. In it I am ensuring that the original string is never changed, I use a variable tamanho to avoid using strlen more than once and I guarantee that the characters that are not ()[]{} are skipped and use a for in place of while. It is also important to call the destroiPilha(p) before all the returns. It remained so:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "pilha.h"

int bemFormada(char v[]) {
    int tamanho = strlen(v);
    Pilha *p = criaPilha(tamanho);

    for (int i = 0; i < tamanho; i++) {
        char c = v[i];
        if (c == '{' || c == '[' || c == '(') {
            empilha(p, c);
        } else if (c == '}' || c == ']' || c == ')') {
            if (pilhaVazia(p)) {
                destroiPilha(p);
                return 0;
            }
            char t = desempilha(p);
            if ((c == '}' && t != '{') || (c == ']' && t != '[') || (c == ')' && t != '(')) {
                destroiPilha(p);
                return 0;
            }
        }
    }
    int vazio = pilhaVazia(p);
    destroiPilha(p);
    return vazio;
}

int main() {
    char v[100];

    printf("Informe a sequencia: ");
    scanf("%99s", v);

    if (bemFormada(v)) {
        printf("\nBem formada!\n");
    } else {
        printf("\nMal formada!\n");
    }

    return 0;
}

Note that in the above code, the functions topo and eleTopo no longer need to be used.

Your pilha.c:

#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"

#define tipoDaPilha char

typedef struct pilha {
    tipoDaPilha *v; /*mudar dependendo do tipo de dado usado*/
    int topo;
    int tamanho;
} Pilha;

Pilha *criaPilha(int tamanho) {
    apontaPilha p = malloc(sizeof(Pilha));
    p->v = malloc(tamanho * sizeof(tipoDaPilha ));
    p->topo = 0;
    p->tamanho = tamanho;

    return p;
}

int pilhaCheia(Pilha *p) {
    return p->topo > p->tamanho;
}

int pilhaVazia(Pilha *p) {
    return p->topo == 0;
}

void empilha(Pilha *p, tipoDaPilha elemento) {
    if (!pilhaCheia(p)) {
        p->v[p->topo] = elemento;
        p->topo++;
    } else {
        printf("Pilha cheia!\n");
    }
}

tipoDaPilha desempilha(Pilha *p) {
    if (!pilhaVazia(p)) {
        p->topo--;
        return p->v[p->topo];
    } else {
        return '\0';
    }
}

int tamanho(Pilha *p) {
    return p->topo;
}

tipoDaPilha elementoTopo(Pilha *p) {
    return p->v[p->topo - 1];
}

void destroiPilha(Pilha *p) {
    free(p->v);
    free(p);
}

Ah, finally I always recommend to use the keys {} in the bonds for, while and in elses and ifs with several lines. I explain the reason for this in the middle of this other answer in the section "Keys after if, else, while and for". Although this answer is about Java specifically, much of it (but not everything) also applies to C.