CS 3358 Postfix Evaluation

This assignment has two parts pertaining to the stack implementation. The parts of code are given in the .cpp and .h files. The places you need to fill out in the code are marked by // TODO.

The stack implementation is supposed to be array-based in this assignment.

• In mystack.cpp, implement the member functions of the class MyStack, which is a class for integer stacks.
• In stacktest.cpp, complete the implementation of the function PostfixTest(), which uses an integer stack to evaluate postfix expressions. For simplicity, you can assume the postfix expression is input character by character (not an entire string), and each operand is a non-negative, single-digit integer, i.e., 0, 1, , 9. Nonetheless, you are still supposed to detect an invalid or illegal postfix expression input, e.g., "4 5 + -".

Sample tests:

Sample output for stacktest:

Testing the basic functions of your stack...
Please enter the max size of your stack: 2
Please enter 'p' for push, 'o' for pop, 'e' for exit: p
Please enter an integer value you would like to push: 1
Please enter 'p' for push, 'o' for pop, 'e' for exit: p
Please enter an integer value you would like to push: 7
Please enter 'p' for push, 'o' for pop, 'e' for exit: p
Nothing can be pushed in since the stack is full!
Please enter 'p' for push, 'o' for pop, 'e' for exit: o
7 has been popped out
Please enter 'p' for push, 'o' for pop, 'e' for exit: o
1 has been popped out
Please enter 'p' for push, 'o' for pop, 'e' for exit: o
Nothing has been popped out since the stack is empty!
Please enter 'p' for push, 'o' for pop, 'e' for exit: e
Now, start to use a stack to evaluate postfix expressions...
Please enter the operands (integers 1~9) and operators (+, -, *, /) one by one...
and enter '=' to indicate the end of the expression and to output the result.
1
3
5
*
+
1
-
=
The entered postfix expression results in 15

Another run:

Testing the basic functions of your stack...
Please enter the max size of your stack: 1
Please enter 'p' for push, 'o' for pop, 'e' for exit: e
Now, start to use a stack to evaluate postfix expressions...
Please enter the operands (integers 1~9) and operators (+, -, *, /) one by one...
and enter '=' to indicate the end of the expression and to output the result.
1
2
+
-
Error! No sufficient operands.

One more run:

Testing the basic functions of your stack...
Please enter the max size of your stack: 3
Please enter 'p' for push, 'o' for pop, 'e' for exit: e
Now, start to use a stack to evaluate postfix expressions...
Please enter the operands (integers 1~9) and operators (+, -, *, /) one by one...
and enter '=' to indicate the end of the expression and to output the result.
1
3
+
4
5
-
=
The entered postfix expression was not a legal one.

Starter codes:

mystack.h

#ifndef _MYSTACK_H_
#define _MYSTACK_H_

class MyStack
{
public:
MyStack(int size);
~MyStack();
void Push(int elem);
int Pop();
bool IsEmpty() const;
bool IsFull() const;

private:
int *elements; /* To declare a dynamically allocated array of integer elements for a stack (using C++ keyword new) */
int top; /* Index of the top element of the stack */
int max_size; /* Max number of elements that could be in the stack */
};

#endif

mystack.cpp

#include < iostream >
#include "mystack.h"

using namespace std;

/*
* Constructor
* Usage: MyStack(val);
* -------------------------
* A new stack is created and initialized. The initialized stack is made empty.
* The parameter 'size' is used to determine the maximum number of integer
* elements that can be held in the stack.
*/

MyStack::MyStack(int size)
{
// TODO
}


/* Destructor
* -----------------------
* Release the memory allocated for the stack.
*/

MyStack::~MyStack()
{
// TODO
}

/*
* Functions: Push, Pop
* Usage: st.Push(val); val = st.Pop();
* --------------------------------------------
* These are the fundamental stack operations that add an element to
* the top of the stack and remove an element from the top of the stack.
* A call to pop from an empty stack or to push on a full stack is an error.
* Make use of IsEmpty()/IsFull() (see below) to avoid the error.
*/

void MyStack::Push(int elem)
{
// TODO
}

int MyStack::Pop()
{
// TODO
}

/*
* Functions: IsEmpty, IsFull
* Usage: if (!IsEmpty()) ...
* -----------------------------------
* Return true if the stack is empty (IsEmpty) or full (IsFull).
*/

bool MyStack::IsEmpty() const
{
// TODO
}

bool MyStack::IsFull() const
{
// TODO
}

stacktest.cpp

#include < iostream >
#include "mystack.h"

using namespace std;

void PostfixTest()
{
// TO DO
}

int main()
{
cout << "Testing the basic functions of your stack..." << endl;
cout << "Please enter the max size of your stack: ";
int test_size;
cin >> test_size;

MyStack test_stack(test_size);

while (1)
{
cout << "Please enter 'p' for push, 'o' for pop, 'e' for exit: ";
char user_choice;
cin >> user_choice;

if (user_choice == 'e')
break;

switch (user_choice)
{
case 'p':
if (!test_stack.IsFull())
{
cout << "Please enter an integer value you would like to push: ";
int val;
cin >> val;
test_stack.Push(val);
}
else
cout << "Nothing can be pushed in since the stack is full!" << endl;
break;
case 'o':
if (!test_stack.IsEmpty())
cout << test_stack.Pop() << " has been popped out" << endl;
else
cout << "Nothing has been popped out since the stack is empty!" << endl;
break;
default:
cout << "Invalid user-input character. Please try again." << endl;
}
}

cout << "Now, start to use a stack to evaluate postfix expressions..." << endl;
PostfixTest();

return 0;
}