Nesta aula vamos ver uma aplicação da estrutura de dados pilha aqui no nosso Curso de Programação C. Vamos ver como verificar se uma expressão matemática está mal formada com o auxilio de uma estrutura PILHA.

Normalmente uma expressão matemática pode ser composta por caracteres como parênteses ( () ), colchetes ( [] ) e chaves ( {} ). Estes caracteres ajudam a determinar a ordem em que as operações podem ser realizadas. Para cada caracter de abertura é necessário um de fechamento formando o par.

A ideia aqui é elaborar um pequeno programa em C que, dada uma expressão digitada no teclado, ele seja capaz de dizer se a expressão está bem formada ou não.

No início pode parecer complicado, mas não é, desde claro que você tenha entendido como trabalhar com a estrutura pilha. A ideia básica aqui é, percorrer a expressão procurando pelos caracteres mencionados acima. Ao encontrar qualquer um dos três, vamos avaliar se é de abertura ou de fechamento. Se for de abertura, então ele será inserido na pilha. Se for de fechamento, então iremos remover o elemento do topo da pilha, que precisa obrigatoriamente fazer par com o elemento de fechamento, caso contrário a expressão está mal formada. Observe a expressão a seguir:

3 * [(5 – 2) / 5]

Será empilhado um [ e, sem seguida um (. Ao encontrarmos o ), será desempilhado o topo da pilha, formando o par (), e ao encontrar o ], será desempilhado novamente o topo da pilha, formando o par []. Como ao terminar a expressão a pilha estará vazia, então podemos afirmar que a expressão está bem formada.

Este processo descrito acima é realizado pela função a seguir:

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

    // percorre a string (expressão digitada) até o fim
    while(x[i] != '\0'){
        // se for um caracter de abertura, empilha
        if(x[i] == '[' || x[i] == '(' || x[i] == '{'){
            pilha = empilhar(pilha, x[i]);
            imprimir(pilha);
        }
        // se for um caracter de fechamento, desempilha e verifica se formam par
        else if(x[i] == ']' || x[i] == ')' || x[i] == '}'){
            remover = desempilhar(&pilha);
            // se não formar um par, então a expressão está mal formada
            if(forma_par(x[i], remover->caracter) == 0){
                printf("\tEXPRESSAO MAL FORMADA!\n");
                return 1; // expressao está mal formada
            }
            free(remover);
        }
        i++;
    }
    imprimir(pilha);
    // ao final, se a pilha não estiver vazia significa que a expressão está mal formada
    if(pilha){
        printf("\tExpressao mal formada!\n");
        return 1;
    }
    else{
        printf("\tEXPRESSAO BEM FORMADA!\n");
        return 0;
    }
}

* Esta função tem um problema. Teste ela com esta expressão 3 * (5 – 2) / 5] e tende descobrir qual o problema. Nas aulas seguintes trarei a solução.

A função a seguir, utilizada na função anterior, recebe dois caracteres e verifica se formam um par ou não.

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

Código completo em C para verificar se uma expressão está bem formada ou não com uma estrutura de dados pilha

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

            Código escrito por Wagner Gaspar
            Julho de 2021
*/

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