Implement a Deque (Double-Ended Queue) and use that data structure to write a cl

Question

Implement a Deque (Double-Ended Queue) and use that data structure to write a class that can convert between Postfix, Infix, and Prefix notation.

Using these functions:

std::string postfixToInfix(std::string inStr)

std::string postfixToPrefix(std::string inStr)

std::string infixToPostfix(std::string inStr)

std::string infixToPrefix(std::string inStr)

std::string prefixToInfix(std::string inStr)

std::string prefixToPostfix(std::string inStr)

You need to implement a fully functional deque using a doubly linked list. When writing the methods to convert between the notations, you can ONLY use your deque and strings for storing data in the algorithms. You may not use the any C++ Standard Library containers, such as the STL Deque, Stack, Queue, Vector, or List.

Example Output:

White space (one or more characters of space) separate all operand and

operators, while parentheses must have white space on the outside (between operators), and

inside parentheses white space is optional. Parentheses are only used in infix strings.

Parentheses must have operators between them, as all operations must be binary and not

implied.

Hints

It would be a good idea to decode the input string and place it into a deque to make it easier to read for the various methods

In the algorithm header, there is a method that can reverse strings.

When dealing with infix notations, remember that operator precedence is very important.

Remember, a deque can operate like a stack or a queue, queues and stacks can be considered specializations of a deque

You may not need to write a separate algorithm for all six methods. For example, when going from postfix to prefix, you can go from postfix to infix and infix to prefix if those methods are already implemented.

Please explain your code.

Explanation / Answer

#include <iostream>
using namespace std;

struct DQ_Node {
int value;
DQ_Node* nxt;
DQ_Node* prevs;
};

class deque {
private:

DQ_Node* headNode;
DQ_Node* tailNode;

public:
deque()
{
headNode = tailNode = NULL;
}

bool is_Empty()
{
if (headNode == NULL)
return true;
return false;
}
int size()
{
if (!is_Empty()) {
DQ_Node* temporary = headNode;
int length = 0;
while (temporary != NULL) {
length++;
temporary = temporary->nxt;
}
return length;
}
return 0;
}
void insert_first(int element)
{
DQ_Node* temporary = new DQ_Node[sizeof(DQ_Node)];
temporary->value = element;
if (headNode == NULL) {
headNode = tailNode = temporary;
temporary->nxt = temporary->prevs = NULL;
}
else {
headNode->prevs = temporary;
temporary->nxt = headNode;
temporary->prevs = NULL;
headNode = temporary;
}
}

void insert_last(int element)
{
DQ_Node* temporary = new DQ_Node[sizeof(DQ_Node)];
temporary->value = element;
if (headNode == NULL) {
headNode = tailNode = temporary;
temporary->nxt = temporary->prevs = NULL;
}
else {
tailNode->nxt = temporary;
temporary->nxt = NULL;
temporary->prevs = tailNode;
tailNode = temporary;
}
}
void remove_first()
{
if (!is_Empty()) {
DQ_Node* temporary = headNode;
headNode = headNode->nxt;
headNode->prevs = NULL;
free(temporary);
return;
}
cout << "List is Empty" << endl;
}
void remove_last()
{
if (!is_Empty()) {
DQ_Node* temporary = tailNode;
tailNode = tailNode->prevs;
tailNode->nxt = NULL;
free(temporary);
return;
}
cout << "List is Empty" << endl;
}
void display()
{
if (!is_Empty()) {
DQ_Node* temporary = headNode;
while (temporary != NULL) {
cout << temporary->value << " ";
temporary = temporary->nxt;
}
cout << endl;
return;
}
cout << "List is Empty" << endl;
}
};

class Stack : public deque {
public:
void push(int element)
{
insert_last(element);
}
void pop()
{
remove_last();
}
};
class Queue : public deque {
public:
void enqueue(int element)
{
insert_last(element);
}

void dequeue()
{
remove_first();
}
};

int main()
{
Stack stac;
stac.push(7);
stac.push(8);
cout << "Stack: ";
stac.display();
stac.pop();
cout << "Stack: ";
stac.display();
Queue Q;
Q.enqueue(12);
Q.enqueue(13);
cout << "Queue: ";
Q.display();
Q.dequeue();
cout << "Queue: ";
Q.display();

cout << "Size of Stack is " << stac.size() << endl;
cout << "Size of Queue is " << Q.size() << endl;
return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.