Expert: Zlatko - 11/22/2009

Question
QUESTION: Write a program that reverses the string contents of a stack (the top and bottom elements exchange positions, the second last element exchange positions, and so forth until the entire stack is reversed). Hint: You may use a second stack. The following diagram illustrates the exchange process.

A   I
B   H
C   G
D   F
E   E
F   D
G   C
H   B
I   A

this id the code i write to read an integer and put in the stack. then reverce the stack.
can you tell me how to read a string and store the string in a stack and then reverce it.
thank you.




#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
/* self-referential structure */
struct stackNode {
  int data;          /* define data as an int */
  struct stackNode *nextPtr; /* stackNode pointer */
}; /* end structure stackNode */

struct stackNode1 {
  int data;          /* define dat1a as an int */
  struct stackNode1 *nextPtr; /* stackNode1 pointer */
}; /* end structure stackNode1 */

typedef struct stackNode StackNode; /* synonym for struct stackNode */
typedef StackNode *StackNodePtr; /* synonym for StackNode* */

typedef struct stackNode1 StackNode1; /* synonym for struct stackNode */
typedef StackNode1 *StackNode1Ptr; /* synonym for StackNode* */

/* prototypes */
void push( StackNodePtr *topPtr, int info );
void push1( StackNode1Ptr *topPtr, int info );
int pop( StackNodePtr *topPtr );
int isEmpty( StackNodePtr topPtr );
void printStack( StackNodePtr currentPtr );
void printStack1( StackNode1Ptr current1Ptr );

int i,counter=0;
/* function main begins program execution */
int main( void )
{



  StackNodePtr stackPtr = NULL; /* points to stack top */
  StackNode1Ptr stack1Ptr = NULL; /* points to stack top */

  //StackNodePtr stackPtr = NULL; /* points to stack top */

  char value[15];  /* int input by user */

  clrscr();  /*Clear screen*/

  for (i=0;i<10;i++)
   {
      printf( "Enter [%2d] integer: " ,i);
      scanf("%d",&value);
      push( &stackPtr, value );
      printStack( stackPtr );
      counter+=1;
      printf("counter : %d\n",counter);
    }

  clrscr();
  for(i=0;i<counter;i++)
  {
     printStack( stackPtr );
  }
  getch();

  clrscr();
  for(i=0;i<counter;i++)
  {
  push1( &stack1Ptr, pop( &stackPtr ) );
     printStack1( stack1Ptr );
  }
  getch();
  return 0; /* indicates successful termination */

} /* end main */

/* Insert a node at the stack top */
void push( StackNodePtr *topPtr, int info )
{
  StackNodePtr newPtr; /* pointer to new node */

  newPtr = malloc( sizeof( StackNode ) );

  /* insert the node at stack top */
  if ( newPtr != NULL ) {
     newPtr->data = info;
     newPtr->nextPtr = *topPtr;
     *topPtr = newPtr;
  } /* end if */
  else { /* no space available */
     printf( "%d not inserted. No memory available.\n", info );
  } /* end else */

} /* end function push */





void push1( StackNode1Ptr *topPtr, int info )
{
  StackNode1Ptr newPtr; /* pointer to new node */

  newPtr = malloc( sizeof( StackNode1 ) );

  /* insert the node at stack top */
  if ( newPtr != NULL ) {
     newPtr->data = info;
     newPtr->nextPtr = *topPtr;
     *topPtr = newPtr;
  } /* end if */
  else { /* no space available */
     printf( "%s not inserted. No memory available.\n", info );
  } /* end else */

} /* end function push */

/* Remove a node from the stack top */
int pop( StackNodePtr *topPtr )
{
  StackNodePtr tempPtr; /* temporary node pointer */
  int popValue; /* node value */

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

  return popValue;

} /* end function pop */

/* Print the stack */
void printStack( StackNodePtr currentPtr )
{

  /* if stack is empty */
  if ( currentPtr == NULL ) {
     printf( "The stack is empty.\n\n" );
  } /* end if */
  else {
     printf( "The stack is:\n" );

     /* while not the end of the stack */
     while ( currentPtr != NULL ) {
   printf( "%s --> ", currentPtr->data );
   currentPtr = currentPtr->nextPtr;
     } /* end while */

     printf( "NULL\n" );
  } /* end else */

} /* end function printList */


void printStack1( StackNode1Ptr current1Ptr )
{

  /* if stack is empty */
  if ( current1Ptr == NULL ) {
     printf( "The stack is empty.\n\n" );
  } /* end if */
  else {
     printf( "The reversed stack is:\n" );

     /* while not the end of the stack */
     while ( current1Ptr != NULL ) {
   printf( "%s --> ", current1Ptr->data );
   current1Ptr = current1Ptr->nextPtr;
     } /* end while */

     printf( "NULL\n" );
  } /* end else */

} /* end function printList */




