(C++) Implement the linked list and test the functionality of it using tests. Wr
ID: 3732320 • Letter: #
Question
(C++) Implement the linked list and test the functionality of it using tests.
Write your Test first and then implement your functions.
EXPRESSIONSTREAM is given in the end.
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
QUEUE.H
#ifndef LAB05_INC_QUEUE_H
#define LAB05_INC_QUEUE_H
#include "linked_list.h"
namespace lab5 {
class queue {
private:
linked_list storage_structure;
public:
queue();
queue(std::string &data);
queue(const queue &original);
virtual ~queue();
queue &operator=(const queue &RHS);
bool isEmpty() const;
unsigned queueSize() const;
std::string top() const;
void enqueue(const std::string &data);
void dequeue();
friend std::ostream& operator<<(std::ostream& stream, queue& RHS);
friend std::istream& operator>>(std::istream& stream, queue& RHS);
};
}
#endif
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
QUEUE.CPP
namespace lab5{
queue::queue() { }
queue::queue(std::string &data) { }
queue::queue(const queue &original) { }
queue::~queue() { }
queue &queue::operator=(const queue &RHS) { }
bool queue::isEmpty() const { return false; }
unsigned queue::queueSize() const { return 0; }
std::string queue::top() const { }
void queue::enqueue(const std::string &data) { }
void queue::dequeue() { }
std::ostream& operator<<(std::ostream &stream, queue &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, queue &RHS) { return stream; }
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
STACK.H
#ifndef LAB05_INC_STACK_H
#define LAB05_INC_STACK_H
#include "linked_list.h"
namespace lab5 {
class stack {
private:
linked_list storage_structure;
public:
stack();
stack(std::string &data);
stack(const stack &original);
virtual ~stack();
stack &operator=(const stack &RHS);
bool isEmpty() const;
unsigned queueSize() const;
std::string top() const;
void push(const std::string &data);
void pop();
friend std::ostream& operator<<(std::ostream& stream, stack& RHS);
friend std::istream& operator>>(std::istream& stream, stack& RHS);
};
}
#endif
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
STACK.CPP
#include "stack.h"
namespace lab5{
stack::stack() { }
stack::stack(std::string &data) { }
stack::stack(const stack &original) { }
stack::~stack() { }
stack &stack::operator=(const stack &RHS) { }
bool stack::isEmpty() const { return false; }
unsigned stack::queueSize() const { return 0; }
std::string stack::top() const { }
void stack::push(const std::string &data) { }
void stack::pop() { }
std::ostream& operator<<(std::ostream &stream, stack &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, stack &RHS) { return stream; }
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
LINKED_LIST.H
#ifndef LAB05_INC_LINKED_LIST_H
#define LAB05_INC_LINKED_LIST_H
#include "node.h"
#include
namespace lab5 {
class linked_list {
node *head, *tail;
public:
linked_list();
explicit linked_list(std::string &data);
linked_list(const linked_list &original);
virtual ~linked_list();
linked_list &operator=(const linked_list &RHS);
friend std::ostream& operator<<(std::ostream& stream, linked_list& RHS);
friend std::istream& operator>>(std::istream& stream, linked_list& RHS);
bool isEmpty() const;
unsigned listSize() const;
std::string get_value_at(unsigned location);
void insert(const std::string input, unsigned location = 0 );
void append(const std::string input);
void remove(unsigned location = 0);
void sort();
};
}
#endif
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
LINKED_LIST.CPP
#include
namespace lab5 {
linked_list::linked_list() { }
linked_list::linked_list(std::string &data) { }
linked_list::linked_list(const linked_list &original) { }
linked_list::~linked_list() { }
linked_list &lab5::linked_list::operator=(const linked_list &RHS) { }
bool linked_list::isEmpty() const { return false; }
unsigned linked_list::listSize() const { return 0; } //Note that you do **not** have a size variable in your linked list. You *MUST* count the nodes.
void linked_list::insert(const std::string input, unsigned int location) { //create a node from the input string and put it into the linked list at the given location node *prev; node *current; node *temp = new node (input); current = head; }
void linked_list::append(const std::string input) { } //create a new node and put it at the end/tail of the linked list
void linked_list::remove(unsigned location) { } //Remove the node at the given location
std::ostream& operator<<(std::ostream &stream, linked_list &RHS) { return stream; }
std::istream& operator>>(std::istream &stream, linked_list &RHS) { return stream; }
void linked_list::sort() { } //Perform selection sort on the linked list
std::string linked_list::get_value_at(unsigned location) { }
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
NODE.H
#ifndef LAB5_NODE_H
#define LIB_LAB5_NODE_H
#include
namespace lab5 {
class node {
public:
node *next;
std::string data;
explicit node(const std::string &data) : data(data), next(nullptr){};
};
}
#endif
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
FANCYCALCULATOR.H
#ifndef LAB5_CALCULATOR_H
#define LAB5_CALCULATOR_H
#include "stack.h"
#include "queue.h"
#include "expressionstream.h"
#include
namespace lab5{
class calculator{
lab5::queue infix_expression;
lab5::queue postfix_expression;
void parse_to_infix(std::string &input_expression); //PRIVATE function used for converting input string into infix notation
void convert_to_postfix(lab5::queue infix_expression); //PRIVATE function used for converting infix FIFO to postfix
public:
calculator(); //Default constructor
calculator(std::string &input_expression); // Constructor that converts input_expression to infix and postfix upon creation
friend std::istream& operator>>(std::istream& stream, calculator& RHS); //Store the infix and postfix expression in calculator
int calculate(); //Return the calculation of the postfix expression
friend std::ostream& operator<<(std::ostream& stream, calculator& RHS); //Stream out overload. Should return in the format "Infix: #,#,#,# Postfix: #,#,#,#"
};
}
#endif
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
FANCYCALCULATOR.CPP
#include "fancy_calculator.h"
#include "stack.h"
#include "queue.h"
namespace lab5{
void calculator::parse_to_infix(std::string &input_expression) { }
void calculator::convert_to_postfix(lab5::queue infix_expression) { }
calculator::calculator() { }
calculator::calculator(std::string &input_expression) { }
std::istream &operator>>(std::istream &stream, calculator &RHS) { return stream; }
int calculator::calculate() { return 0; }
std::ostream &operator<<(std::ostream &stream, calculator &RHS) { return stream; }
bool is_number(std::string input_string);
bool is_operator(std::string input_string);
int get_number(std::string input_string);
std::string get_operator(std::string input_string);
int operator_priority(std::string operator_in);
}
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
EXPRESSIONSTREAM.CPP //THIS IS ALREADY DONE.
#include "expressionstream.h"
namespace lab1 {
bool is_number(char c);
expressionstream::expressionstream(const std::string &string_in) : buffer(string_in) {
current_pos = buffer.begin();
next_position = current_pos;
skip_white_space();
}
void expressionstream::skip_white_space() {
while (*current_pos == ' ' && current_pos != buffer.end()) ++current_pos;
while (*next_position == ' ' && next_position != buffer.end()) ++next_position;
}
std::string expressionstream::get_number() {
bool is_negative = false;
std::string::iterator number_start;
//check if the number is negative, this is used to skip any white space after '-'
if (*current_pos == '-') is_negative = true;
//find beginning of number
number_start = current_pos;
while (number_start != buffer.end() && !is_number(*number_start))++number_start;
//find ending of number
next_position = number_start;
while (next_position != buffer.end() && is_number(*next_position))++next_position;
//create and return number using position iterators
return (is_negative) ? '-' + std::string(number_start, next_position) : std::string(number_start,
next_position);
}
bool expressionstream::is_negative() {
//after finding a '-' check if it is minus or negative by checking previous character
//create an iterator to the previous character
std::string::iterator negative_check = next_position - 1;
//move backward until reach non-whitespace
while (negative_check != buffer.begin() && *negative_check == ' ') --negative_check;
//if the previous character is not a number and not a close parenthesis the number is negative
//EXAMPLE: the following should get negatives on the 13's but not the 5's : "-13-(-13-(5--13)-5)--13"
return (!is_number(*negative_check) && *negative_check != ')');
}
std::string expressionstream::get_next_token() {
//move the current_position iterator forward then get the "current" token
current_pos = next_position;
return get_current_token();
}
std::string expressionstream::get_current_token() {
skip_white_space();
//check for end of buffer
if (current_pos == buffer.end()) return "";
//reset next position each time current token is called
//this should stop the 'next_position' from drifting on
//consecutive "get_current_token()" calls
next_position = current_pos;
if (next_token_is_int())
return get_number();
//if token is not a number then it is one character long
//setting the 'next_position' iterator forward one will
//return one character
++next_position;
return std::string(current_pos, next_position);
}
bool expressionstream::next_token_is_int() {
skip_white_space();
if (is_number(*next_position))
return true;
if (*next_position != '-')
return false;
return is_negative();
}
bool expressionstream::next_token_is_op() {
skip_white_space();
if (next_token_is_int()) return false;
return (*next_position == '+' || *next_position == '-' || *next_position == '*' || *next_position == '/');
}
bool expressionstream::next_token_is_paren_open() {
skip_white_space();
return *next_position == '(';
}
bool expressionstream::next_token_is_paren_close() {
skip_white_space();
return *next_position == ')';
}
bool is_number(char c) {
return (c >= '0' && c <= '9');
}
}
Explanation / Answer
/* Program to demonstrate Stack using inked list with Test Functionality*/
#include <iostream>
#include "stack.h"
using std::cout;
using std::ends;
/* FUNCTION: To Validate whether if the stack is empty or has at least one element */
template <class T1>
bool stack<T1>::empty() { return (root_node == nullptr); }
/* FUNCTION: Returns current size of the stack */
template <class T1>
int stack<T1>::size() { return elements; }
/* FUNCTION: Pushing nodes to the stack with one argument which is the data to be inserted */
template <class T1>
void stack<T>::push(T1 data) {
//Activity to check if the stack is empty or not.
//Root element will be removed from the start (First in, Last out)
if ( empty() ) {
root_node2 = new node;
root_node2->node_data2 = data;
root_node2->next2 = nullptr;
elements++;
}
//Activity to preform if stack is not empty.
//Elements added to the stack with dynamic allocation.
else {
node *new_node2 = new node;
*new_node2 = *root_node2;
root_node2->next2 = new_node;
root_node2->node_data2 = data;
elements++;
}
}
/* FUNCTION: Elements removed from the top of the stack */
template <class T>
void stack<T>::pop() {
if (size() > 1) {
node *temp_node2 = new node;
temp_node2 = root_node2->next;
root_node2 = temp_node2;
elements--;
}
else if (size() == 1) {
root_node = nullptr;
elements--;
}
else {cout << " Operation pop() failed: Stack is Null!" << endl;}
}
/* FUNCTION: Extracts the element at the top of the stack */
template <class T>
T stack<T>::top() {
if (!empty()) {return root_node->node_data;}
else {cout << " Operation top() failed: Stack is empty!" << endl; return -1;}
}
/* FUNCTION: Prints the stack contents */
template <class T>
void stack<T>::print() {
int index = size();
for (int i = 1; i < index; i++) {
cout << "Element " << i << ": " << " " << top() << endl;
pop();
}
}
/* Program to check demonstrate the usage of queue using linked list with Test functionality*/
#include "queue.h"
#include<iostream.h>
using namespace std;
class person
{
friend class Queue;
public:
int prior;
string name;
};
class Queue
{
friend class person;
private:
//Structure for my linked list.
typedef struct node {
person data2;
struct node *next;
}Node, *NodePtr1;
Node *head1, *tail1;
public:
//Prototype Functions
Queue(void); //Initializer function
bool empty1(void); //Test if empty
int size1(void); //Return size
void enqueue2(Person *); //Insert Node
void dequeue1(void); //Remove Node
Person* front1(void); //Access Next Node
Person* back1(void); //Access last node
};
PQueue::Queue()
{
head = NULL;
tail = NULL;
}
bool PQueue::empty(){
return (head1 == NULL);
}
void PQueue::enqueue(Person *myPers){
NodePtr np1 = (NodePtr) malloc(sizeof(Node));
np1->data = *myPer;
np1->next = NULL;
if(empty())
{
cout << "Process of creating the first node, of the linked list" <<endl;
head = np1;
tail = np1;
}
else { //Queue has more the one node
Node* temp1 = head1;
if(np->data.priority > temp->data.priority) //If the priority is greater then the rest.
{
head1 = temp1; //Saving my head pointer
head1->data = np1->data; //Adding new Data to the head pointer
head1->next = temp1; //Adding the rest of the linked list back into head.
cout << "Process of creating the first node again, having to reassign." <<endl;
}
else{
//Searching where to place the node.
while(temp1->data.priority > np1->data.priority) //Searching if the next priority is higher then the passed.
{
cout << "Inside the while loop: " << np->data.priority << " versus "<<temp->data.priority <<endl;
if(temp1->next == NULL)
break;
temp1 = temp1->next;
}
if(temp1->next == NULL && np1->data.priority < temp1->data.priority) //Inserting at the end.
{
cout << "Process of creating the last node" <<endl;
tail1->next = np1;
cout << "Passing the function of creating the last node" <<endl;
}
else //Adding to the middle of the function.
{
cout << "Inserting in the middle of the queue" <<endl;
np1->next = temp1->next;
temp1->next = np1;
}
}
}
}
void PQueue::delqueue(){
if(empty()){
cout << " Process to remove from an empty list." << endl;
exit(1);
}
Person hold1 = head1->data;
NodePtr temp1 = head1;
head1=head1->next;
if (head1 == NULL) tail = NULL;
free(temp1);
}
Person* PQueue::Front(){
//Person &temp1 = head1->next->data;
//Person &temp1 = head1->data;
Person &temp1 = head1->data;
return &temp1;
}
Person* PQueue::back(){
if(empty()){
cout << " No entries exists in the list." << endl;
exit(1);
}
Person &temp1 = tail1->data;
return &temp1;
}
int main() {
cout << "Starting main" << endl;
PQueue que1; //Queue Creation.
cout << "Queue has been created" << endl;
Person tempPerson1;
ifstream inFile;
inFile.open("/tmp/temp");
cout << "going into while loop" << endl;
while (inFile >> tempPerson.priority >> tempPerson.name1){
cout << "The priority will be " << tempPerson.prior << " the name is " << tempPerson.name1 <<endl;
queue1.enqueue(&tempPer);
}
//Testing Section, trying to get .front and .back to work.
Person *testPers;
testPers = que1.front();
cout << "The TEST priority is " << testPerson->priority << " the TEST name is " << testPerson->name <<endl;
/**
Person *tailPerson;
testPerson = queue1.back();
cout << "The TEST priority is " << tailPerson->priority << " the TEST name is " << tailPerson->name <<endl;
**/
que1.delqueue();
que1.delqueue();
que1.delqueue();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.