Solved

Top Urgent!  Strange Problem in a stack

Posted on 1998-10-27
10
171 Views
Last Modified: 2010-04-02
I got into a strange program of a c++ program.
Here is the source:

#include <iostream.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
//#include <conio.h>

class Stack
{
private:
   char *buffer[80];
   int index, buf_size;
public:
      Stack();            //a default size is used
      Stack(int size);  //initialise the buffer to the specified size
      ~Stack();              //destructor

   void push(char *);      //push an integer to the stack
   char * pop(void);      //pop up an item
   int Is_empty(void);  //return '1' if emtpy, otherwise '0'
   int Is_full(void);        //retunr '1' if full, otherwise '0'
}

Stack::Stack()
{
   buf_size = 10;
   index = -1;
}

Stack::~Stack()
{
   index = -1;
   buf_size = 0;
}

void Stack::push(char *item)
{
   index++;
   buffer[index] = item;
}

char * Stack::pop(void)
{
   return buffer[index--];
}

int Stack::Is_empty(void)
{
   if (index < 0)
      return 1;
   else
      return 0;
}

int Stack::Is_full(void)
{
   if (index >= buf_size-1)
      return 1;
   else
      return 0;
}

Stack::Stack(int size)
{
   *buffer = new char[buf_size = size];
   index = -1;
}

void main()
{
   Stack operand(80), sign(80);
   char expression[80];              //holding the string input from keyboard
   char *temp_item="";

   cout << "Input:" << endl;
   cin.getline(expression, 80, '\n');

   for (int i = 0; i < strlen(expression); i++) {
      if(isdigit(expression[i])) {
       temp_item=strncat(temp_item, &expression[i], 1);
       operand.push(temp_item);
       cout << "i = " << i << " temp_item = " << temp_item << endl;
      }
   }

   while (!operand.Is_empty())
      cout << "from stack: " << operand.pop() << endl;

}

This program makes me crazy as it didn't give me the expected result. After running the above program, the output is:
Input:
123abc4
i = 0 temp_item = 1
i = 1 temp_item = 12
i = 2 temp_item = 123
i = 6 temp_item = 1234
from stack: 1234
from stack: 1234
from stack: 1234
from stack: 1234

Why it is so strange because in the program, I push the "temp_item" into the stack.  The value of "temp_item" changes as it shows above.  However, when the items are pop out from the stack, they become all the same.

My desired result should be:
Input:
123abc4
i = 0 temp_item = 1
i = 1 temp_item = 12
i = 2 temp_item = 123
i = 6 temp_item = 1234
from stack: 1234
from stack: 123
from stack: 12
from stack: 1

Do anyone know what's wrong?  What changes should I make in order to get my desired output?
Tks alot.  
0
Comment
Question by:chuyan
  • 7
  • 2
10 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 200 total points
Comment Utility
There are a bunch of problems.  You need to start with the changes I proposed on your other question.  i.e. the stack need to store private copies of the strings.
0
 

Author Comment

by:chuyan
Comment Utility
nietod,

sorry, it seems that your solution is too difficult for me to understand.
can i just using the existing stack?
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
Here is one problem.

 char *temp_item="";
    *   *   *
temp_item=strncat(temp_item, &expression[i], 1);

When you declare temp_item you allocate space for a 0 character long string .  That is, space for a NUL character that marks the string's end and no other characters.  Then when you do the strncat() it tries to store a character AND a NUL terminator in the string.  That is you had room for one byte but it will try to store 2.  That is bad!   With the C "char *" string operatiojns, you must always make sure you are working with character arrays that are long enough for the strings you are generating.  The RTL procedures you call, like strcpy() and strcat() will assume that the character arrays you pass to them are long enough for the strings they will create.  They have no way to know if they aren't.  so it is up to you to make sure.  

Buit before  you start worring about that.  Lets get the stack class cleaned up.   Look at the suggestions I made in the other question.  Ask me if you have questions.  Make the changes and then post what you get done or e-mail it to me at nietod@theshop.net.



   operand.push(temp_item);
0
 

Author Comment

by:chuyan
Comment Utility
tks first.

Why I added the statment:
 char *temp_item="";
because if without this, after running the program, the dos session will forced to close.


0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>> can i just using the existing stack?
You could use it in very limited ways if you were sure to stick to the conditions under which it would work.  But you will find those conditions too limiting and you will find it impossible to stick to them----even if you intend to.  

Let me give you an example of what is wrong.  Lets simplify the stack class so that it holds only one string--a very small stack.  Ratter than having an array if string pointers called buffer[], we will have just one string pointer, called StrPtr.  Note the only difference is that the old stack used to have many of these string pointers, the new one has just one.  The class will look like

