(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 "\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');

}

}