Implementando Pilha com Vetores de Forma Flexivel

Andryas · 29 de junho de 2010

Gostaria de fazer uma pilha em C que aceitasse tanto vetores de char,int e ponto flutuante. Para isso, encontrei um exemplo que utiliza unions, mas estou com dificuldade em entender.

Segue o codigo:


#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
#define INTGR     1
#define FLT       2
#define STRING    3

struct stackelement
{
    int etype;
    union
    {
        int ival;
        float fval;
        char cval;
    }element;
};

struct stack
{
    int top;
    struct stackelement items[STACKSIZE];
};

Segundo a explicação, etype poderá assumir valores correspondentes a INTGR,FLT,STRING. Entretanto, não sei como faço para implementar as funçoes push e pop pra pilhas.

Teria que mandar o usuario escolher o tipo do vetor,mas ai como eu leria os valores e passaria pra push?

Tentei isso:


#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
#define INTGR     1
#define FLT       2
#define STRING    3

struct stackelement
{
    int etype;
    union
    {
        int ival;
        float fval;
        char cval;
    }element;
};

struct stack
{
    int top;
    struct stackelement items[STACKSIZE];
};

menu()
{
    printf("\nMenu Tipo de Pilha: ");
    printf("\n1-Inteiros");
    printf("\n2-Ponto Flutuante");
    printf("\n3-String");

    printf("\nMenu de Acoes:"); 
    printf("\n1-Inserir novo elemento na Pilha");
    printf("\n2-Remover elemento da Pilha");
    printf("\n3-Imprimir a Pilha");
    printf("\nEntre com o Tipo de Pilha e em seguida a acao desejada: "); 
}