class Simple
{
 char *StrPtr;  // -> string on the "stack"
};

New we will have a simple push operation like

Simple::Push(char *NewStr)
{
   StrPtr = NewStr;
}

We don't have to worry about setting the number of items on the stack or finding the right entry in buffer[] because we are storing just oen string.  Other than that, this is the same.  Do you agree/understand?

continues
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 22

Expert Comment

by:nietod
Comment Utility
Now look at the following code

char expression[80];

strcpy(expression,"First line.");
SomeStack.Push(expression);
strcpy(expression,"Second line.");

You can think of those strcpy() lines as lines that change the strings you are working with.  Line the lines that read from cin with getline()  or your strcat() lines.  These strcpy() will have the same affect, they alter the strings you are working with.  Now you probaly think that
at the end of the above code, the line "First line" is stored in the simple stack.  It isn't.  Second line is.  An no you never even stored "Second Line", yet that is what is there.

continues
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
The problem is that the stack is does not store the string passed to it.  It stores a pointer to the caller's string.  If the caller alters the string, the pointer is pointing to the altered string.  A simple example of this would be

char expression[80];
char *StrPtr;

strcpy(expression,"First line.");
StrPtr = expression;
strcpy(expression,"Second line.");

Note that what thos does is make StrPtr point to the expression character array.  Thus StrPtr doesn't store a string, it just references the string stored in expression.  when we change expression, the string that StrPtr references is changed.  This how your stack works.  You load a character array with data and then telll the stack to store the string.  But it doesn't store the string, it stores a pointer to the character array that currently holds the string.   Then you go on and change that character array (for getting the next string to be stored in the stack).  Now the stack is holding a new string (or a pointer to it) even though you didn't want that.

make sense?

In summary "char *" variables don't store strings.  They "refer" to them.  You need to allocate a character array to store a string.  The stack class I proposed allocates the char arrays as needed.  take a look back, now.  It might be clearer.
0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
>>Why I added the statment:
>>      char *temp_item="";
>>     because if without this, after running the program, the
>> dos session will forced to close.

That fixes one bug with another.

note that if you had

  char *temp_item;
   *   *   *
  strncat(temp_item, &expression[i],1);

the problem is that temp_item is a pointer to a character array, but it was not initialized to point to any particular character array.  Thus as I said before, when you call strncat() (or similar procedure) you must specify a pointer to a character array that is big enough to hold the result.  but in the above you are specifying a pointer to some random location in memory.

When you fix it with

  char *temp_item = "";
   *   *   *
  strncat(temp_item, &expression[i],1);

you now make it point to a character array that has room for 0 characters.  (room only for  the NUL termiantor).  Thus strncar will still cause problems (maybe not noticed right away) bacause it needs toom for 1 character (2 bytes total) and you didn't give it enough.

Note that a line like

char *Ptr = "X";

is the same as

char SomeBuf[2] = "X";
char *Ptr = SomeBuf;

i.e. Ptr does not store the string.  It points to a character array that stores the string.  In the first example, C++ makes a "hidden" character array for you.  In the 2nd example it was made by the programmer.  In either case there is a 2 byte character array (enough for 1 character and the NUL).  And the pointer points to it.  it does not store "X" the character array stores "X"


0
 
LVL 22

Expert Comment

by:nietod
Comment Utility
What is happening with this?  Are you having any luck?
0
 

Expert Comment

by:piyushsharma
Comment Utility
nietod has given a good solution. I would like to add a few lines
to this .

>>class Stack
>>{
>>private:
>>   char *buffer[80]; // is a pointer to array of 80 chars.

>>void Stack::push(char *item)
>>{
>>      index++;
>>      buffer[index] = item; // PROBLEM lies here.
>>}

the above push method has the problem. This code assigns a pointer to array of chars to the buffer[index], which(item) itself is being updated with every "strcat" operation. So, at last this(item) is pointing to the complete string, whatever inputed. Eventually every buffer[index] points to the same array of chars, and thus the result is same string.

Following change in push method will obtain the objective.

>>void Stack::push(char *item)
>>{
>>      index++;
>>//      buffer[index] = item; // PROBLEM lies here.
>>      if(index>0)
>>       buffer[index] = new char [80];
>>      strcpy(buffer[index], item);
>>}

In the constructor of Stack ie:
>>Stack::Stack(int size)
>>{
>>//   *buffer = new char[buf_size = size]; // NOT REQUIRED as                                                                                                         // the buffer[0] is                                                                                                                                                                                                           // alredy allocated memory for 80 chars in declaration.                                                       >>   index = -1;
>>}
Hope this help.
0

Featured Post

What Security Threats Are You Missing?

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

744 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

15 Experts available now in Live!

Get 1:1 Help Now