Infixa, Posfixa E Préfixa

[Guest carlos dunga]

Galera alguém ai tem algum exemplo ou coisa do tipo para mi ajuda ... é para mim estudar tou ferrado e preciso saber isso o mais rapido possivell... :blink: :blink:

na teoria eu já sei eu não sei a implementação...

tipo

eu queria um programa que ao receber uma expressão na forma infixa como exemplo:

INFIXA-> (2 + 5) * 6

INFIXA-> 2 + 9

INFIXA-> (8 - 1) * (4 + 2)

converta para POSFIXA que nesses exemplo ficaria assim:

POSFIXA-> 2 5 + 6 *

POSFIXA-> 2 9 +

POSFIXA-> 8 1 - 4 2 +*

então galera... tipo eu sei a teoria mais não sei como implementar isso... sei que o melhor é usar pilha para isso...

no caso 2 pilhas uma que guarda os operandos e outra com o numerandos...

mais se alguém tiver algo pronto ou apenas as rotinas de conversao e poder postar nossa ia ser uma boa pra mim estudar...

vlw galera!!!!!! ;)

[Graymalkin]

Ok, se você sabe a teoria, o que está faltando na prática, para você implementar isso? O que você não conseguiu fazer?

Abraços,

Graymalkin

[Guest Visitante]

então... é que eu não consigo implementar... nem tenho ideia de como por em uma pilha... minha mente trava quando chega nisso...

entendi... não tenho saida...

então queria uma ajuda não é? pra quem saiba eu consiga destravar minha mente...

não consigo montar a pilha correta para isso!!!!

abraços

carlos dunga

[Graymalkin]

Montar rotinas para a pilha não é difícil, se bem que em C++ você já tem uma classe para isso (chamada stack). Portanto, seria só uma questão de pegar elemento por elemento da expressão e jogar nas pilhas. Todos as expressões entre parênteses devem ser executadas primeiro, certo? Então, você iria percorrer os caracteres da expressão de forma a determinar qual é o par de parênteses mais interno, de modo que ele seria o primeiro a ser executado. De posse disso, você pegaria os valores e os operadores e os colocaria na pilha. O mesmo seria feito com as operações mais externas. Essa é a lógica do problema, que você já parece saber.

Abraços,

Graymalkin

[Guest carlos dunga]

olha só eu fiz mais não está dando certo...

qual será o erro?

OBS: é em C e não C++

#include<stdio.h>
#include<conio.h>

typedef struct pilha{
        char dado;
        struct pilha *prox;
        } *pil;


int inicializa(pil *p){
    (*p) = NULL;
}

int vazia(pil *p){
    return ((*p) == NULL);
}

int aloca(pil *p, char d){
    pil que = (pil) malloc(sizeof(struct pilha));
    if (que == NULL){
       return 0;
    } else {
      que->dado = d;
      que->prox = (*p);
      (*p) = que;
      return 1;
    }
}

int remover(pil *p, char *d){
    pil que;
    //pil que = (*p);
    if (vazia(p))
       return 0;
    if ((*p)->prox == NULL){
       (*d) = (*p)->dado;
       (*p) = NULL;
    } else {
           (*d) = (*p)->dado;
           que = (*p);
           (*p) = (*p)->prox;
           free(que);
    }
    return 1;
}

/*void menu(char *op) {
     system("CLS"); //clrscr() no borland C
     printf("1 - Inserir\n");
     printf("2 - Remover\n");
     printf("3 - Sair\n");
     printf("Opcao ====> ");
     (*op) = getch();     
}*/

int main () {
    char exp[50];
    char ver;
    int x, y;
    pil prim;
    inicializa(&prim);    
    printf("digite uma expressao :");
    scanf("%s",&exp);
    x = strlen(exp);
    for (y = 0; y <= x; y++){
          ver = exp[y];
          if ((ver != '*') && (ver != '+')){
             printf(&ver);
          } else {
            switch (ver) {
                 case '*' :
                      aloca(&prim,ver);
                 break;
                 case '+' :
                      aloca(&prim,ver);
                 break;
                 case '}' :
                      if (remover(&prim,&ver)){
                         printf (&ver);
                      } else {
                        printf("\n\n\nfalta parenteses na expressao digitada...");
                      }
                 break;
                 default:
                         getch();
                 break; 
            }
          }
    }    
    getch();
    return 0;
}   

abraços

