Name: Homework 5 Stacks and Queues
SKU: 22468
Price: 24.99 USD
Availability: InStock

Description

5/5 – (2 votes)

Overview
1. Delete, re-adjust, and detect loop in a linked list. A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in first-out (FIFO) principle. Both of them can be implemented using Arrays or LinkedLists. In this assignment, stacks are implemented using Linked Lists and Queues are modified to a circular queues implemented using arrays.

Part 1 – Tv Buff Decoder

You are being asked to guess a movie or tv show name. But they are unfortunately encoded in a secret message!

Using the provided Stack class implementation, write the evaluate() function to print secret messages directly to the terminal. Secret messages are surrounded by parenthesis inside of otherwise readable strings (e.g. “This sentence contains a {terces} message”). The secret messages are just words in reverse, which we can use a stack to flip back into a readable format. The evaluate() method should decode secret messages by pushing an entire message string onto a stack, and then identifying secret messages between ‘{‘ and ‘}’ characters while popping each element off. You can assume there is only one potential secret message in any given string.

MessageDecoder Class

Implement the MessageDecoder class according to the following specifications:

Parser* head

Points to the top of the stack (first node in the Linked List). This is defined in the header file.

MessageDecoder()

Constructor–set the head pointer to NULL

~MessageDecoder()

Destructor–pop everything off the stack and set head to NULL

bool isEmpty()

Returns true if the stack is empty (i.e. head is NULL), otherwise false

void push(char ch)

Insert a new node with ch onto the top of the stack (beginning of linked list).

void pop()

If the stack is empty, print “Stack empty, cannot pop an item.” and return. Otherwise delete the top most item from the stack.

Parser* peek()

If the stack is empty, print “Stack empty, cannot peek.” and return NULL. Otherwise, return a pointer to the top of the stack.

Parser* getStackHead()

Already Implemented , no need to change.

void evaluate(std::string symbol)

Push all the characters into the stack

pop all the elements from the stack, while doing so, start storing the characters to a character array between “}” and “{”
if the parenthesis matched, then print the secret message.

else print ”No secret message”

MessageDecoder main driver file

Create a stack by instantiating an MessageDecoder object

Take input string from terminal

call evaluate function and pass the input string

Below are some sample outputs

Instructions for the `main_1.cpp` file

The driver code should start with printing `Enter the encoded sentence` with an endline.

Print `#>` and then accept the encoded string from the user.

If the string array is empty print `Nothing to evaluate`

Otherwise call the evaluate function with the string array.

Free any unused memory

Order of function implementation

1. push

2. pop

3. peek

4. evaluate

5. Destructor

6. main

Part 2 – TV Shows Queue

For this part, you will create an application that mimics a TV show queue. Specifically, the application allows users to both add (enqueue) and retrieve (dequeue) TV shows. The implementation will require creating a data buffer in the form of a queue. You will simulate this interaction using a circular queue.

EnqueueDequeue 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 EnqueueDequeue 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 EnqueueDequeue.hpp

int queueFront

Index in the array that keeps track of the front item

int queueEnd

Index in the array that keeps track of the first available empty space (in case the queue is full, queueEnd points to queueFront).

int counter

variable to keep track of the number of shows in the queue. Initialized to 0 in EnqueueDequeue.hpp.

EnqueueDequeue()

Constructor–Set queueFront and queueEnd to -1

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 show)

If the queue is not full, then add the show to the end of the queue and modify queueFront and/or queueEnd if appropriate, else print “Queue full, cannot add a new show”

void dequeue()

Remove the first show from the queue if the queue is not empty and modify queueFront and/or queueEnd if appropriate. Otherwise print “Queue empty, cannot dequeue show”

int queueSize()

Return the number of shows 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 show in the queue.

main_2.cpp 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 (Tip: use getline for all inputs)

Option 1: Enqueue (Add shows to the queue) – This is an enqueue operation

This option prompts the user to enter the number of shows being enqueued using the below print statement

Then prompt the user to enter each show using the below print statement

Add (enqueue) all the shows to the queue

Option 2: Dequeue (Remove shows from the queue) – This is a dequeue operation

This option prompts the user to enter the number of shows being removed using the below print statement

Remove (dequeue) shows from the queue. If the number of shows to be removed is greater than the total number of shows in the queue, then remove (dequeue) all the available shows in the queue and notify the user with a below statement:

This message should never be printed more than once.