C Simular uma expressão usando Pilhas

[Lipeco]

Bom dia gostaria de algumas dicas sobre como fazer um exercício sobre pilhas.

 

Exercício pede para que eu escreva uma expressão e logo após mostrar o resultado.

Exemplo: Digito a expressão: (5-2)*(9+1)

                Imprime Resultado: 30.

 

Regras do exercício:

Iniciar com pilha vazia; Realizar uma varredura na expressão para cada caractere caso seja um operador (Enquanto a pilha não estiver vazia e houver no seu topo um símbolo com prioridade maior ou igual ao encontrado, desempilhe o operador e copie-o na saída). Empilhe o operador encontrado.

Se for "(", empilhe.

Se for um operando, copie para saída.

Se for ")" desempilhar e copiar na saída, até que seja desempilhado o parêntese de abertura correspondente.

Ao final, esvaziar a pilha e mover simbolos desempilhados para a saída.

 

Prioridades:

"(" prioridade 1;

"-" ou "+" prioridade 2;

"/" ou "*" prioridade 3;

 No final o resultado da expressão estará ao topo da pilha.

[Ansi C]

Olá, tudo bem? Espero que esteja bem!

Sendo um exercício, o melhor é responder somente com os auxílios existentes no livro|apostila|apontamento|páginas eletrônicas ou aplicativo com conteúdo que antecede o exercício e esse enunciado está confuso (pelo menos para mim).

Veja

9 horas atrás, Lipeco disse:

desempilhar e copiar na saída

O que é saída nesse contexto? Desempilhar e copiar, separadamente, parecem duas funções e a última expressão (copiar na saída) faz-me pensar em escrever no terminal ou qualquer outro destino de saída, daí o motivo da confusão porque o resultado (outputs) é como sugeriu baixo:

9 horas atrás, Lipeco disse:

Exemplo: Digito a expressão: (5-2)*(9+1)

                Imprime Resultado: 30.

Existem duas linhas para entrada e saída.

Logo

9 horas atrás, Lipeco disse:

gostaria de algumas dicas sobre como fazer um exercício sobre pilhas

Construa sua TDA Pilha conforme o apontamento|livro do exercício que em tese tem as dicas-instruções para conseguir uma interpretação|compreensão desse enunciado.

[Lipeco]

@mauro_b Mandei incompleto. Estou lendo sobre infixa Para Posfixa tentando entender para aplicar no exercicio em anexo.

[Lipeco]

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


int main(){
   char exp[50];

    No *pPos = NULL;
    No *pTemp = NULL;

    printf("\tDigite um expressao: ");
    scanf("%49[^\n]", exp);            //Digita no máximo 49 caractere sendo que um é para identificar o final da string até que p usuário aperte Enter
    verificaExpressao(exp);
    expressaoInfixa(&pPos, &pTemp); //Passa posFixa como null e i temporário também
    printf( "\tEXPRESSAO POSFIXA: " );
    imprimePosfixo( pPos );
    printf("\n\n");
}
  
pilha.c 
  
#include <stdio.h>
#include <stdlib.h>
#include "pilha.h"

typedef struct no{
    char expressao;  //A expressão é caractere
    float valor;
    struct no *proximo;
}No;

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

    if(novo){                        //Verifica se a alocação está correta
        novo->expressao = valor;    //Valor é empilhado
        novo->proximo = pilha;      //Coloca no Topo da Pilha
        return novo;
    }
    else
        printf("\tERRO AO ALOCAR memória!\n");
    return NULL;
}

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

    if(*pilha){                     //Se o conteúdo apontado por esse ponteiro for diferente de Nulo
        remover = *pilha;           //Recebe o topo da pilha
        *pilha = remover->proximo;  //Remove do topo da pilha
    }
    else
        printf("\tPILHAVAZIA\n");
    return remover;
}


void imprimir(No *pilha){         //USADO PARA OBSERVAR SE O PARENTESE FOI EMPILHADO
    while(pilha){
        printf("\tCONTEM NA PILHA: %c\n\n", pilha->expressao);
        pilha = pilha->proximo;
    }
}

int verificaParentese(char fechaP, char desempilhado){   //Verifica se o parentese foi colocado corretamente
    switch(fechaP){
    case ')':
        if(desempilhado == '(')          //Caso o parentese  fechado for igual a sua abertura - Expressão correta
            return 1;                   //Expressao correta
        else
            return 0;                  //Expressao incorreta

    }
}

