Writing a stack module

[yazici.batuhan]

Consider a stack module like (two files stack.h stack.cpp) which supports the these functions;

void push (stack *, std::string); std::string & pop(stack &);

bool isEmpty(stack &); std::string & top (stack *);

I didnt understand this part what it means. Also I declared stack like;

struct stack { … };

But with these functions, can i write this module without class?

[NathanOliver]

It looks like that is how your instructor wants this done. Why he would want it like this I have no idea. IMHO he should be cited for endangering the education of a student. You could do this with a class but since you functions need to have access to everything the stack contains I would just use a struct for the default public specifier.

[tinstaafl]

If you think of those statements like this:

void push (stack *, std::string); 
std::string & pop(stack &);    
bool isEmpty(stack &); 
std::string & top (stack *);

These are the prototypes for the functions. Whenever the actual code is separated from the class declaration this is the pattern that is usually followed.

[NathanOliver]

@ tinstaafl You wouldn't write a function like void push (stack *, std::string) if the function is a member of the class. You would write it like void push (std::string) and externally it would be void stack::push (std::string)

[yazici.batuhan]

PS: all thing is under there

1) Write a stack module (two files stack.cpp stack.h) supports the following functions

void push (stack *, std::string); std::string & pop(stack &); bool isEmpty(stack &); std::string & top (stack *);

Note that there is no isFull() function, therefore your stack should be never full (unless your heap memory is exhausted).

The stack should be declared as a struct, i.e.

struct stack { … };

You might declare additional structs in this module, however no classes should be used/declared in this module.

Reccomendation: Before continuing to the next step, write your module and test it using a simple function test1 such as

stack myStack; push(&myStack, "3"); push(&myStack, "5"); cout << pop(myStack) << isEmpty(myStack) << pop(myStack) << isEmpty(myStack) << endl; cout << pop(myStack) << endl;

2) Write a queue class (files queue.h, queue.cpp) and implement it using two stacks. No other data structures are allowed (HOW?). As opposed to the first part, in this part you should use classes but no structs, except the stacks that are already implemented as structs in the first part. The files queue.cpp should contain at least the following

class Queue { public: Queue(); void enqueue(string &); // intentionally different from stack.h string & dequeue(); bool isEmpty(); };

Reccomendation: Before continuing to the next step, write your module and test it using a simple function test2 such as

Queue myQueue; string three = "3"; string five = "5"; string six = "6"; string seven = "7"; myQueue.enqueue(three); myQueue.enqueue(five); cout << myQueue.dequeue() << myQueue.isEmpty() << endl; myQueue.enqueue(six); myQueue.enqueue(seven); cout << myQueue.dequeue() << myQueue.isEmpty() << endl; cout << myQueue.dequeue() << myQueue.isEmpty() << endl; cout << myQueue.dequeue() << myQueue.isEmpty() << endl; cout << myQueue.dequeue();

3) Read about the Reverse Polish Notation http://en.wikipedia.org/wiki/Reverse_Polish_notation and write an RPN expression evaluator using the queue and stack implemented in the previous sections. Your program should: a) read the entire input, parse it into tokens and store the recognized tokes in a queue one token at a time. b) get one token at a time from the queue and perform evaluation. You should recognize the following tokens (any other token is ignored by not adding to the queue at the first stage): Numbers, +, -,*,/,? . ? marks the end of an expression. When a ? is encountered you pop an element from the stack and print it. The stack should be empty after this operation, otherwise it is an expression error and the popped element should be pushed back to the stack. If the stack is empty in any other stage it is also an expression error and the program should print the contents of the queue and terminate. Sample Input: 4 23 + ? xy 31 9 + 3 * zx ? 2 3 ? + + 3 * ? Sample Output: 27 120 ERROR: Premature end of expression ERROR: Stack Empty: + 3 * ?

Explanation:

xy and zx are not recognized tokens and therefore not added to the queue. Therefore, at the end of the first stage the queue contains:

4 23 + ? 31 9 + 3 * ? 2 3 ? + + 3 * ?

4 and 23 are pushed into the stack.

+: 23 and 4 are popped and 27 is pushed ?: 27 is popped, the stack is empty as required, 27 printed. 31 and 9 pushed +: 9 and 31 popped and 40 is pushed 3 pushed *: 3 and 40 popped, 120 pushed ?: 120 is popped, the stack is empty as required, 120 printed. 2 and 3 pushed ?: 3 popped, the stack is not empty, print “ERROR: Premature end of expression”, push back 3 + : 3 and 2 popped, 5 pushed + : 5 popped, the stack is empty, an error message with the current token (+) and queue content ( 3 * ? ) are printed.

note: normally ? sign is dollar sign

[yazici.batuhan]

Maybe anyone understand better

[NathanOliver]

I would suggest you work on getting part one working first and then go on from there.

[yazici.batuhan]

Thank you for your help but, i did with class implamentation first one, but he asked to do without class, thats the point, it is easy with class doing like dynamic string stack.

[NathanOliver]

So rework the class to be a struct.

[Moschops]

So what's the problem?

It makes no sense to say that you can do it easily using a class but not like this. The functions in your class would be almost identical.

If you've done it with a class, you're almost done. Leave every member variable in the class, change the word "class" to "struct" and make sure everything's public visibility. Pull out every function and add stack* stackParameter to the parameters. In each function, where you used to use a member variable, put "stackParameter->" on the front.

Done.