class ListNode { private: int data; ListNode* prev; ListNode* next; public: List
ID: 3708168 • 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(); }
};
Program 1. Reverse Polish Notation Calculator Write a program (rpn.cpp) that does the following: - III 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 cxpressions 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 processExplanation / Answer
#include <iostream>
#include <stack>
#include <string>
#include <sstream> //class called istringstream
#include<iomanip>
using namespace std;
class LinkedList
{
public:
double data;
LinkedList *top;
LinkedList *ptr;
int count;
LinkedList()
{
top = NULL;
ptr = NULL;
count = 0;
}
int size() { return count;}
void push(double val)
{
LinkedList *next = new LinkedList;
next -> data = val;
next -> ptr = top;
top = next;
}
double pop()
{
LinkedList *next = top -> ptr;
double ret = top -> data;
delete top;
top = next;
return ret;
}
void print()
{
LinkedList *node = NULL;
cout << "= " << data << endl << ">>";
}
};
//Function prototype for isOperator
bool isOperator(const string& input);
//Function prototype for performOperation
int performOperation(const string& input, LinkedList& calcStack);
int main()
{
//Linked list declaration
LinkedList calcStack;
//Variable declaration
//stack<double> calcStack; //Declare stack<double> class
string input; //Declare a string named input
double num;
cout << "RPN Calculator: " << endl;
//Prompt the user to input their expression to be calculated
cout << "Input ";
//Declare a double named num
//Terminate program when 0 is entered by user
while(input != "0 ")
{
// Input from user
cin >> input;
/*Use istringstream function to read input where the
operators and operands are separated by a single space*/
if(istringstream(input) >> num)
{
//use push function
calcStack.push(num);
}
// check for operator, Call function isOperator
else if(isOperator(input))
{
//Call perforOperation function
performOperation(input, calcStack);
}
//terminates the expression with an equals sign
else if(input == "=")
{
//Error checking for too many operands by checking calcStack.size
if (calcStack.size() != 1)
{
cout << "Error: too many operands" << endl;
calcStack.print();
system("pause");
return 1;
}
else
{
/*Output the result- calcStack.top returns a
reference to the top element in the stack*/
//cout << "Output: " << data << endl;
//<< calcStack.top();
/*calcStack.pop() Removes the element on top
of the stack, effectively reducing its size by one.*/
calcStack.pop();
cout << endl << endl;
}
}
}
}
//Function definition for isOperator
bool isOperator(const string& input)
{
//Declare a static const string and initlialize te the operators
static const string operators = "-+*/";
//Error check for right size to be an operator.
if (input.length() == 1)
{
// look in the operator string for the first character in input
return operators.find_first_of(input[0]) != string::npos;
}
else
{
return false;
}
}
//Function defition for performOperation
int performOperation(const string& input, LinkedList& calcStack)
{
double firstOperand = 0; //Declare double for firstOperand
double secondOperand = 0; //Declare double for secondOperand
double result = 0; //Declare double for result
/*
//Error chceck for too many operators, if too many operators, exit program
if( calcStack.size() < 2 )
{
cout << "Error: too many operators" << endl;
system("pause");
exit(0);
}
*/
/*Assign secondOperand to calcStack.top returning a reference to the top element in the stack*/
//secondOperand = calcStack.top();
/*calcStack.pop() Removes the element on top of the stack, effectively reducing its size by one.*/
firstOperand = calcStack.pop();
//Assign firstOperant to calcStact.top()
//firstOperand = calcStack.top();
secondOperand = calcStack.pop();
//Switch statement for processing calculations
switch (input[0])
{//Begin switch
case '-': //Calculate subtraction, assign to result
//result = firstOperand - secondOperand;
calcStack.push(firstOperand - secondOperand);
break;
case '+': //Calculate addition, assign to result
calcStack.push(firstOperand + secondOperand);
break;
case '*': //Calculate multiplacation, assign to result
calcStack.push(firstOperand * secondOperand);
break;
case '/':
//Error checking for division by 0, if division by 0, exit program
if (secondOperand == 0)
{
cout << "Error: Division by 0. ";
calcStack.print();
system("pause");
exit(0);
}
//Calculate division, assign to result
calcStack.push(firstOperand / secondOperand);
break;
}//End switch
//calcStack.push inserts a new element at the top of the stack, above its current top element.
//calcStack.push(result);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.