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

Pair Programming Extra Credit Opportunity (5 pts)
  • Watch the video and answer the questions on this worksheet (only one time per quarter).
  • Both partners fill in, sign and date the pair programming contract (once per assignment).
  • Upload the two documents along with your assignment to Canvas under Lab 3.
  • Only ONE partner submits the lab assignment on Canvas. Please make sure both your names are on it.

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
        //postcondition: an empty queue

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

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

        /**manipulation procedures*/

        void dequeue();
        //removes an element from the front of the queue
        //precondition:size!=0
        //postcondition: an element has been removed from the front of the queue

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

        /**accessors*/

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

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

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

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

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


    private:
        struct Node
        {
            queuedata data;
            Node* link;
            Node(queuedata ndata) {

data = ndata;
link = NULL;

            }
        };

        Node* front;
        Node* back;
        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
        //postcondition: an empty stack

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


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

        /**manipulation procedures*/

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

        void push(stackdata data);
        //adds an element to the top of the stack
        //postcondition: 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
       //precondition: size != 0

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

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


       /**additional operations*/

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

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

           Node(stackdata ndata) {

data = ndata;
link = NULL;

            }      

        };

       Node* top;
       int size;

};


Part 2: Infix to Postfix Equation Converter (40 pts)

  • Using exactly one stack and one queue, create a program that converts equations in infix notation (entered by the user) to postfix notation (output by the program).
  • This program should be written in a file called Postfix.cpp
  • In Postfix notation (also known as reverse Polish notation), the mathematical operators are always placed on the right 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 or have a Polish or reverse Polish notation setting.
  • We are more familiar with infix notation (the way most calculators are programmed to read our input).
  • For example, check out the following equation, written in both infix and postfix notation:

            5 + 3 * 4 / 7 //infix notation

     5 3 4 * 7 / + //postfix notation

  • For more information on infix, prefix and postfix watch the video here
  • You can also convert equations 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  1 + 2 * 3 rather than 1+2*3
  • Also, you can assume that the user will only enter integer values (no floating point values).
  • You can also assume no parenthesis, and that you will only be given +, -, *, and / as operations.


Requirements

  • You must use your stack and queue classes written for part 1 above to complete this assignment
  • You must use exactly one stack and one queue to complete this assignment
  • You cannot add any functions or prototypes to your stack and queue class to complete this portion of the assignment or alter these classes in any way.
  • Your file must be named Postfix.cpp


Hints

  • It is recommend, though not required, that you make use of the following:
    • stringstreams (#include<sstream>)
    • An isNumeric 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 or "q" to quit: 5 + -7 * 8 - 10 * -2
The equation in postfix notation is: 5 -7 8 * + 10 -2 * -

Enter another equation or "q" to quit: -100 + 200 * 300
The equation in postfix notation is: -100 200 300 * +

Enter another equation or "q" to quit: 8 / 3 * -10 + 5
The equation in postfix notation is: 8 3 / -10 * 5 +

Enter another equation or "q" to quit: 4 * 6
The equation in postfix notation is: 4 6 *

Enter another equation or "q" to quit: q

Goodbye!


What to Submit:

  • Submit your Queue.h, QueueTest.cpp, Stack.h, StackTest.cpp, and Postfix.cpp to Canvas.
  • Please do not submit as a zip file - 5 point penalty for zip submissions.