Calculadora RPN - Implementação Ligada de Pilhas (Listas ligadas)

[Matilda 0]

Olá, estou com um problema para implementar as funções pop, push e empty. O código contém mais erros, pois estou adaptando o código de uma calculadora RPN com implementação de pilhas. Gostaria de ajuda com essa parte e/ou com o código por inteiro.

 

//-------------------------------------------------------------------------//

// Arquivos de cabeçalho //

//-------------------------------------------------------------------------//

#include <stdio.h>

#include <math.h>

#include <stdlib.h>

//-------------------------------------------------------------------------//

// Constantes e variáveis globais //

//-------------------------------------------------------------------------//

 

#define NUMNODE 5 //dimensão da lista

 

struct nodetype{

float info;

int next;

 

};

struct nodetype node[NUMNODE];

int avail; // endereço para início da lista livre

int s; // endereço para o top da pilha

 

 

//-------------------------------------------------------------------------//

// Função getnode //

//-------------------------------------------------------------------------//

 

//Remove o primeiro nó da lista livre e retorna um ponteiro para ele //

 

int fc_getnode(){

 

if (avail == -1) { // Teste de estouro da lista livre

printf("Estouro \n");

exit(1);

}

 

int p;

 

avail = node[avail].next; //Ponteiro para o nó

p = avail; // Atualiza lista livre

return(p); // Retorna ponteiro

 

}

 

//-------------------------------------------------------------------------//

// Função Freenode //

//-------------------------------------------------------------------------//

//Aceita um ponteiro para um nó e o retorna para a lista livre //

 

 

int fc_freenode(int p){

 

node[p].next = avail; // Faz p apontar para a lista livre

avail = p; // Faz avail apontar para 'p'

return(0);

}

 

//-------------------------------------------------------------------------//

// Função push //

//-------------------------------------------------------------------------//

//Adiciona um dado ao topo da pilha

 

int fc_push (int p){

p=fc_getnode(); // Cria novo nó

info(p)=x; // Salva o dado x no nó

next(p)=s; // Conecta ao próximo nó

s = p; // Informa novo endereço de início

}

/*int fc_push (pnt_s,x)

struct stack *pnt_s;

float x;

 

{

int wait;

 

if (pnt_s -> top == STACKSIZE-1){ //Testa overflow

printf(">> Erro: estouro de pilha.");

scanf("%d", &wait); //Aguarda leitura

exit(1); // Encerra o programa

 

}

 

else {

pnt_s -> items [++(pnt_s -> top)] = x;

}

} */

 

//-------------------------------------------------------------------------//

// Função empty //

//-------------------------------------------------------------------------//

//Verifica se a pilha está vazia

 

if (p == null){

printf(A pilha está vazia);

}

else{

printf(A pilha contém dados);

}

 

 

/*int fc_empty(pnt_s)

struct stack *pnt_s;

 

{

if (pnt_s -> top == -1)

return (1); //A pilha está vazia

else

return (0); //A pilha contém dados

 

} */

 

 

//-------------------------------------------------------------------------//

// Função pop //

//-------------------------------------------------------------------------//

//Retira um dado do topo da pilha

 

int fc_pop(pnt_s)

struct stack *pnt_s;

 

{

int wait;

if (fc_empty(pnt_s)){ //Teste de underflow

printf(">> Erro: A pilha esta vazia.");

scanf("%d", &wait); //Aguarda leitura

exit(1); //Encerra programa

 

}

 

else {

return( pnt_s -> items [(pnt_s -> top)--]); //Desempilhar

}

 

}

 

//-------------------------------------------------------------------------//

// Função principal //

//-------------------------------------------------------------------------//

int main ()