[Ø£¡vë¡®'§®]

Carlos Dunga,

eu dei uma ajeitada e ele parou de imprimir tudo aquelas coisas mais funcionou só que ao invés de mostrar os operadores ele mostra apenas ")" no pos fixa

galera agora até eu incanei hauhauhaua o que será que esta errado...tentei tentei e nem consegui

olha o codigo ai como fiko

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

typedef struct pilha{
        char dado;
        struct pilha *prox;
        } *pil;


int inicializa(pil *p){
    (*p) = NULL;
}

int vazia(pil *p){
    return ((*p) == NULL);
}

int aloca(pil *p, char *d){
    pil que = (pil) malloc(sizeof(struct pilha));
    if (que == NULL){
       return 0;
    } else {
      que->dado = (*d);
      que->prox = (*p);
      (*p) = que;
      return 1;
    }
}

int remover(pil *p, char *d){
    pil que = (*p);
    if (vazia(p))
       return 0;
    if ((*p)->prox == NULL){
       (*d) = (*p)->dado;
       (*p) = NULL;
    } else {
           (*d) = (*p)->dado;
           que = (*p);
           (*p) = (*p)->prox;
           free(que);
    }
    return 1;
}

int main () {
    char exp[50];
    char ver,most;
    int x, y;
    pil prim;
    inicializa(&prim);    
    printf("digite uma expressao :");
    scanf("%s",&exp);
    x = strlen(exp);
    for (y = 0; y <= x; y++){
          ver = exp[y];
          if ((ver != '*') && (ver != '+') && (ver != ' ') && (ver != '(')){
             printf("%c ",ver);
          } else {
            switch (ver) {
                 case '*' :
                      aloca(&prim,&ver);
                 break;
                 case '+' :
                      aloca(&prim,&ver);
                 break;
                 case '}' :
                      remover(&prim,&most);
                      printf ("%c ",most);
                 break;
                 default:

                 break; 
            }
          }
    }    
    getch();
    return 0;
}  

abraços

[Guest --Eu mesmo --]

Galera Tenta esse...

num deu tempo de testar... até acho que ainda tem porblemas.. mas tah mais perto

#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#include <string.h>

typedef struct pilha{
        char dado;
        struct pilha *prox;
        } *pil;


void inicializa(pil *p){
    (*p) = NULL;
}

int vazia(pil *p){
    return ((*p) == NULL);
}

int aloca(pil *p, char *d){
    pil que = (pil) malloc(sizeof(struct pilha));
    if (que == NULL){
       return 0;
    }
    que->dado = (*d);
    que->prox = (*p);
    (*p) = que;
    return 1;
}

int remover(pil *p, char *d){
    pil que = (*p);
    if (vazia(p))
       return 0;
    if ((*p)->prox == NULL){
       (*d) = (*p)->dado;
       (*p) = NULL;
    } else {
           (*d) = (*p)->dado;
           que = (*p);
           (*p) = (*p)->prox;
           que -> prox = NULL;
           free(que);
    }
    return 1;
}

int main () {
    char exp[50];
    char ver,most;
    int x, y;
    pil prim;
    inicializa(&prim);
    printf("digite uma expressao :");
    scanf("%s",&exp);
    x = strlen(exp);
    for (y = 0; y <= x; y++){
          ver = exp[y];
          if ((ver != '*') && (ver != '+')&& (ver != '(') && (ver != ')')){
                  printf("%c ",ver);
          } else {
            switch (ver) {
                 case '*' :
                      aloca(&prim,&ver);
                 break;
                 case '+' :
                         remover(&prim,&most);
                          if (most == '*')
                                     printf ("%c ",most);
                      else{
                          aloca(&prim,&most);
                      }
                          aloca(&prim,&ver);

                 break;
                 case ')' :
                           do{
                          remover(&prim,&most);
                          printf ("%c ",most);
                      }
                      while(prim!=NULL);
                      break;
                 default:
                         break;
            }

          }
    }
    do{
          remover(&prim,&most);
          printf ("%c ",most);
    }
    while(prim!=NULL);
    getch();
    return 0;
}

Editado Outubro 12, 2008 por kuroi
Adicionar tag CODE

[Guest Visitante]

Cara eu to com um problema com esse programa também!

com expressões pequenas ele "funciona" mas com maiores ele brocha!

AQUI É A BIBLIOTECA DE PILHAS QUE EU FIZ!

/****************************************************************
Prototipos e definicoes das operacoes sobre Pilhas
*****************************************************************/

//Define o tamanho da pilha e estrutura
#define MAXPILHA 999
struct stack    {
     int topo;
     char item[MAXPILHA];
};

//Prototipos das funcoes sobre PILHAS

//Inicializa a pilha
void IniciaPilha(struct stack *ps);
//Verifica se a pilha esta' vazia
int iPilhaVazia(struct stack *ps);
//Verifica se a pilha esta' cheia
int iPilhaCheia(struct stack *ps);
//Adiciona um item na pilha
char iPush(struct stack *ps, char iVal);
//Remove um item da pilha e retorna-o
char iPop(struct stack *ps);
//Retorna o ultimo item da pilha
int iElemTopo(struct stack *ps);


/***********************************************************
Definicao das funcoes sobre pilhas
************************************************************/

/*
Nome da função:
    IniciaPilha
Descrição:
    Inicializa a pilha
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
Retorno:
    Nenhum
*/
void IniciaPilha(struct stack *ps)
{
    ps->topo = -1;
}

/*
Nome da função:
    iPilhaVazia
Descrição:
    Verifica se a pilha está vazia
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
Retorno:
    1 - Se a pilha estiver vazia
    0 - Se a pilha NÃO estiver vazia
*/

int iPilhaVazia(struct stack *ps)
{
    if (ps->topo == -1)
        return(1); //Verdadeiro - Pilha Vazia
    else
        return(0); // Falso - Pilha NÃO Vazia
}

/*
Nome da função:
    iPilhaCheia
Descrição:
    Verifica se a pilha está cheia
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
Retorno:
    1 - Se a pilha estiver Cheia
    0 - Se a pilha NÃO estiver Cheia
*/
int iPilhaCheia(struct stack *ps)
{
    if (ps->topo == MAXPILHA -1)
        return(1); //Verdadeiro - A pilha está Cheia
    else
        return(0); //Falso - A pilha NÃO está Cheia
}

/*
Nome da função:
    iPush
Descrição:
    Adiciona um item na pilha
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
    iVal    - Valor que deverá ser inserido na pilha
Retorno:
    Valor do elemento foi inserido na pilha
*/

char iPush(struct stack *ps, char Val)
{
    if (iPilhaCheia(ps) == 1)
    {
        printf("Ocorreu overflow na pilha!\n"); //Pilha CHEIA
        //exit(1); //Saindo fora da função (forçando a saida)
    }
    else
    {
        return(ps->item[++(ps->topo)]=Val);
    }
}

/*
Nome da função:
    iPop
Descrição:
    Remove um item da pilha e retorna-o
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
Retorno:
    Elemento que foi retirando da pilha
*/
char iPop(struct stack *ps)
{
   /* if (iPilhaVazia(ps) == 1)
    {
        printf("Ocorreu underflow na pilha!\n"); //Pilha está VAZIA
        //exit(1); //Saindo fora da função (forçando a saida)
    }*/
    
    return(ps->item[(ps->topo)--]);
    
}

/*
Nome da função:
    iElemTopo
Descrição:
    Retorna o ultimo item da pilha
Argumentos:
    *ps     - Ponteiro para a estrutura (struct) da pilha
Retorno:
    Retorna o elemente que está no topo da pilha
*/

int iElemTopo(struct stack *ps)
{
    if (iPilhaVazia(ps)==1)
    {
        printf("Ocorreu underflow na pilha!\n"); //Pilha está VAZIA
        //exit(1);  //Saindo fora da função (forçando a saida)
    }
    else
    {
        return(ps->item[ps->topo]);
    }
}



E AQUI O BENDITO PROGRAMA QUE NÃO DA CERTO!


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "stackschar.h"


int main(int argc, char *argv[])
{
  struct stack p, p2,p3;
  IniciaPilha(&p);
  IniciaPilha(&p2);
  IniciaPilha(&p3);
  int tam,i=0;
  char equa[40],aux[40];

  printf("\nDigite a formula desejada ex: (a+(b*c))\n\n");
  fflush(stdin);
  fgets(equa,40,stdin);
  equa[strlen(equa)-1]= '';
  tam=strlen(equa);
  printf("%d\n", tam);
  for(i=0;i<tam;i++)
  {
       
        if(equa[i]== '+' || equa[i]== '-' || equa[i]== '*' || equa[i]== '/')
            iPush(&p, equa[i]);
        else if(equa[i] == '(')
            printf(" ");
        else
           aux[i]=equa[i];
           
   
                    
          
    }
    aux[strlen(aux)-1]= '';
    for(i=0;aux[i]!= ')';i++)
    {
      printf(" %c\n", aux[i]);}
    
     if(aux[i]== ')')
     {
            printf(" %c\n", iPop(&p));
            
      
        }
        
  

  system("PAUSE");    
  return 0;
  }

alguém PODE ME AJUDAR? ABRAÇO!

Editado Outubro 12, 2008 por kuroi
Adicionar tag CODE

[kuroi]

com expressões pequenas ele "funciona" mas com maiores ele brocha!

o q você quer dizr com isso?? a expressao sai errada ou ele trava??