Infixa para Pós-fixa em C

Publicado por Ivan Rocha 01/11/2007

[ Hits: 34.129 ]

Homepage: http://homes.dcc.ufba.br/~ivan062/bahia

Download posfInf.c




Programa que recebe como entrada uma Notação Infixa bem-formada (Ex: (A+B*C); (A*(B+C)/D-E); A+B*(C-D*(E-F)-G*H)-I*3 ) e retorna sua respectiva Notação Pós-fixa (Ex: ABC*+; ABC+*D/E-; ABCDEF-*-GH*-*+I3*-).

É feito utilizando 2 pilhas: uma auxiliar e a pilha Pós-fixa, que conterá a Expresão Pós-Fixa que será impressa no final.

  



Esconder código-fonte

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

typedef struct _Pilha
{
    char op;
    struct _Pilha *prox;
}Pilha;

void transfereTempPos( Pilha **pPos, Pilha **pTemp, Pilha *aux )
{
    aux = ( *pTemp ) -> prox;
    ( *pTemp ) -> prox = *pPos;
    *pPos = *pTemp;
    *pTemp = aux;
}

void alocaCharNaPilha( Pilha **pilha, Pilha *aux, char op )
{
    aux = ( Pilha *) malloc( sizeof( Pilha ) );
    aux -> op = op;  
    aux -> prox = *pilha;
    *pilha = aux;
}

void leOperacao( Pilha **pPos, Pilha **pTemp )
{
    char op;
    Pilha *aux;
    
    scanf( "%c", &op );
    while( op != '\n' )
    {      

        switch( op )
        {
            case '+':
            case '-':

                while( ( *pTemp ) && ( (*pTemp) -> op != '(' ) )
                {
                    transfereTempPos( &( *pPos ), &( *pTemp ), aux );
                }

                alocaCharNaPilha( &( *pTemp ), aux, op );
                
                break;

            case '*':
            case '/':

                while( ( *pTemp ) && ( (*pTemp) -> op != '+' && (*pTemp) -> op != '-'
                        && (*pTemp) -> op != '(' ) )
                {        
                    transfereTempPos( &( *pPos ), &( *pTemp ), aux );
                }

                alocaCharNaPilha( &( *pTemp ), aux, op );
                
                break;

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

                if( (*pTemp) && (*pTemp) -> op == '(' )
                {
                    aux = *pTemp;
                    *pTemp = (*pTemp) -> prox;
                    free( aux );
                }
                
                break;

            case '(':
                alocaCharNaPilha( &( *pTemp ), aux, op );
                
                break;

            default:
                alocaCharNaPilha( &( *pPos ), aux, op );
                
                break;
        }

        scanf( "%c", &op );
    }

    while( *pTemp )
    {
        alocaCharNaPilha( &( *pTemp ), aux, op );
    }
    
}

void imprime( Pilha *topo )
{
    if( topo )
    {
        imprime( topo -> prox );
        printf( "%c", topo -> op );
    }   
}

int main()
{
    Pilha *pPos = NULL;
    Pilha *pTemp = NULL;

    printf( "Operacao Infixa: " );
    leOperacao( &pPos, &pTemp );
    printf( "Operacao Posfixa: " );
    imprime( pPos );
    printf( "\n" );

    return 0;
}

Scripts recomendados

Ponteiros

Retirar ocorrências de uma substring dentro de uma string

Exemplo de Menu

Exibe quantos números perfeitos foram digitados

Comando strncat


  

Comentários
[1] Comentário enviado por ivan.cr.neto em 01/11/2007 - 02:11h

Olá, pessoal, no finalzinho da função leOperacao(), onde tem:

while( *pTemp )
{
alocaCharNaPilha( &( *pTemp ), aux, op );
}

coloquem:

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

se não vai dar loop infinito em algumas expressões. Ah, e em qualquer lugar onde tenha &( *<variavel> ) podem colocar apenas <variavel>, já que & e * se anulam.

[]'s

[2] Comentário enviado por Marciocorni em 08/11/2010 - 11:54h

Meu amigo Ivan!
Quero agradece-lo muito por ter publicado o codigo desse programa!
Tenho um trabalho para entregar na faculdade e não estava conseguindo muito progresso no implemento, e como o prazo é sempre curto comecei a pesquisar na net, e depois de MUUUITO procurar encontrei o link do fórum.
O fato que vou estudar o seu codigo para utiliza-lo em meu trabalho.
Agora tenho que fazer um programa de posfixa para infixa.
E um com avaliação de expressões posfixa.
Muito obrigado
por ter ajudado alguem e a mim por tabela.
Marcio

[3] Comentário enviado por nickarcos em 08/08/2013 - 14:34h

Muitoooo obrigado, também estou precisando desse código, vou estuda-lo e reimplementa-lo com de acordo com meu entendimento.

Viva o Unix (linux e mac hehe).

abraço

[4] Comentário enviado por nick_arcos em 08/08/2013 - 17:58h

Tenho que adicionar além os operadores +, -, /, e * o operador ˆ(exponencial), e gerar um resultado da notação pós fixa, com valores do tipo flutuante. vou criar os arquivos.c e arquivos.h (isso eu já consigo) para deixar ele estruturado.

Poderia alguém me ajudar? :\
Obrigado e gde abraço


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts