class ListNode { private: int data; ListNode* prev; ListNode* next; public: List
ID: 3707404 • Letter: C
Question
class ListNode
{
private:
int data;
ListNode* prev;
ListNode* next;
public:
ListNode() { prev = next = NULL; }
ListNode(int d, ListNode* p, ListNode* n) { data = d; prev = p; next = n; }
friend class List;
};
class List
{
private:
ListNode* list_head;
ListNode* list_tail;
public:
List() { list_head = list_tail = NULL; }
~List() { clear(); }
bool isEmpty() { return list_head == NULL; }
bool contains(int value);
void addToHead(int value);
void addToTail(int value);
int head() { return list_head->data; }
int tail() { return list_tail->data; }
int removeHead();
int removeTail();
void clear();
};
bool List::contains(int value)
{
ListNode *temp = list_head;
while (temp != NULL && temp->data != value)
temp = temp->next;
return temp != NULL;
}
void List::addToHead(int value)
{
if (isEmpty())
{
list_head = list_tail = new ListNode(value, NULL, NULL);
}
else
{
list_head = new ListNode(value, NULL, list_head);
list_head->next->prev = list_head;
}
}
void List::addToTail(int value)
{
if (isEmpty())
{
list_head = list_tail = new ListNode(value, NULL, NULL);
}
else
{
list_tail = new ListNode(value, list_tail, NULL);
list_tail->prev->next = list_tail;
}
}
int List::removeHead()
{
int value = list_head->data;
if (list_head == list_tail)
{
delete list_tail;
list_head = list_tail = NULL;
}
else
{
list_head = list_head->next;
delete list_head->prev;
list_head->prev = NULL;
}
return value;
}
int List::removeTail()
{
int value = list_head->data;
if (list_head == list_tail)
{
delete list_tail;
list_head = list_tail = NULL;
}
else
{
list_tail = list_tail->prev;
delete list_tail->next;
list_tail->next = NULL;
}
return value;
}
void List::clear()
{
while (!isEmpty())
removeTail();
}
class Stack
{
private:
List* list;
public:
Stack() { list = new List(); }
~Stack() { delete list; }
bool isEmpty() { return list->isEmpty(); }
void clear() { list->clear(); }
void push(int data) { list->addToHead(data); }
int pop() { return list->removeHead(); }
int top() { return list->head(); }
};
In computer science, a priority queue is an ADT which is similar to a regular queue; however, each entry in the queue is also has a "priority" associated with it. If two elements have the same priority, they are served according to their order in the queue PriorityQueue *pqnew PriorityQueue (); pq-enqueue("a", 30); pq->enqueue ("b", 10); pq->enqueue ("c", 20); pq->enqueue ("d", 10); cout dequeue() ?? pa-?dequeue() ? pq-?dequeue(); The string "acbd" is outputted is the "a" has the highest priority, followed by "c", followed by "b", and then followed by "d'" Program 1. (50 points) Reverse Polish Notation Calculator Writc a program (pn.cpp) that docs thc following Leverages the provided Stack class (in stack.h) accomplish the other goals of the assignment Accepts a valid infix expression, converts it into RPN, and then evaluates the expression If an invalid infix expression is provided, write an appropriate message to standard out and end the program Print the convert postfix expression before evaluation, as well as its evaluated result The major pieces of the program are broken into reusable functions Infix expressions will contain the following operators: ()* /+ When reading an infix expression, be sure to consider order of operators when converting to postfix You may add new functions to the List and Stack classes in stack.h. if you feel they are necessary, but do not modify any existing functions If you are having issues parsing input, you can create arrays with predetermined input to test the conversion process -Explanation / Answer
Conversion of Infix to Postfix in C++ language.Hope it helps.
#include<stack>
int length(char input[]){
int i=0;
while(input[i])
i++;
return i;
}
//Function to return priority of operators
int priority(char c)
{
if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
// returns the value when a specific operator operates on two operands
int evaluate(int op1, int op2, char operate) {
switch (operate) {
case '*': return op2 * op1;
case '/': return op2 / op1;
case '+': return op2 + op1;
case '-': return op2 - op1;
default : return 0;
}
}
// convert infix expression to postfix expression
void infixToPostfix(char *input)
{
stack<char> s;
int len = length(input),index=0;
char output[1000];
for(int i = 0; i < len; i++)
{
if((input[i] >= '0' && input[i] <= '9')) {
output[index++] = input[i];
} else if(input[i] == '(') {
s.push('(');
} else if(input[i] == ')')
{
// If the scanned character is an ‘)’, pop and to output string from the stack until
an ‘(‘ is encountered.
while(!s.empty() && s.top() != '(')
{
char c = s.top();
s.pop();
output[index++] = c;
}
if(s.top() == '(')
{
char c = s.top();
s.pop();
}
} else{
while(!s.empty() && priority(input[i]) <= priority(s.top()))
{
char c = s.top();
s.pop();
output[index++]= c;
}
s.push(input[i]);
}
}
//Pop all the remaining elements from the stack
while(!s.empty())
{
char c = s.top();
s.pop();
output[index++] = c;
}
output[index] = '';
cout << output << " ";
//copying to change input expression from calling function evaluatePostfix
int i=0;
while(i < length(output)){
input[i] = output[i];
i++;
}
input[i] = '';
}
void evalPostfix(char postfix[]) {
stack<int> s;
int i = 0;
char ch;
int val;
int len = length(postfix);
while (i < len) {
ch = postfix[i];
if (isdigit(ch)) {
s.push(ch-'0');
}
else {
int op1 = s.top();
s.pop();
int op2 = s.top();
s.pop();
val = evaluate(op1, op2, ch);
s.push(val);
}
i++;
}
cout << val;
}
void evaluatePostfix(char exp[]) {
infixToPostfix(exp);
evalPostfix(exp);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.