/* Return 1 if the stack is empty, 0 otherwise */
int isEmpty( StackNodePtr topPtr )
{
  return topPtr == NULL;

} /* end function isEmpty */




ANSWER: Hello Canno.

Thank you for working so hard on your assignment. It has some problems, but because you worked so hard, I have corrected the problems for you. I've also added a final output in the main program.

All my changes start with the comment:  /*XXX


Two things I must comment on.

1)

You do not need a second stack node datatype called stackNode1. You re-use the stackNode datatype for all stacks. All code dealing with stackNode1 should be removed, as I have done with #if 0 / #endif. After you read my comments, you should delete the dead code between the #if 0 and the #endif

Of course, each stack needs its own stackPtr variable, so you need 2 stack pointers
   StackNodePtr stackPtr = NULL; /* points to stack top */
   StackNodePtr stack1Ptr = NULL; /* points to stack top */
but they are both of the same datatype.

2)

You are not really reversing the first stack, you are simply moving the contents of the first stack to the second. On the second stack, the contents are in the reverse order, but I don't know if that is what your instructor wants.

I'm guessing that your instructor wants the contents of the first stack to be reversed, and to end up on the first stack. The second stack is used only for temporary storage. What do you think ?

Let me know if you need more help.

Best regards
Zlatko

Code follows:

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

/* self-referential structure */
struct stackNode {
   int data;          /* define data as an int */
   struct stackNode *nextPtr; /* stackNode pointer */
}; /* end structure stackNode */




/*XXX You do not need a stackNode1 datatype, you use the same stackNode for all stacks.
This is a data type declaration, not a variable declaration */
#if 0 /*XXX removed from program */
struct stackNode1 {
   int data;          /* define dat1a as an int */
   struct stackNode1 *nextPtr; /* stackNode1 pointer */
}; /* end structure stackNode1 */
#endif





typedef struct stackNode StackNode; /* synonym for struct stackNode */
typedef StackNode *StackNodePtr; /* synonym for StackNode* */




#if 0 /*XXX removed from program */
typedef struct stackNode1 StackNode1; /* synonym for struct stackNode */
typedef StackNode1 *StackNode1Ptr; /* synonym for StackNode* */
#endif




/* prototypes */
void push( StackNodePtr *topPtr, int info );
/* XXX void push1( StackNode1Ptr *topPtr, int info ); */
int pop( StackNodePtr *topPtr );
int isEmpty( StackNodePtr topPtr );
void printStack( StackNodePtr currentPtr );
/*XXX void printStack1( StackNode1Ptr current1Ptr ); */

int i,counter=0;
/* function main begins program execution */
int main( void )
{
   StackNodePtr stackPtr = NULL; /* points to stack top */
   /*XXX Use the same datatype for the second stack StackNode1Ptr stack1Ptr = NULL; /* points to stack top */
   StackNodePtr stack1Ptr = NULL;



   /*XXX change value from char to int if you are using scanf %d */
   /*XXX You do not need an array here because you are reading a single integer, and
   pushing it onto the stack */
   /*XXX char value[15];  /* int input by user */
   int value;

   clrscr();  /*Clear screen*/

   for (i=0;i<10;i++)
   {
       printf( "Enter [%2d] integer: " ,i);
       scanf("%d",&value);
       push( &stackPtr, value );
       printStack( stackPtr );
       counter+=1;
       printf("counter : %d\n",counter);
   }

   clrscr();
   /*XXX you only need to print the stack once here, for(i=0;i<counter;i++) */
   /*XXX { */
       printStack( stackPtr );
   /*XXX } */
   getch();

   clrscr();
   printf("Now doing reversal: Moving stackPtr to stack1Ptr\n");
   for(i=0;i<counter;i++)
   {
       /*XXX Not using push1 and printStack1, the same function works on all stacks */
       push( &stack1Ptr, pop( &stackPtr ) );
       printStack( stack1Ptr );
   }

   /*XXX added printout of the results */
   printf("\n******************* RESULTS *******************\n");
       printf("Printing stack1Ptr\n------------_-----\n");
       printStack( stack1Ptr );
       printf("Printing stackPtr\n-----------------\n");
       printStack( stackPtr );

   getch();
   return 0; /* indicates successful termination */

} /* end main */

/* Insert a node at the stack top */
void push( StackNodePtr *topPtr, int info )
{
   StackNodePtr newPtr; /* pointer to new node */

   newPtr = malloc( sizeof( StackNode ) );

   /* insert the node at stack top */
   if ( newPtr != NULL ) {
       newPtr->data = info;
       newPtr->nextPtr = *topPtr;
       *topPtr = newPtr;
   } /* end if */
   else { /* no space available */
       printf( "%d not inserted. No memory available.\n", info );
   } /* end else */

} /* end function push */