push(struct stack *ptr,tipo_pilha,valor)
{
    if(ptr->top == STACKSIZE-1)
        printf("Pilha Cheia");

    else
    {
        switch(tipo_pilha)
        {
            case 1: ptr->items[++(ptr->top] = valor;
        }
    }


}

int main()
{
    int opcao;
    struct stack s;
    struct stackelement s2;
    s.top = -1;
    menu();

    scanf("%d",&s2.etype);
    scanf("%d",&opcao);
    switch(opcao)
    {
        case 1: 
                if(s2.etype == INTGR)
                {
                    printf("\nDigite o numero a ser inserido: ");
                    scanf("%d",&s2.element.ival); 

                }
                else if(s2.etype == FLT)
                {
                    printf("Digite o numero de ponto flutuante a ser inserido: ");
                    scanf("%f",&s2.element.fval);
                }
                else
                {
                    printf("Entre com o char a ser inserido: ");
                    scanf("%c",&s2.element.cval);
                }
                push(&s)   

        case 2: 
                pop();break;
        case 3: 
                print_stack();
    }
    menu();
}

dontpanic · 30 de junho de 2010

Na verdade, o etype alí só pode ser int mesmo...

Acho que a ideia do etype naquela struct é só pra indicar mesmo o tipo de valor que o elemento da pilha vai usar. Ex: 1 - int, 2 - float, 3 - char...

Você terá que implementar as funções da pilha (push, pop, etc) levando esse valor em consideração. Você verifica o etype, se for um INT, você faz o pop pra um int, se for um float, faz pra um float, etc...

Ou seja, suas funções de pilha terão que ser 3 em 1...

O union é exatamente como uma struct, só que você só pode usar um elemento do union por vez (eles compartilham o mesmo espaço na memória, então naquele exemplo que você usou alí, se você tentar dar valor pro ival e depois pro fval, você perde o valor do ival)... então considerando isso seria uma boa ideia evitar uma pilha com elementos com tipos diferentes.

Andryas · 30 de junho de 2010

Na verdade, o etype alí só pode ser int mesmo...
Acho que a ideia do etype naquela struct é só pra indicar mesmo o tipo de valor que o elemento da pilha vai usar. Ex: 1 - int, 2 - float, 3 - char...

Você terá que implementar as funções da pilha (push, pop, etc) levando esse valor em consideração. Você verifica o etype, se for um INT, você faz o pop pra um int, se for um float, faz pra um float, etc...

Ou seja, suas funções de pilha terão que ser 3 em 1...

O union é exatamente como uma struct, só que você só pode usar um elemento do union por vez (eles compartilham o mesmo espaço na memória, então naquele exemplo que você usou alí, se você tentar dar valor pro ival e depois pro fval, você perde o valor do ival)... então considerando isso seria uma boa ideia evitar uma pilha com elementos com tipos diferentes.

Tentei fazer da seguinte maneira:


#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
#define INTGR     1
#define FLT       2
#define STRING    3

struct stackelement
{
    int etype;
    union
    {
        int ival;
        float fval;
        char cval;
    }element;
};

struct stack
{
    int top;
    struct stackelement items[STACKSIZE];
};

void menu()
{
    printf("\nMenu Tipo de Pilha: ");
    printf("\n1-Inteiros");
    printf("\n2-Ponto Flutuante");
    printf("\n3-String");

    printf("\nMenu de Acoes:");
    printf("\n1-Inserir novo elemento na Pilha");
    printf("\n2-Remover elemento da Pilha");
    printf("\n3-Imprimir a Pilha");
    printf("\nEntre com o Tipo de Pilha e em seguida a acao desejada: ");
}

void push(stack *ptr,stackelement *ptr2)
{
    if(ptr->top == STACKSIZE-1)
        printf("Pilha Cheia");

    else
    {
        if(ptr2->etype == 1)
          ptr->items[++(ptr->top)] = ptr2->element;// *****
        else if(ptr2->etype == 2)
          ptr->items[++(ptr->top)] = ptr2->element;
        else ptr->items[++(ptr->top)] = ptr2->element;//****
    }


}

int main()
{
    int opcao;
    struct stack s;
    struct stackelement s2;
    s.top = -1;
    menu();

    scanf("%d",&s2.etype);
    scanf("%d",&opcao);
    switch(opcao)
    {
        case 1:
                if(s2.etype == INTGR)
                {
                    printf("\nDigite o numero a ser inserido: ");
                    scanf("%d",&s2.element.ival);

                }
                else if(s2.etype == FLT)
                {
                    printf("Digite o numero de ponto flutuante a ser inserido: ");
                    scanf("%f",&s2.element.fval);

                }
                else
                {
                    printf("Entre com o char a ser inserido: ");
                    scanf("%c",&s2.element.cval);

                }
                push(&s,&s2);


    }
    return (0);
}

Ta dando erro Onde marquei ***** O compilador diz que nao há sentido na atribuição com '='

Como faço para usar o ponteiro nessa situação,quando temos uma union dentro de uma estrutura e meu ponteiro aponta para esta estrutura?

No mais, a logica tem erros?

dontpanic · 30 de junho de 2010

O erro é porque você tá tentando atribuir objetos diferentes.

ptr->items[] = ptr2->element;

ptr->items[] é um objeto do tipo "struct stackelement"

e ptr2->element é um objeto do tipo "union"

Talvez o que você quisesse fazer seria:

ptr->items[] = *ptr2;

A lógica estaria correta, você estaria atribuindo um elemento do tipo "struct stackelement" pra elemento do array items, que é um array de "struct stackelement".

Mas aí você teria erro de sintaxe.

O melhor seria fazer a copia dos valores:

Se for um int:

ptr->items[].etype = 1;

ptr->items[].element.ival = ptr2->element.ival;

Se for um float:

ptr->items[].etype = 2;

ptr->items[].element.fval = ptr2->element.fval;

etc...

Como eu sugeri antes, teria que testar o etype do "ptr2" e fazer na mesma função os 3 casos.

Andryas · 3 de julho de 2010

Valeu pela ajuda, panic.

Fiz uma nova versao,mas o problema que na hora que eu desempilho eu preciso saber com que tipo valores estou trabalhando. Meu programa rodou certinho,mas na hora de desempilhar floats(opcao 2), ele ta truncando informacao nos decimos. Sabe porque?


#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
#define INTGR     1
#define FLT       2
#define STRING    3

struct stackelement
{
    int etype;
    union
    {
        int ival;
        float fval;
        char cval;
    }element;
};

struct stack
{
    int top;
    struct stackelement items[STACKSIZE];
};

void menu()
{
    printf("\nMenu Tipo de Pilha: ");
    printf("\n1-Inteiros");
    printf("\n2-Ponto Flutuante");
    printf("\n3-String");

    printf("\n\nMenu de Acoes:");
    printf("\n1-Inserir novo elemento na Pilha");
    printf("\n2-Remover elemento da Pilha");
    printf("\n3-Imprimir a Pilha");
    printf("\nEntre com o Tipo de Pilha e em seguida a acao desejada: ");
}

int empty(stack *pilha)
{
    return(pilha->top == -1);

}

void push(stack *ptr,stackelement *ptr2)
{
    if(ptr->top == STACKSIZE-1)
        printf("Pilha Cheia");

    else
    {
        if(ptr2->etype == 1)
          ptr->items[++(ptr->top)].element.ival = ptr2->element.ival;

        else if(ptr2->etype == 2)
          ptr->items[++(ptr->top)].element.fval = ptr2->element.fval;

        else
          ptr->items[++(ptr->top)].element.cval = ptr2->element.cval;

    }


}

int pop(struct stack *pilha,stackelement *ptr)
{
    int num;
    float val;
    char ch;

    if(empty(pilha)){
      printf("Pilha Vazia");
      exit(1);
    }
    else if(ptr->etype == 1)
    {
       num = pilha->items[pilha->top--].element.ival;
       return(num);
    }

    else if(ptr->etype == 2)
    {
        val = pilha->items[pilha->top--].element.fval;
        return(val);
    }

    else
    {
        ch = pilha->items[pilha->top--].element.cval;
        return (ch);
    }


}



int main()
{
    int opcao;
    struct stack s;
    struct stackelement s2;
    s.top = -1;
    char check = 'y';

    do{
    menu();
    scanf("%d",&s2.etype);
    scanf("%d",&opcao);
    switch(opcao)
    {
        case 1:
                if(s2.etype == INTGR)
                {
                    printf("\nDigite o numero a ser inserido: ");
                    scanf("%d",&s2.element.ival);

                }
                else if(s2.etype == FLT)
                {
                    printf("Digite o numero de ponto flutuante a ser inserido: ");
                    scanf("%f",&s2.element.fval);

                }
                else
                {
                    printf("Entre com o char a ser inserido: ");
                    fflush(stdin);
                    scanf("%c",&s2.element.cval);

                }
                push(&s,&s2);
                break;

        case 2:
                if(s2.etype == 1)
                   printf("O valor inteiro removido foi :%d ", pop(&s,&s2));
                else if(s2.etype == 2)
                   printf("O valor pto flutuante removido foi: %f ", pop(&s,&s2));

                else printf("O valor do caractere removido foi :%c ", pop(&s,&s2));
                break;


    }
    printf("Deseja continuar(y/n): ");
    fflush(stdin);
    scanf("%c", &check);
    }while(check =='y');

    return (0);
}

ScreenBlack · 3 de julho de 2010

Você estava fazendo algumas confusões no momento de remover os elementos da pilha. Além de corrigir isso, fiz a função retornar um ponteiro pra void, assim você conseguirá recuperar corretamente o valor retornado, já que poderá retornar mais de um tipo.

No mais, seu código esta correto.

Segue o código corrigido por mim, para comparação:


#include <stdio.h>
#include <stdlib.h>
#define STACKSIZE 100
#define INTGR     1
#define FLT       2
#define STRING    3

// Mudei aqui
typedef struct
{

    int etype;

    union
    {

        int ival;
        float fval;
        char cval;

    } element;

} stackelement;

// Mudei aqui
typedef struct
{

    int top;
    stackelement items[STACKSIZE];

} stack;

// Mudei aqui
void menuPilha(void)
{

    fflush(stdout);
    printf("\nMenu Tipo de Pilha:\n");
    printf("1-Inteiros\n");
    printf("2-Ponto Flutuante\n");
    printf("3-String\n");

}

// Mudei aqui
void menuOpcao(void)
{

    fflush(stdout);
    printf("\n\nMenu de Acoes:\n");
    printf("1-Inserir novo elemento na Pilha\n");
    printf("2-Remover elemento da Pilha\n");
    printf("3-Imprimir a Pilha\n");

}

int empty( stack *pilha )
{
    if ( pilha->top > 0 )
        return 0;

    return 1;

}


void push( stack *ptr, stackelement *ptr2 )
{

    if ( ptr->top == STACKSIZE - 1 )
    {
        fflush(stdout);
        printf("Pilha Cheia");
    }
    else
    {

        if ( ptr2->etype == 1 )
        {
          ptr->items[ptr->top].element.ival = ptr2->element.ival; // empilha inteiro
        }
        else
        {

            if ( ptr2->etype == 2 )
                ptr->items[ptr->top].element.fval = ptr2->element.fval; // empilha float
            else
                ptr->items[ptr->top].element.cval = ptr2->element.cval; // empilha char
        }

        ptr->items[ptr->top++].etype = ptr2->etype; // Antes nao era setado o tipo de dado dentro da pilha

    }

}

// Mudei aqui - Agora retornará um ponteiro de void
void * pop( stack *pilha, int tipo )
{

    if ( empty(pilha) )
    {
        fflush(stdout);
        printf("Pilha Vazia");
        exit(1);
    }
    else
    {

        if ( tipo == 1 )
        {
            return (void *) &pilha->items[--pilha->top].element.ival; // Mudei aqui
        }
        else
        {

            if ( tipo == 2 )
            {
                return (void *) &pilha->items[--pilha->top].element.fval; // Mudei aqui
            }
            else
            {
                return (void *) &pilha->items[--pilha->top].element.cval; // Mudei aqui
            }

        }

    }

}


int main(void)
{

    int opcao;
    stack s;
    stackelement s2;
    char check = 'y';

    s.top = 0; // Inicializa pilha

    do
    {

        menuOpcao();
        fflush(stdin);
        scanf("%d",&opcao);

        if ( opcao == 1 )
        {
            menuPilha();
            fflush(stdin);
            scanf("%d",&s2.etype);
        }

        switch ( opcao )
        {

            case 1:
                    if( s2.etype == INTGR )
                    {

                        fflush(stdout);
                        printf("\nDigite o numero a ser inserido: ");
                        fflush(stdin);
                        scanf("%d",&s2.element.ival);

                    }
                    else
                    {
                        if( s2.etype == FLT )
                        {

                            fflush(stdout);
                            printf("Digite o numero de ponto flutuante a ser inserido: ");
                            fflush(stdin);
                            scanf("%f",&s2.element.fval);

                        }
                        else
                        {

                            fflush(stdout);
                            printf("Entre com o char a ser inserido: ");
                            fflush(stdin);
                            scanf("%c",&s2.element.cval);

                        }
                    }
                    push(&s,&s2);
                    break;

            case 2:
                    if ( s.items[s.top-1].etype == INTGR )
                    {
                        fflush(stdout);
                        printf("O valor inteiro removido foi : %d\n", *( (int *) pop( &s, 1 ) ) ); // Mudei aqui
                    }
                    else
                    {
                        if ( s.items[s.top-1].etype == 2 )
                        {
                            fflush(stdout);
                            printf("O valor pto flutuante removido foi: %f\n", *( (float *) pop( &s, 2 ) ) ); // Mudei aqui
                        }
                        else
                        {
                            printf("O valor do caractere removido foi : %c\n", *( (char *) pop( &s, 3 ) ) ); // Mudei aqui
                        }
                    }
                    break;


        }

        fflush(stdout);
        printf("Deseja continuar(y/n): ");
        fflush(stdin);
        scanf("%c", &check);

    }
    while ( check == 'y' );

    return (0);
}

Andryas · 3 de julho de 2010

Mt bom screen,valeu.

Fiquei na duvida do por quê do operador & aqui:

return (void *) &pilha->items[--pilha->top].element.ival;

E no meu codigo, ele tava desempilhando certinho,mas só na hora de desempilhar o float dava erro. Nao entendi o motivo.

você resolver usar ponteiro pra void- mt interessante- valeu o aprendizado

ScreenBlack · 3 de julho de 2010

o & é para retornar um ponteiro para o conteudo de "pilha->items[--pilha->top].element.ival", e com isso, faço um typecast (void *) para a função poder retornar um valor de qualquer tipo.

Sobre a parte de desempilhar, você estava decrementando "pilha->top" depois que recuperasse o valor, mas isso não pode, já que o valot de pilha->top referencia para uma posição no vetor onde não foi usado.

Por exemplo, temos pilha->top valendo 2, então estamos usando a posição 0 e 1 do vetor, assim, para alcançarmos o segundo valor, devemos diminuir o pilha->top em 1.

fazer:


pilha->items[--pilha->top].element.ival;

é o mesmo que:


pilha->items[pilha->top-1].element.ival;
pilha->top--;

Exemplo de atribuições (--valor1) e (valor2--):


int valor1 = 50;
int valor2 = 50;

printf("valor1: %d\n", valor1--); // vai mostrar o valor 50
printf("valor2: %d\n", --valor2); // vai mostrar o valor 49

Andryas · 3 de julho de 2010

Sobre a parte de desempilhar, você estava decrementando "pilha->top" depois que recuperasse o valor, mas isso não pode, já que o valot de pilha->top referencia para uma posição no vetor onde não foi usado.

Por exemplo, temos pilha->top valendo 2, então estamos usando a posição 0 e 1 do vetor, assim, para alcançarmos o segundo valor, devemos diminuir o pilha->top em 1.

Screen, se você olhar meu código verá que eu implementei o inicio da pilha diferentemente de você. Fiz

s.top = -1;

e na função de push, eu incremento 1º e depois empilho; já na função pop, eu desempilho e só depois decremento top. Tá certo, nao ta?

Tenta executar o meu codigo, e testa com todos os tipos(int,float,char), todos,com exceção do float,desempilham corretamente. Sabe me dizer porque dá erro(truncamento nas casas depois da virgula)?

Abraços

ScreenBlack · 4 de julho de 2010

Se for aplicar dessa maneira no código que postei, a validação dos dados começaria na posição -1 da pilha (ex: s[-1]), e essa posição não existe.

Eu costumo programar sempre utilizando a variavel inicializada já com a posição inicial, e depois incrementa-la, se for programar usando a sua maneira, o incremento terá de vir antes.

O que muda no final é apenas a forma como vai interpretar para fazer a leitura, pois não vai mudar em nada no desempenho do sistema.

Se você usar o depurador, e ver a execução linha-a-linha, entenderá melhor o porquê.