Stack<int> and Stack<string> problem solving

[fisken]

Hi,

I'm taking a distance course in C++ programming and problem solving at the univiersity of Saarland.
I'm a totaly beginner with programming and I have only studied a basic course in C-programming before.
At the moment I'm studing for the exam by looking at old exams and I stumbled over an exam task I do not understand how to solve.
So now I'm reaching out for help from you more experienced guys! :)
Please note that I would preffer to only get hints about how to solve this, not an entire solution, in order to learn.

The question is about correcting an implementation of a simple stack built with templates and then to write a small program that uses the stack class.
I have managed to correct the stack implementation so the stack works as intended. The stack is implemented using templates and under the hood it uses
only a simple array with 15 elements.
The stack has the following operations:
push() - push a element on to the stack
pop() - pop the top element from the stack
top() - returns the top most element of the stack
empty() - returns true if stack is empy, false otherwise
full() - return true if stack is full, false otherwise

The above works just fine and I have tested the stack implementation as a Stack<int>, Stack<string>, Stack<char> and Stack<bool>.

However, my problem lays in the program using the stack. The program shall read a line from stdin and print words in the same order as entered but print
integers in the reversed order and print everything to stdout. Below follows some examples for clarification:
Example 1:
input: one two three four five
output: one two three four five

Example 2:
input: 1 2 3 4 5
output: 5 4 3 2 1

Example 3:
input: one two 3 4 5 six seven 8 9 ten
output: one two 9 8 5 six seven 4 3 ten

The program also has the following requirements:
1. Multiple values are only allowed to be stored in my stack implementation
2. I may use as many stacks as I want
3. It is ok to assume that the user only enters strings and integers and no more than 15 of each kind on a single line

So far I have done the following:
1. I have created three stacks, one Stack<int> and two Stack<string>
2. I read an entire line and steps throu and determines which are integers and which are strings
3. I push the integers and strings into the corresponding stack.
4. When entire line is parsed, I pop all elements in the Stack<string> and pushes them into the second String<stack> (in order to be able to push the second String<stack> and get the strings in original order).
5. I pop both Stack<int> and second Stack<string> and print to stdout.

The above steps take care of example 1 and 2 above without problem. But I cannot figure out how to created example 3, i.e. I do not understand how to
control the order of strings and integers so that the output has the same format, e.g. string string int int int string string int int string in the
above example.
Do anyone of you guys understand how to solve this? If so, can you please point me in the right direction? And as I stated before, I would like to only
get hints about this in order to see if I can figure the rest out by myself. :)

Thanks in advance!
// Fisken

[discofire]

You could maintain another stack of integers, or array of integers that just stores 0's and 1's. The 0's can correspond to strings, and the 1's can correspond to integers. Then you read the next value from that stack to determine which data type you should retrieve next. You would populate the new array while reading in your original string from the user. An array of size 30 would guarantee there is enough space to fit 15 of each data type.

To print the final solution, loop through the 0's and 1's array, and for each 0, pop your string stack and for each 1, pop your integer stack.

[fisken]

Hi discofire,

thanks for the answer but I do not think that will solve the task. This because of two reasons:
1. "Multiple values are only allowed to be stored in my stack implementation", i.e. no extra array is allowed.
2. Using a Stack<int> for store the order is sufficient as long as they are no more than totally 15 elements (integers and strings) on one line, but "no more than 15 of each kind on a single line" says that it should be possible to have up to 30 elements on a line. So another stack will not have enough room to store the "format" information for such line since the given simple stack only has room for 15 elements.

Thanks for your response anyway.
Do you or someone else have another solution?

[keskiverto]

That limit of 15 is a good point. If one stack cannot do the job, then 15 will: Stack<Stack<bool>>

[fisken]

Hm, you have a point there kesikverto, that will probably work just fine.
But isn't that kinda ugly to use a stack with stacks only for storing the order?
To me, that feels like a hack and I cannot believe that the course at the university has an exam task that will require such a thing, or?
Maybe I'm wrong since I have little experience in programming and C++.

Are they no one that can figure out a cleaner solution to this task?
(Or maybe it is no other solution even though I would prefer one) :)

[keskiverto]

There might be other solutions, but it is clearly "problem solving" to solve a task with non-optimal tool.

Besides, doesn't our awkward approach test the Stack::full()?

[fisken]

Fair point, however, I still belive that the exam maker have another solution in mind.
Anyone else that have any suggestions how to attack this problem?

Thanks for the answers.

[fisken]

No one else that have a suggested solution for this task?

[a k n]

Cheat a bit , have a stack of string that only has one element , that string is made up of 0's and 1's
Or simply , Use a string or if you know/are allowed to use bit manipulations , use an unsigned integer (or uint32_t )and use its bits to set whether there's a string or int next.

[discofire]

Sorry for taking so long to get back to you. Since you can only have stacks as data structures, you can create another stack of ints and store the index of the string or int in the original input. The stack will need to be reversed like your int stack, but then as you're printing the final output, keep a counter, and whenever the counter equals the top value in your index array, print the corresponding data type, then pop that stack. Otherwise, print the opposite data type.