/* Remove a node from the stack top */
int pop( StackNodePtr *topPtr )
{
   StackNodePtr tempPtr; /* temporary node pointer */
   int popValue; /* node value */

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

   return popValue;

} /* end function pop */

/* Print the stack */
void printStack( StackNodePtr currentPtr )
{

   /* if stack is empty */
   if ( currentPtr == NULL ) {
       printf( "The stack is empty.\n\n" );
   } /* end if */
   else {
       printf( "The stack is:\n" );

       /* while not the end of the stack */
       while ( currentPtr != NULL ) {
         /*XXX your stack has integers, not strings, so I changed %s to %d */
         printf( "%d --> ", currentPtr->data );
         currentPtr = currentPtr->nextPtr;
       } /* end while */

       printf( "NULL\n" );
   } /* end else */

} /* end function printList */

/* Return 1 if the stack is empty, 0 otherwise */
int isEmpty( StackNodePtr topPtr )
{
   return topPtr == NULL;

} /* end function isEmpty */


---------- FOLLOW-UP ----------

QUESTION: Thank you so much that correct my code.
So how about i want to read a string into the stack and reverse the stack like what i have done before that i read into first stack then i use move to the second stack so that the content in the stack is been reverse. Thank you.

ANSWER: Hello Canno

There are 2 ways that I can read your problem.
1) You want to read one string into the stack so that each stackNode has one character.
or
2) you want each stackNode to contain a string.

When I look at the original problem statement, I think you are asking for the first way. Please let me know if I am wrong.


If you want to store a single character in each stackNode, you need very few changes. You can keep the stackNode data as an integer. The input loop looks like this:

   while ((value = getc(stdin)) != '\n')
   {
       push( &stackPtr, value );
       counter+=1;
   }

Instead of :
   //for (i=0;i<10;i++)
   //{
   //    printf( "Enter [%2d] integer: " ,i);
   //    scanf("%d",&value);
   //    push( &stackPtr, value );
   //    printStack( stackPtr );
   //    counter+=1;
   //    printf("counter : %d\n",counter);
   //}

The new input loop reads characters until you press the "Enter" key. You can add whaever prompting and printing you like to the input loop.

When printing out the stack, use %c, instead of %d
printf( "%c --> ", currentPtr->data );


---------- FOLLOW-UP ----------

QUESTION: thank you so much.
How about i want to read the string and store in each stack node?

Thank you so much that kindly helping me to solve my question.

Answer
Hello Canno
Here are the changes you need to make:


1)
change stackNode to have:
char* data;
as the data type.

2)
change push to accept char* instead of int

3)
change pop to return char*

4)
Change your input routine to accept strings. This is tricky. You need to decide how long a string can be. You need to read characters into a buffer. You need to make sure the buffer does not overflow and you need to drain your keyboard buffer so that the next input request doesn't get garbage left over from the previous input request.

For example, if you have a destination buffer 31 characters long, it can hold 30 characters, and 1 zero byte to end the string. If the user types in 40 characters, the first 30 can go into the destination buffer, but the last 10 need to be read and thrown away, otherwise they will interfere with the next input request.

Many beginners try to do a fflush(stdin) to drain the keyboard buffer, but this is wrong. fflush is not defined on input streams, only on output streams.

Here is a sample input string function

/*
function inputString
takes a destination buffer, and the space available in the destination
The function fills in the destination as much as possible, reserving the last
byte for the 0 string terminator.

The function returns when the user enters the newline character. The newline character
is not put into the buffer and is not part of the input count.

The function returns the number of characters the user attempted to input.
*/
int inputString(char* dest, int space)
{
   int count = 0;
   if (dest == NULL || space == 0) return 0;

   while(1)
   {
       char c = getc(stdin);
       if (c == '\n' || c == EOF)
       {
         if (space) *dest = 0;
         break;
       }

       ++count;
       if (space > 1)
       {
         *dest++ = c;
         --space;
       }
       if (space == 1)
       {
         *dest = 0;
         --space;
       }
   }
   return count;
}

5)
You need to change your input loop to use the inputString function. I used this loop for testing.

   char value[16];
   for(i = 0; i < 10;)
   {
       printf( "Enter [%2d] string: " ,i);
       if (inputString(value, sizeof(value)) >= sizeof(value))
       {
         printf("Thats too long, try again\n");
       }
       else
       {
         i++;
         counter+=1;
         push( &stackPtr, strdup(value) );
       }
   }

6)
Change printStack to use %s

Best regards
Zlatko