chuyan
asked on
Top Urgent! Strange Problem in a stack
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_ite
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.
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_ite
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.
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Here is one problem.
char *temp_item="";
* * *
temp_item=strncat(temp_ite
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);
char *temp_item="";
* * *
temp_item=strncat(temp_ite
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);
ASKER
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.
Why I added the statment:
char *temp_item="";
because if without this, after running the program, the dos session will forced to close.
>> 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
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
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
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
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.
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.
>>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"
>> 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"
What is happening with this? Are you having any luck?
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.
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.
ASKER
sorry, it seems that your solution is too difficult for me to understand.
can i just using the existing stack?