Skip to main content
GameDev.net gamedev.net
🔒 Locked

Stack problem in C

Started by CodeguruX Oct 28, 2005 at 9:42 PM 3 replies 550+ views
Original Post
CodeguruX
CodeguruX
Having a problem with this stack implementation in C and I can't figure out how this one node keeps changing on me.

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

struct stackNode
{
  char *data;
  struct stackNode *nextPtr;
};

typedef struct stackNode STACKNODE;
typedef STACKNODE *STACKNODEPTR;

void push(STACKNODEPTR *, char*);
char* pop(STACKNODEPTR *);
int isEmpty(STACKNODEPTR);
void printStack(STACKNODEPTR);

int main()
{
  FILE *file;
  STACKNODEPTR top = NULL;
  char c, *temp, str[9]="", filename[100], infix[302], postfix[302];
  int i,j,k;
  
  do
  {
    printf("Enter the name of the file containing the infix expression: ");
    scanf("%s",filename);
    file= fopen(filename,"r");
    
    if(file == NULL)
      printf("File does not exist, enter again.\n");
  }while(file == NULL);
  
  i=0;
  while ((c= fgetc(file)) != EOF)
  {
    if (c != ' ')
    {
      printf("%c",c);
      infix= c;
      i++;
    }
  }

  printf("The original infix expression is:\n%s\n",infix);
  push(⊤,"(");
  printStack(top);
  infix= ')';
  infix[i+1]= '\0';
  printf("%s\n",infix);

  i=0;
  j=0;
  while (!isEmpty(top))
  {
    if(infix >= '0' && infix <= '9')
    {
      while(infix >= '0' && infix <= '9')
      {
        postfix[j]= infix;
        i++;
        j++;
      }
    
      postfix[j]= ' ';
      j++;
    }
    else if(infix == '(')
    {
      str[0]= infix;
      temp= str;
      push(⊤, temp);
      i++;
      printStack(top);
    }
    else if(infix == '+' || infix == '-' || infix == '*' || infix == '/' ||
            infix == '^')
    {
      switch(infix)
      {
        case '+':
        case '-':
          while(top->data[0] == '*' || top->data[0] == '/' || top->data[0] == '^')
          {
            temp= pop(⊤);
            printStack(top);
            postfix[j]= temp[0];
            j++;
            postfix[j]= ' ';
            j++;
          }
          k= sprintf(str,"%c",infix);
          temp= str;
          printf("%s\n");
          printStack(top);
          printf("Push\n");
          push(⊤, temp);
          printStack(top);
          i++;
          printStack(top);
          break;
        case '*':
        case '/':
          while(top->data[0] == '^')
          {
            temp= pop(⊤);
            printf("Operator1.5\n");
            printStack(top);
            postfix[j]= temp[0];
            j++;
            postfix[j]= ' ';
            j++;
          }
          
                           ********** 
          str[0]=infix; ***Here***
                           **********

          temp= str;
          push(⊤, temp);
          i++;
          printStack(top);
          break;
        default:
          break;
      }
    }
    else if(infix == ')')
    {
      while(top->data[0] != '(')
      {
        temp= pop(⊤);
        printStack(top);
        postfix[j]= temp[0];
        j++;
        postfix[j]= ' ';
        j++;
      }
      
      temp= pop(⊤);
      printStack(top);
    }
  }
  postfix[j]= '\0';
  printf("The expression in postfix notation is:\n%s\n",postfix);


  return 0;
}

/* Insert a node at the stack top */
void push(STACKNODEPTR *topPtr, char *info)
{   STACKNODEPTR newPtr;

   newPtr = malloc(sizeof(STACKNODE));
   if (newPtr != NULL) {
      newPtr->data = info;
      newPtr->nextPtr = *topPtr;
      *topPtr = newPtr;
   }
   else
      printf("%d not inserted. No memory available.\n", info);
}

/* Remove a node from the stack top */
char* pop(STACKNODEPTR *topPtr)
{
   STACKNODEPTR tempPtr;
   char *popValue;

   tempPtr = *topPtr;
   popValue = (*topPtr)->data;
   *topPtr = (*topPtr)->nextPtr;
   free(tempPtr);
   return popValue;
}

/* Print the stack */
void printStack(STACKNODEPTR currentPtr)
{
   if (currentPtr == NULL)
      printf("The stack is empty.\n\n");
   else {
      printf("The stack is:\n");

      while (currentPtr != NULL) {
         printf("%s --> ", currentPtr->data);
         currentPtr = currentPtr->nextPtr;
      }

      printf("NULL\n");
   }
}

/* Is the stack empty? */
int isEmpty(STACKNODEPTR topPtr)
{
   return topPtr == NULL;
}







The equation I have in the file is (6*67)-23/5. At the spot where I marked ***here*** the stack seems to replace the current top node's data with whatever I set the str[0] element to be and I don't see how that's possible. The stack right before that line is ( --> ( --> NULL and right after it sets it to * --> ( --> NULL, then it proceeds to change it to * --> * --> ( --> NULL when I use my push function like it is intended to do. Anyone have a guess? Thanks... CodeguruX [Edited by - CodeguruX on October 28, 2005 10:08:50 PM]
Zahlman
Zahlman
void push(STACKNODEPTR *topPtr, char *info){   STACKNODEPTR newPtr;   newPtr = malloc(sizeof(STACKNODE));   if (newPtr != NULL) {      newPtr->data = info; // <-- !!!!!      newPtr->nextPtr = *topPtr;      *topPtr = newPtr;   }   else      printf("%d not inserted. No memory available.\n", info);}


newPtr->data is a pointer, and it is now pointing to the chunk of data that info points to. If you change something via (thing passed as 'info')[(index)] later, that change also appears in every node that was 'push'ed with that thing, because a shallow copy has been made.
CodeguruX
CodeguruX
Should have guessed it was in the code I didn't write, I just modified it for using a string instead of an integer. Is there a way to pass it by value so that data is just given the value of info if that even makes sense. I'm kinda stumped on this at the moment...

CodeguruX
CodeguruX
CodeguruX
WOOT! Ok I love that someone was thinking about this at some point in time to make the strdup function. Instead of:

newPtr->data = info;

I simply changed it to

newPtr->data = strdup(info);

So it only takes what's in the info string and throws back the value straight into the newPtr->data. I am kinda new to C libraries having been using C++ for years now so excuse me if I get a little excited over trivial triumphs. Hope this will help someone else at some point. Thank you for the help...

CodeguruX
Zahlman
Zahlman
Remember that you will need to deallocate the memory eventually as well. In this case, when you pop() a node, you will pass back a pointer to the node's copy, so the client should free() the string that it received via pop() after it's done with it (unless it will store the string somewhere else).

Since you are familiar with C++, you should be familiar with std::string; you may want to invest the time to produce a rough equivalent (keeping in mind that it won't be templated on the character type and that you can't really do RAII properly in C).

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.