========================================

StackCalculator.hpp

#pragma once #include

struct Operand { float number; Operand* next; };

class StackCalculator { private: Operand* stackHead; // pointer to the top of the stack

public: StackCalculator(); ~StackCalculator(); bool isEmpty(); void push(float num); void pop(); Operand* peek(); Operand* getStackHead() { return stackHead; } bool evaluate(std::string* s, int size); };

=====================================

StackCalculator.cpp

#include #include "StackCalculator.hpp"

using namespace std; /* * Purpose: Determine whether some user input string is a * valid floating point number * @param none * @return true if the string s is a number */ bool isNumber(string s) { if(s.size() == 1 && s == "-") return false;

else if(s.size() > 1 && s[0] == '-') s = s.substr(1);

bool point = false; for(int i = 0; i

return true; }

StackCalculator::StackCalculator() { //TODO: }

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

bool StackCalculator::isEmpty() { //TODO: }

void StackCalculator::push(float number) { //TODO: }

void StackCalculator::pop() { //TODO: }

Operand* StackCalculator::peek() { //TODO: return nullptr;// remove this line if you want }

bool StackCalculator:: evaluate(string* s, int size) { /*TODO: 1.scan the array from the end 2.Use isNumber function to check if the input is an operand 3.push all operands to the stack 4.If operator take two element of from the stack, compute and put the result back in stack 5.Handle the boundery cases as required. 6.Read the writeup for more details */

return true; }

===========================

driver.cpp

#include #include #include #include "StackCalculator.hpp"

using namespace std;

int main() { // stack to hold the operands StackCalculator stack;

int numElement = 0; string* inparr = new string[50];

// enter a number string number; cout

while(true) { cout "; getline(cin, number);

/* TODO 1. Read input (operators and operands) until you encounter a "=" 2. store them in inparr */

}

/* TODO - If the inparr is empty then print "No operands: Nothing to evaluate" else call the evaluate function */

/* TODO - Validate the expression 1. If valid then print the result cout

JobQueueDriver.cpp

/****************************************************************/ /* Job Queue Driver File */ /****************************************************************/ /* TODO: Implement menu options as described in the writeup */ /****************************************************************/

#include "JobQueue.hpp" #include // you may include more libraries as needed

using namespace std;

/* * Purpose: displays a menu with options * @param none * @return none */ void menu() { cout

JobQueue.hpp

/****************************************************************/ /* JobQueue Class */ /****************************************************************/ /* LEAVE THIS FILE AS IS! DO NOT MODIFY ANYTHING! =] */ /****************************************************************/ #pragma once

#include

const int SIZE = 20;

class JobQueue { private: int queueFront; //the index in queue[] that will be dequeued next int queueEnd; //the index in queue[] that keeps track of the next available empty space int counter; // number of elements in the queue currently std::string queue[SIZE];

public: JobQueue(); bool isEmpty(); bool isFull(); void enqueue(std::string job); void dequeue(); std::string peek(); int queueSize(); int getQueueFront() { return queueFront; } int getQueueEnd() { return queueEnd; } std::string* getQueue() { return queue; }

}; ===============================

Please complete TODO and show

StackCalculator.cpp

driver.cpp

JobQueue.cpp

JobQueueDriver.cpp

Assignment 5 - Stacks and Queues OBJECTIVES 1. Create, add to, delete from, and work with a stack implemented as a linked list 2. Create, add to, delete from, and work with a queue implemented as an array Overview Stacks and Queues are both data structures that can be implemented using either an array or a linked list. You will gain practice with each of these in the following two mini-projects. The first is to build a simple calculator using a linked list stack and the second is to simulate a job scheduling system using a circular array based queue. Stack calculator In this assignment we will implement a linked list based stack. We will use this stack implementation to evaluate prefix expressions. In the following section we will discuss what is a prefix expression and how we can evaluate them using stack. Your task will be to implement the logic into c++ code. We will consider only two binary operators "+" and "*" for prefix notations. Prefix Notation In general the way we express a binary operator in mathematical expression is infix. For example 4 + 3". In this expression the order is " operator ". The prefix notation for the will be + 4 3". The order here is "operator ". A visual representation of the operation is given here. Note though 4 + 3" and " + 4 3" are different strings but both of them should be evaluated to 7. operator Even if the computation tree is deeper we can follow the same paradigm to represent the operand2 expression. For example consider the expression- operand1 4 ( 3 "(4+3) + (2+5)". The computation tree of the same is given below. For each subexpression we will follow the same procedure operator ". So the subexpression 4 + 3 will be + 4 3 and 2 + 5" will be + 2 5" . Now these two subexpressions " + 4 3 and + 2 5" are the operands for "*'. So the final expression become * +43 + 2 5". * +4 3 + 2 5 +43 +25 4 3 2 5 Again note the expression "* + 4 3 + 2 5" evaluates to be 49 which is the same as its infix counterpart (4+3) + (2+5)". Here is another example for ( 6 + 21 ) + 3 + + 6 21 3 3 +6 21 3 6 21 How to Evaluate To evaluate a prefix expression we will use stack. We will parse the expression from the back. If we encounter a number we will push it to the stack. If we encounter an operator ("+" or **") we will take two elements from the stack top and perform the operation. We will push back the result again in the stack. To determine whether an element is operator or operand we will use isNumber function. Note this function is provided in the cpp file so you do not need to implement is Number function. Consider the example * + 4 3 + 2 5. Our code will accept the notation as an array of strings- + 4 3 + 2 5 Index:0 1 2 3 4 5 6 Instruction Stack Index: 0 4 2 4 3 3 5 2 + + 2 6 5 1 5 Push 5 Index: 0 4 4 2. 4 3 3 3 3 5 2 6 5 * + + 2 1 5 Push 2 Index: 0 # 2 4 3 3 4 3 3 5 2 6 5 + + 7 1 Pop two elements. Perform the operation '+'. Push the result. Index: 0 1 4 2 4 3 3 5 2 6 5 + + 1 7 Pop two elements. Perform the operation '+'. Push the result. Index: 0 4 2 4 3 3 5 2 6 5 + + 3 1 7 Push 3 Index: 0 4 1 + 2 4 3 3 5 2 6 5 * + 2 + 4 3 7 Push 4 Index: 0 3 2. 4 3 3 4 + 5 2 2 6 5 + 7 7 Pop two elements. Perform the operation +. Push the result. Index: 0 3 2. 4 3 3 4 + 5 2 5 2 6 5 + + 49 Pop two elements. Perform the operation *. Push the result. Class Specifications The node structure for the linked list is defined in StackCalculator hpp. struct Operand { float number; // the number to store Operand* next; // the pointer to the next node }; The StackCalculator class definition is provided in the file StackCalculator.hpp in Canvas. Do not modify this file or your code won't work on Coderunner! Fill in the file StackCalculator.cpp according to the following specifications. Operand* stackHead; Points to the top of the stack StackCalculator(); Class constructor; set the stackHead pointer to NULL -StackCalculator(); Destroy the stack. Take special care not to leave any memory leaks. StackCalculator(); Class constructor, set the stackHead pointer to NULL -StackCalculator(); Destroy the stack. Take special care not to leave any memory leaks. bool isEmpty(); Returns true if the stack is empty void push(float num); Push a float element to the stack void pop(); Pop the element out of the stack. Do not leave any memory leak. Print "Stack empty, cannot pop a job." if the stack is empty. Operand* peek(); Returns the top of the stack. Print "Stack empty, cannot peek." if the stack is empty. Operand* getStackHead() { return stackHead; } Returns the stackHead. This is already implemented. bool evaluate(std::string* s, int size); This function will accept an array of strings and the length of the array. The array represents the prefix expression. This function will evaluate the expression and will store the ultimate result in the stack. If the function encounters any other operator than "+" or "*" it should print "err: invalid operation" and return false. If the array does not have the correct number of operands it should print "err: not enough operands" and return false. If everything goes well it will return true. Driver code The driver code should start with printing "Enter the operators and operands ('+', '*') in a prefix format" * It will keep taking input from the user and will store the input to a string array. Print to each line of the console while accepting input. Refer to the example run. If user inputs "=" it will stop accepting the input and will call the evaluate function with the string array. If the expression is not valid it should print "Invalid expression" For valid expression it should print the result with "Results" Free any unused memory Example Runs: 1. Enter the operators and operands ('+', '*') in a prefix format #> * #> + #> 4 #> 3 #> + #> 2 #> 5 #> = Result: 49 2. Enter the operators and operands ('+', '*') in a prefix format #> + #> + #> 14 #> 12 #> 3 #> = Result= 29 3. Enter the operators and operands ('+', '*') in a prefix format #> #> + #> 4 #> 3 #> = err: not enough operands #> + #> 4 #> 3 #> 2 #> 5 #> = Invalid expression JobQueue Class **Beware of edge cases that arise from the array being circular** In this class you will build a queue using the circular array implementation. Implement the methods of JobQueue according to the following specifications. std::string queue[SIZE] A circular queue of strings in the form of an array. SIZE is initialized to a default value of 20 in JobQueue.hpp int queue Front Index in the array that keeps track of the index at which dequeue will happen next int queue End Index in the array that keeps track of the first available empty space (in case the queue std::string queue[SIZE] A circular queue of strings in the form of an array. SIZE is initialized to a default value of 20 in JobQueue.hpp int queue Front Index in the array that keeps track of the index at which dequeue will happen next int queue End Index in the array that keeps track of the first available empty space (in case the queue is full, queue End points to queue Front). JobQueue() Constructor--Set queueFront, queueEnd and counter to 0 bool isEmpty() Return true if the queue is empty, false otherwise bool isFull() Return true if the queue is full, false otherwise void enqueue(std::string job) If the queue is not full, then add the job to the end of the queue and modify queue Front and/or queueEnd if appropriate, else print Queue full, cannot add new job" void dequeue() Remove the first job from the queue if the queue is not empty and modify queue Front and/or queueEnd if appropriate. Otherwise print "Queue empty, cannot dequeue a job" int queue Size() * Return the number of jobs in the queue. std::string peek() If the queue is empty then print Queue empty, cannot peek and return an empty string Otherwise, return the first job in the queue. JobQueue main driver file Your program will start by displaying a menu by calling the menu() function which is included in the provided skeleton code. The user will select an option from the menu to decide upon what the program will do, after which the menu will be displayed again. Below are the specifics of the menu (Tips: use getline for all inputs, and you are required to create and write the main function.) Option 1: Add jobs into the queue - This is an enqueue operation This option prompts the user to enter the number of jobs being created using the below print statement cout ":" ; Below is a sample output Choose an option: 1. Add jobs into the queue 2. Dispatch jobs from the queue 3. Return the queue size and exit 1 Enter the number of jobs to be created: 3 job1: Sort job2: 3 Enter the number of jobs to be created: 3 job1: Sort job2: Save job3: Load Choose an option: 1. Add jobs into the queue 2. Dispatch jobs from the queue 3. Return the queue size and exit 2 Enter the number of jobs to be dispatched: 2. Dispatched: Sort Dispatched: Save *. Choose an option: 1. Add jobs into the queue 2. Dispatch jobs from the queue 3. Return the queue size and exit * 3 Number of jobs in the queue: 1