Check if an expression is well formed

1

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

Something of type {[()()]} is well formed whereas something of type {{())({] is not.

I've implemented a "stack.c" library from which I take some functions of the program I left below.

Basically if the read character is "open" it is stacked on the stack. When reading a "close" character it checks if it is the character that corresponds to the opening character at the top of the stack; if it does, it pops the read character and proceeds to read. If not the expression is poorly formed. 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;
}

--- Stack.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 '
#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;
}
'; } 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); }
    
asked by anonymous 23.08.2018 / 22:35

1 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 given string as input, truncating it by placing a null terminator in the middle of it. I do not recommend doing this. Does not seem to make sense. Maybe it would be better to ignore symbols that are not in the ()[]{} group instead of trying to delete 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 understand better, let's rewrite 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 unpack if you have found the symbol that closes corresponding to what you opened. But what if you were closing something that was not open? In that case, you do nothing, and that is one of the things that is wrong. In addition, you assign the unstacked symbol to the variable c , but the value assigned to it will never be used, because at the next iteration of while c = v[i]; will overwrite this value.

In fact, what you should do is to find a )]} , unstack always the top of the stack (which contains the opening) and check that the closure matches the opening. >

The if (pilhaVazia(0)) is also suspect. It was not meant to be p instead of 0 ?

And there's also this:

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

This sizeof(char) does not make sense to be there. The parameter is the amount of elements to be considered in the stack, the size of each element does not matter because its stack implementation already handles this.

I do not think that's cool either:

typedef Pilha * apontaPilha;

This will not hurt your program, but I do not think it will help either. That sort of thing masks its types and is confusing. I suggest using only Pilha * directly.

This is also strange here:

#define tipoDaPilha int

This also does not help your code at all. Even more considering that the return of functions pilhaCheia and pilhaVazia is of this type, being that the ideal would be to use Boolean type. By changing the return types of these functions to int or bool , this defines almost that it loses its purpose to exist. It is only in the topo function, which should actually be called tamanhoPilha and the return of it has nothing to do with the type of the stack, it is actually an integer and therefore should be int .

Actually, the stack type was meant to be char , not int . For in it, you are piling characters. So, the type should be in places where there is char , that is, empilha , desempilha , eleTopo , and in the v of struct field.

Based on this, this allocation is wrong:

malloc(tamanho * sizeof(Pilha));

The right would be sizeof(char) . Or 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 fact, your pilha.c seems to me correct.

Your main is also not right:

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

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

scanf("%99s", v);

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

Restructured your code. In it I'm ensuring that the original string is never changed, I use a tamanho variable to avoid using strlen more than once and I guarantee characters that are not ()[]{} are skipped and use for instead of% with%. It is also important to call while before all destroiPilha(p) s. It looks like this:

#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 return and topo no longer need to be used.

Your eleTopo :

#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 '
    for (int i = 0; i < strlen(v); i++)
        if (v[i] != '{' || v[i] != '}' || v[i] != '[' || v[i] != ']' || v[i] != '(' || v[i] != ')')
            v[i] = 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); }

Oh, finally I recommend always using the pilha.c keys in the {} , for loops, and while s and else s loops with multiple rows. I explain the reason for this in the this other response section in the " Keys after if , if , else and while ". Although this answer is about Java specifically, much of it (but not everything) also applies to C.

    
23.08.2018 / 22:56