{

 

avail = 0; // Ponteiro externo para a lista-livre (primeiro elemento do vetor node)

for (i = 0; i < NUMNODE-1; i++) { // Organização dos endereços em ordem crescente

node.next = i + 1;

node[NUMNODE-1].next = -1; // Definição do final da lista livre (null)

 

 

//---------------------------------//

// Declaração das variáveis //

//---------------------------------//

 

struct stack s; //Declaração pilha "s"

 

float x,x1,x2,y; // Variaveis numéricas (X = entrada de dados, y = resultados)

char c;

 

int flag_float;

 

s.top = -1; //Inicializando pilha vazia

 

 

 

 

//---------------------------------//

// Interface com o usuário //

//---------------------------------//

 

printf("------------------\n");

printf(" CALCULADORA RPN \n");

printf("------------------\n");

printf("\n");

 

 

 

while (c != 'q'){

printf(">> ");

scanf(" %c",&c);

//---------------------------------//

// Identifica operação //

//---------------------------------//

 

 

//Testa se o operador é valido

if (c=='+' || c=='-' || c=='*' || c=='/') {

 

x1 = fc_pop(&s);

x2 = fc_pop(&s);

 

 

switch©{ //Executa a operação

case '+' : y = x2+x1; break; //Adição

case '-' : y = x2-x1; break; // Subtração

case '*' : y = x2*x1; break; //Produto

case '/' : y = x2/x1; break; // Divisão

 

}

fc_push(&s,y); //Empilha resultado

printf(">> %0.3f\n",y); //Exibe Resultado

 

 

}

 

//---------------------------------//

// Identifica o dado //

//---------------------------------//

 

else {

 

ungetc(c, stdin); //Devolve dado ao prompt

 

flag_float=scanf("%f", &x); //Lê dado e retorna estado da função "scanf"

 

if (flag_float = 1){

fc_push(&s,x);

}

else {

printf(">> Dado invalido.\n");

scanf("%c", &c); //Lê novamente o dado

}

 

}

 

}

 

printf(">> ");

scanf("%c",&c);

//-------------------------------------------------------------------------//

}

[guidjos 65]

Qual sua dúvida?

[Matilda 0]

Na verdade é tudo, mas a dúvida principal é como implementar as funções funções push, pop e empty.

[reebr 94]

Poderia por gentileza utilizar o bbcode code? Facilita a leitura do código...

int teste ()
{ 
   //...
   return 0;
}

Eu dei uma lida meio por cima, tá muito complicado de entender devido ao nome que deu as variáveis e pelo código não estar indentado...

[Matilda 0]

//-------------------------------------------------------------------------//
// Arquivos de cabeçalho                                                   //
//-------------------------------------------------------------------------//
#include 
#include 
#include 
//-------------------------------------------------------------------------//
// Constantes e variáveis globais                                          //
//-------------------------------------------------------------------------//
#define NUMNODE 5 //dimensão da lista
struct nodetype{
       float info;
       int next;
};
struct nodetype node[NUMNODE];
int avail; // endereço para início da lista livre
int s; // endereço para o top da pilha
int x;
//-------------------------------------------------------------------------//
// Função getnode                                                          //
//-------------------------------------------------------------------------//
//Remove o primeiro nó da lista livre e retorna um ponteiro para ele       //
int fc_getnode(){
         if (avail == -1) { // Teste de estouro da lista livre
            printf("Estouro \n"); 
            exit(1);
            }
         int p; 
avail = node[avail].next; //Ponteiro para o nó
p = avail; // Atualiza lista livre
return(p); // Retorna ponteiro
}
//-------------------------------------------------------------------------//
// Função Freenode                                                         //
//-------------------------------------------------------------------------//
//Aceita um ponteiro para um nó e o retorna para a lista livre             //
int fc_freenode(int p){
  node[p].next = avail; // Faz p apontar para a lista livre
  avail = p; // Faz avail apontar para 'p'
  return(0);
}
//-------------------------------------------------------------------------//
// Função push                                                             //
//-------------------------------------------------------------------------//
//Adiciona um dado ao topo da pilha
    int fc_push (int p){
        p=fc_getnode(); // Cria novo nó
        info(p)=x; // Salva o dado x no nó
        next(p)=s; // Conecta ao próximo nó
        s = p; // Informa novo endereço de início
}
    /*int fc_push (pnt_s,x)
    struct stack *pnt_s;
    float x;
{
    int wait;
    if (pnt_s -> top == STACKSIZE-1){     //Testa overflow
        printf(">> Erro: estouro de pilha.");
        scanf("%d", &wait);               //Aguarda leitura
        exit(1);                          // Encerra o programa
    }    
    else {
       pnt_s -> items [++(pnt_s -> top)] = x;
    }
} */
//-------------------------------------------------------------------------//
// Função empty                                                            //
//-------------------------------------------------------------------------//
//Verifica se a pilha está vazia
int fc_empty(int p){
    if(p == null){
        printf(A pilha está vazia);
  }
  else{
       printf(A pilha contém dados);
  }
}
/*int fc_empty(pnt_s)
     struct stack *pnt_s;
{
     if (pnt_s -> top == -1)
        return (1);  //A pilha está vazia
     else
        return (0);  //A pilha contém dados
} */
//-------------------------------------------------------------------------//
// Função pop                                                              //
//-------------------------------------------------------------------------//
//Retira um dado do topo da pilha
int fc_pop(pnt_s)
    struct stack *pnt_s;
{
    int wait;
    if (fc_empty(pnt_s)){                //Teste de underflow
       printf(">> Erro: A pilha esta vazia.");
       scanf("%d", &wait);              //Aguarda leitura
       exit(1);                         //Encerra programa
    }
    else {
         return( pnt_s -> items [(pnt_s -> top)--]); //Desempilhar
         }
}
//-------------------------------------------------------------------------//
// Função principal                                                        //
//-------------------------------------------------------------------------//
int main ()
{
 avail = 0; // Ponteiro externo para a lista-livre (primeiro elemento do vetor node)
 for (i = 0; i < NUMNODE-1; i++) { // Organização dos endereços em ordem crescente
      node[i].next = i + 1;
      node[NUMNODE-1].next = -1; // Definição do final da lista livre (null)
//---------------------------------//
// Declaração das variáveis        //
//---------------------------------//
struct stack s;        //Declaração pilha "s"
float x,x1,x2,y;  // Variaveis numéricas (X = entrada de dados, y = resultados)
char c;
int flag_float;
s=-1;          //Inicializando pilha vazia
//---------------------------------//
// Interface com o usuário         //
//---------------------------------//
printf("------------------\n");
printf(" CALCULADORA RPN \n");
printf("------------------\n");
printf("\n");
while (c != 'q'){
      printf(">> ");
      scanf(" %c",&c);      
      //---------------------------------//
      //  Identifica operação            //
      //---------------------------------//
      //Testa se o operador é valido
      if (c=='+' || c=='-' || c=='*'  || c=='/' ) {
         x1 = fc_pop(&s);
         x2 = fc_pop(&s);
         switch(c){                    //Executa a operação
         case '+' : y = x2+x1; break;  //Adição
         case '-' : y = x2-x1; break;  // Subtração
         case '*' : y = x2*x1; break;  //Produto
         case '/' : y = x2/x1; break;  // Divisão 
         case '^' : y = x1^x2; break;
         }
         fc_push(&s,y);              //Empilha resultado
         printf(">> %0.3f\n",y);     //Exibe Resultado
      }
      //---------------------------------//
      //  Identifica o dado              //
      //---------------------------------//
      else {
           ungetc(c, stdin);       //Devolve dado ao prompt
           flag_float=scanf("%f", &x);       //Lê dado e retorna estado da função "scanf"
           if (flag_float = 1){
               fc_push(&s,x);
           }
           else {
                printf(">> Dado invalido.\n");
                scanf("%c", &c);                     //Lê novamente o dado
           }
       }
}
printf(">> ");
scanf("%c",&c);
//-------------------------------------------------------------------------//
}

 

Acho que agora deu, ele só corta as bibliotecas...

[reebr 94]

struct no
{
    float info;
    struct no *prox;
};

void push (struct no **pilha, float i)
{
    struct no *p = NULL;

    p = (struct no *) malloc (sizeof(struct no));
    p -> info = i;
    p -> prox = *pilha;
    *pilha = p;
}

void pop (struct no **pilha, float *i)
{
    struct no *p;
    p = *pilha;             // aponta p/ o topo da pilha.
    *v = p-> info;
    *pilha = p->prox;       // faz a pilha apontar p/ o segundo nó (que passará a ser o primeiro).

    free (p);
}

void empty (struct no **pilha)
{
    if (*pilha == NULL)
        return 1; // pilha vazia.
    else
        return 0;
}

 

[guidjos 65]

Tenho algumas sugestões aos que postaram códigos:

 

1. Evitar criar confusão com return statements ao denotá-los como chamadas a funções (ao invés de "return(0);", dizer "return 0;"). O mesmo serve para o operador "sizeof", que é frequentemente confundido com uma função (prefira dizer "sizeof a;" ao invés de "sizeof(a);", a não ser que "a" seja o nome de um tipo.

 

2. Ao invés de "exit(1);", dizer "exit(EXIT_FAILURE);".

 

3. Evitar poluir a translation unit com declarações externas desnecessárias - isto acarreta imprevisibilidade (considere outros arquivos de código declarando nomes iguais na mesma T.U., ou mesmo outras T.U.s que possam querer fazer uso de external linkage). Na pior das hipóteses, algum objeto ou função é declarado com internal e external linkage (não-intencionalmente), e o resultado é, por definição, comportamento indefinido.

 

4. Evitar dizer que funções retornam ponteiros quando elas não retornam ponteiros.

 

5. Evitar casts desnecessários: a conversão implícita ("coercão") de (T *) para (void *) e vice-versa, sendo (T) um tipo de objeto, é bem-definida. Ou seja, "int *p = malloc(sizeof *int);" é correto. Na maioria das vezes, quem faz isto está escrevendo - sem saber - C++.

 

6. Em chamadas a malloc, realloc ou calloc, usar o próprio lvalue de destino do retorno da chamada para calcular o valor do argumento que especifica o tamanho da alocação ("int *p = malloc(sizeof *p);" ao invés de "int *p = malloc(sizeof (int));". Assim, se o tipo do objeto mudar, o código continua correto. Caso contrário, pode haver comportamento indefinido, que gera os piores tipos de bugs (não-determinísticos).

 

 

Dito isto, tem detalhes menos importantes sobre os códigos: há prováveis string literals que não foram envolvidas em aspas e códigos de HTML entities (o "address-of operator", "&", aparece como "&").

[reebr 94]

Obrigado pelas informações.

[guidjos 65]

Sem problema.

 

Acho que já compartilhei em outro tópico sobre fazer uma calculadora que usa RPN, mas segue o link da última que escrevi:

 

https://gist.github.com/guipn/5122682

 

Não lembro bem por quê, mas também fiz em outras linguagens... cada implementação tem suas vantagens.

 

Haskell: https://gist.github.com/guipn/5989678

JavaScript: https://gist.github.com/guipn/58bc57ba5fb161c9e58a

 

[]s