(C++) Implement the linked list and test the functionality of it using tests.

Write your Test first and then implement your functions. Don't use Templates. Please state all steps clearly.

EXPRESSIONSTREAM is given in the end.

--------------------------------------

QUEUE.H

#ifndef QUEUE_H

#define QUEUE_H

#include "linked_list.h"

namespace lab0 {

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 lab0{

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 STACK_H

#define STACK_H

#include "linked_list.h"

namespace lab0 {

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 lab0{

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 LINKED_LIST_H

#define LINKED_LIST_H

#include "node.h"

#include

namespace lab0 {

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 lab0 {

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 &lab0::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 NODE_H

#define NODE_H

#include

namespace lab0 {

class node {

public:

node *next;

std::string data;

explicit node(const std::string &data) : data(data), next(nullptr){};

};

}

#endif

--------------------------------------

FANCYCALCULATOR.H

#ifndef CALCULATOR_H

#define CALCULATOR_H

#include "stack.h"

#include "queue.h"

#include "expressionstream.h"

#include

namespace lab0{

class calculator{

lab0::queue infix_expression;

lab0::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(lab0::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 lab0{

void calculator::parse_to_infix(std::string &input_expression) { }

void calculator::convert_to_postfix(lab0::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 "\0";

//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');

}

}