Lab 3 (100 pts)
Due Tuesday, January 30 at 9:20am on Canvas

PAIR PROGRAMMING REQUIREMENTS
  • Watch the video and answer the questions on this worksheet.
  • Both partners fill in, sign and date the pair programming contract.
  • Upload the two documents along with your assignment to Canvas under Lab 3.
  • BOTH partners submit the pair programming contract and worksheet.
  • Only ONE partner submits the lab assignment.

Part 1: Implementing Your Stack and Queue (60 pts)
  • Before you begin Part 2 of this lab, make sure that you have your Stack and Queue data structures working properly.
  • Note: Your will be using the Queue class that you wrote during class time.
  • Note that I would like you to add in the consts to the functions in your Stack and Queue (should these go on access functions or manipulation procedures?).
  • For the Queue class instructions, see Queue Lesson.
  • For the Stack class instructions, see Stack Lesson
  • No credit if you altering your Queue.h and Stack.h class definitions from what was provided in class.
  • Make sure to test all of your functions to ensure that they are working properly in separate test files named QueueTest.cpp and StackTest.cpp (where you should call the functions inside of main).
  • -20 points for not testing each function fully in QueueTest.cpp and StackTest.cpp

Queue

#ifndef QUEUE_H_
#define QUEUE_H_

#include <iostream>
#include <cstddef>
#include <assert.h>
using namespace std;

template<class queuedata>
class Queue {
public:
    /**constructors and destructors*/

    Queue();
    //initializes an empty queue
    //post: an empty queue created with default values for all fields

    Queue(const Queue &Q);
    //initializes queue to have same elements as another queue
    //post: a deep copy of queue

    ~Queue();
    //frees memory allocated to the queue
    //post: memory for queue has been freed

    /**manipulation procedures*/

    void dequeue();
    //removes an element from the front of the queue
    //pre: size!=0
    //post: an element removed from the front of the queue

    void enqueue(queuedata data);
    //adds an element to the end of the queue
    //post: an element added to the end of the queue

    /**accessors*/

    bool operator==(const Queue &Q);
    //returns whether this queue is equal to another queue

    queuedata getFront() const;
    //returns the element at the front of the queue
    //pre: size != 0

    int getSize() const;
    //returns the size of the queue

    bool isEmpty() const;
    //returns whether the queue is empty

    /**additional queue operations*/
    void printQueue() const;
    //prints the elements in the queue separated by a blank space to stdout

private:
    struct Node {

        queuedata data;
        Node* next;
        Node(queuedata d) {
            next = NULL;
            data = d;

        }
    };

    Node* front;
    Node* end;
    int size;

};

#endif /* QUEUE_H_ */


Stack

#ifndef Stack_H_
#define Stack_H_

#include <iostream>
#include <cstddef>
#include <assert.h>

using namespace std;

template <class stackdata>
class Stack
{
    public:
        /**constructors and destructors*/

        Stack();

        //initializes an empty stack
        //post: an empty stack created with all fields assigned default values

        Stack(const Stack &S);
        //initializes this stack to have same elements as S
        //post: a deep copy of the stack S


        ~Stack();
        //frees memory allocated to the stack
        //post: memory for stack has been freed

        /**manipulation procedures*/

        void pop();
        //removes an element from the top of the stack
        //pre: size != 0
        //post: an element has been removed from the top of the stack

        void push(stackdata data);
        //adds an element to the top of the stack
        //post: an element added to the top of the stack

        /**accessors*/


       bool operator==(const Stack &S);
       //returns whether this stack is equal to another stack S

       stackdata peek() const;
       //returns the element at the top of the stack
       //pre: size != 0

       int getSize() const;
       //returns the size of the stack

       bool isEmpty() const;
       //returns whether the stack is empty


       /**additional operations*/

       void printStack() const;
       //prints the elements in the stack each element separate by a blank space to stdout

    private:
       struct Node {
           stackdata data;
           Node* next;

           Node(stackdata d){
               data = d;
               next = NULL;
           }
       };

       Node* top;
       int size;

};

Part 2: Polish and Infix Notation Calculator (40 pts)

  • Using one or more stacks, create a calculator program that reads in user input provided in Polish Notation.
  • In Polish notation, the mathematical operators are always placed on the left of the operands (the numbers).
  • This form of notation eliminates the need to use parenthesis to indicate order of operations.
  • Some calculators are programmed this way (though it is rare) or have a Polish notation setting.
  • We are more familiar with infix notation (the way most calculators are programmed.)
  • For example, the following equation, written in both infix and Polish notation

            ((5 + 3) * 4) / 7 //infix notation

     / * + 5 3 4 7 //Polish notation

  • For more information on Polish Notation, read the article here
  • You can also watch this video here


Assumptions

  • For this assignment, you may assume that the user is entering each symbol and number followed by a blank space.
  • For example, assume the user will enter  * 3 + 4 5 rather than *3+45
  • Also, you can assume that the user will only enter integer values (no floating point values).
  • The output can be given as an integer value as well (see below example output).


Hints

  • It is recommend, though not required, that you make use of the following:
    • stringstreams (#include<sstream>)
    • The atoi function
    • An is_numeric function (write your own using ASCII!!)
  • If you are not familiar with the above, you will be expected to research them for this assignment

Example Output (User Input with Vary):


Welcome!


Please enter an equation in Polish Notation or "q" to quit: * 3 + 4 5
The answer is: 27

Please enter an equation in Polish Notation or "q" to quit: - * - 9 2 3 4
The answer is: 17

Please enter an equation in Polish Notation or "q" to quit: / * + 5 3 4 7
The answer is: 4

Please enter an equation in Polish Notation or "q" to quit: + 13 14
The answer is: 27


Please enter an equation in Polish Notation or "q" to quit: Q


Goodbye!


Grading Criteria:

  • No credit if you do not complete this assignment using pair programming and following the rules specified in the pair programming contract.
  • No credit if you alter the class definitions of the Queue, or Stack or the Node Struct.
  • No credit if you add additional Queue or Stack functions aside from what is provided in the header files for this lab.
  • 60 points for a fully functional Stack and Queue, with complete test files.
  • 40 points for a fully functional Polish Notation Calculator.


What to Submit:

  • Submit your Queue.h, QueueTest.cpp, Stack.h, StackTest.cpp, and Polish.cpp to Canvas (one partner).
  • Submit your pair programming contract and worksheet to Canvas (both partners).
  • Please do not submit as a zip file - 5 point penalty for zip submissions.