Na aula de hoje trago a resposta ao desafio deixado na aula 231 e explico porque nosso algoritmo para descobrir se uma expressão está mal formada ou não irá falhar ao avaliar uma expressão como esta: 3 * (5 – 2) / 5].

O que acontece aqui é um erro lógico, ou seja, um problema em tempo de execução. Este tipo de erro é difícil de ser solucionado e a melhor maneira de descobrir a causa é avaliar linha a linha com um exemplo que causa o erro.

Para isso vamos usar o exemplo que já sabemos que irá falhar, a expressão: 3 * (5 – 2) / 5]

Ao avaliar a expressão seguindo as instruções da nossa função identifica_formacao, estamos procurando por parênteses, chaves e colchetes, então nada será feito para o 3 e para a multiplicação. Ao encontrar o caracter (, ele será empilhado, pois é um caracter de abertura. Nada será feito para os caracteres 5 – 2. Quando encontramos o caracter ), ele é de fechamento, então iremos desempilhar o topo da nossa pilha e verificar se formam um par. Neste caso formam.

Perceba que neste momento a pilha está vazia novamente.

Seguindo a expressão, nada é feito para os caracteres / 5. Quando encontramos o caracter ], ele é de fechamento, então desempilhamos o topo da pilha para verificar se formam um par. Contudo, há alguém na pilha?

Perceba que a pilha está vazia. Assim, ao tentarmos obter o caracter desempilhado em remover->caracter teremos um erro, pois o ponteiro remover é nulo. Para resolver isso basta acrescentarmos mais um teste verificando se o ponteiro remover é diferente de nulo. Se for diferente de nulo, então verificamos se formam um par. Caso contrário, já sabemos que a expressão está mal formada pois há um fechamento sem abertura.

        else if(x[i] == ']' || x[i] == ')' || x[i] == '}'){
            remover = desempilhar(&pilha);

            if(remover){ // se o ponteiro remover for diferente de nulo, verificamos se formam um par

                if(forma_par(x[i], remover->caracter) == 0){
                    printf("\tEXPRESSAO MAL FORMADA!\n");
                    return 1; // expressao está mal formada
                }
                free(remover);
            }

            else{ //  senão, já sabemos que a expressão está mal formada
                printf("\tEXPRESSAO MAL FORMADA!\n");
                return 1; // expressao está mal formada
            }

        }

Código completo em C para verificar se uma expressão está mal formada ou não

/*

            Código escrito por Wagner Gaspar
            Julho de 2021

            Aula 231: Como descobrir se uma expressão matemática está mal formada?

            3 * [(5 - 2) / 5]
            3 * (5 - 2) / 5] <-- ao testar com esta expressão o programa trava. Descobriu o motivo?
*/


typedef struct no{
    char caracter;
    struct no *proximo;
}No;

No* empilhar(No *pilha, char valor){
    No *novo = malloc(sizeof(No));

    if(novo){
        novo->caracter = valor;
        novo->proximo = pilha;
        return novo;
    }
    else
        printf("\tErro ao alocar memoria!\n");
    return NULL;
}

No* desempilhar(No **pilha){
    No *remover = NULL;

    if(*pilha){
        remover = *pilha;
        *pilha = remover->proximo;
    }
    else
        printf("\tPilha vazia\n");
    return remover;
}

void imprimir(No *pilha){
    printf("\n\tPILHA\n");
    while(pilha){
        printf("\t%c\n", pilha->caracter);
        pilha = pilha->proximo;
    }
    printf("\tFIM PILHA\n\n");
}

int forma_par(char f, char d){
    switch(f){
    case ')':
        if(d == '(')
            return 1; // bem formada
        else
            return 0; // mal formada
        break;
    case ']':
        if(d == '[')
            return 1; // bem formada
        else
            return 0; // mal formada
        break;
    case '}':
        if(d == '{')
            return 1; // bem formada
        else
            return 0; // mal formada
        break;
    }
}

int identifica_formacao(char x[]){
    int i = 0;
    No *remover, *pilha = NULL;

    while(x[i] != '\0'){
        if(x[i] == '[' || x[i] == '(' || x[i] == '{'){
            pilha = empilhar(pilha, x[i]);
            imprimir(pilha);
        }
        else if(x[i] == ']' || x[i] == ')' || x[i] == '}'){
            remover = desempilhar(&pilha);
            if(remover){
                if(forma_par(x[i], remover->caracter) == 0){
                    printf("\tEXPRESSAO MAL FORMADA!\n");
                    return 1; // expressao está mal formada
                }
                free(remover);
            }
            else{
                printf("\tEXPRESSAO MAL FORMADA!\n");
                return 1; // expressao está mal formada
            }
        }
        i++;
    }
    imprimir(pilha);
    if(pilha){
        printf("\tExpressao mal formada!\n");
        return 1;
    }
    else{
        printf("\tEXPRESSAO BEM FORMADA!\n");
        return 0;
    }
}

int main(){
    char exp[50];

    printf("\tDigite um expressao: ");
    scanf("%49[^\n]", exp);
    printf("\nExpressao: %s\nRetorno: %d\n", exp, identifica_formacao(exp));
}