int verificaExpressao(char expressao[]){    //Empilha se for parentese, ou desempilha o mesmo

    int i = 0;
    No *remover, *pilha = NULL;

    while(expressao[i] != '\0'){             //Enquanto for diferente do fim da pilha
        if(expressao[i] == '(' ){            //Empilha "("
            pilha = empilhar(pilha, expressao[i]);
           imprimir(pilha); //TESTAR PARA VER SE OS CARACTERES SÂO GUARDADOS NA PILHA
        }
        else if(expressao[i] == ')'){
            remover = desempilhar(&pilha);
            if(verificaParentese(expressao[i], remover->expressao) == 0){
                printf("\tEXPRESSAO ESCRITA INCORRETAMENTE!\n");
                return 1; //Retorna 1 para quando estiver errada
            }
            free(remover);
        }
        i++;
    }

    imprimir(pilha); //TESTAR PARA VER SE OS CARACTERES foram REMOVIDOS dA PILHA

    if(pilha){
        printf("\tExpressao Incorreta!!!\n");
        return 1;   // QUando estiver expressao incorreta
    }
    else{
        printf("\tEXPRESSAO ESCRITA CORRETAMENTE !!!\n");

        // DAQUI TEM QUE IR PARA CONVERTER ESSA EXPRESSAO

        return 0;
    }
}

//TESTES DE CONVERSAO

void imprimePosfixo(No *posFixo)    //Imprime conversão da expressão INFIXO para POSFIXO
{
    if(posFixo)
    {
        imprimePosfixo(posFixo->proximo);
        printf("%c", posFixo -> expressao);
    }
}

void temporarioPos( No **pPos, No **pTemp, No *aux )
{
    aux = (*pTemp)->proximo;
    (*pTemp)->proximo = *pPos;
    *pPos = *pTemp;
    *pTemp = aux;
}

void alocaCharNaPilha(No **pilha, No *aux, char expressao)
{
    aux = ( No *) malloc( sizeof( No ) );
    aux -> expressao = expressao;
    aux -> proximo = *pilha;
    *pilha = aux;
}


void expressaoInfixa(No **pPos, No **pTemp )
{

    char expressao;
    No *aux;

    printf("\n\tTESTANDO DIGITE EXPRESSAO NOVAMENTE: "); //AQUI GOSTARIA DE CHAMAR O VALOR QUE FOI DIGITADO NO INICIO, AO invés DE EU TER QUE DIGITAR NOVAMENTE, JÁ TENTEI DE TUDO E DÁ ERRO.
    gets(&expressao);  //TENHO QUE ESCREVER A EXPRESSÃO NOVAMENTE

    while( expressao != '\n' )
    {
        switch( expressao )
        {
            case '+':
            case '-':

                while((*pTemp) && ((*pTemp) -> expressao != '(' ))
                {
                    temporarioPos(&(*pPos), &(*pTemp), aux);
                }
                alocaCharNaPilha(&( *pTemp ), aux, expressao);
                break;
            case '*':
            case '/':
                while((*pTemp) && ((*pTemp) -> expressao != '+' && (*pTemp) -> expressao != '-'
                        && (*pTemp) -> expressao != '(' ))
                {
                    temporarioPos(&(*pPos), &(*pTemp), aux);
                }

                alocaCharNaPilha(&(*pTemp), aux, expressao);

                break;

            case ')':
                while((*pTemp) && ((*pTemp) -> expressao != '(' ))
                {
                    temporarioPos(&(*pPos), &(*pTemp), aux);
                }

                if( (*pTemp) && (*pTemp) -> expressao == '(')
                {
                    aux = *pTemp;
                    *pTemp = (*pTemp) -> proximo;
                    free(aux);
                }
                break;
            case '(':
                alocaCharNaPilha(&( *pTemp), aux, expressao);

                break;

            default:
                alocaCharNaPilha(&(*pPos), aux, expressao);
                break;
        }
        scanf("%c", &expressao);
    }

    while(*pTemp )
    {
        temporarioPos(&(*pPos), &(*pTemp), aux);
    }

}
  
  pilha.h
  
 typedef struct no No;

No* empilhar(No* pilha, char valor);
No* desempilhar(No**pilha);
void imprimir(No* pilha);
int verificaParentese(char fecha, char desempilhado);//Verifica se o parentese foi colocado corretamente
int verificaExpressao(char exp[]); //Empilha se for parentese, ou desempilha o mesmo
void imprimePosfixo( No *posFixo );
void temporarioPos( No **pPos, No **pTemp, No *aux );
void alocaCharNaPilha( No **pilha, No *aux, char op );
void expressaoInfixa( No **pPos, No **pTemp);

 

Eu estou com dificuldade de na hora da conversao, pegar a expressão digitada inicialmente automaticamente.

 

Eu faço o seguinte , primeiro digito a expressão =  a*(b+c)*(d-g)*h, utilizo ela como exemplo, digito a Infixa, aí o programa me diz se está escrito corretamente , abrindo e fechando os parenteses..

Mas o problema começa quando eu vou converter, não consigo pegar essa expressão, eu tenho que digita-la de novo a*(b+c)*(d-g)*h, aí quando eu digito ela converte certinho para abc+*dg-*h*, utilizo essa expressão como teste.

 

Deixei anotado no código, se alguém puder dar uma ajuda, agradeço.