Implement the stack and the queue using a linked list. Use the given Stack and Q
ID: 3675057 • Letter: I
Question
Implement the stack and the queue using a linked list. Use the given Stack and Queue class definitions. You will need to write the Stack.cpp, Queue.cpp and your client code. Once you have working Stack.cpp and Queue.cpp files, write a program to evaluate Reverse Polish Notation (RPN) expressions. A RPN expression is a post-fixed expression. This program should allow the user to insert a RPN expression on a queue, print the expression, and evaluate the expression. Let the program be menu driven, using the following menu. Enter an expression Evaluate an expression Print all expression that have not been evaluated Exit Enter an expression This option will allow the user to enter a RPN expression. The expression will be added to a queue. Evaluate an expression This option will allow the RPN expression that is at the front of the queue to be removed from the queue and evaluated. The expression along with the resulting solution will be printed. Print all expressions that have not been evaluated This option will print all of the expressions that are currently on the queue. Exit This option will allow the user to exit the program. Use a queue to hold the RPN expressions. Use a stack to evaluate a RPN expression. A RPN expression should be represented as a character string. For simplicity all operands will be single-digit. No spaces should be in the character string. (Example: 23+46+)This expression evaluates to be 50.Explanation / Answer
The following file is Stack.cpp , which is the implementation file of Stack.h .Here stack is implemented using Linked list .Dev C++ IDE is Used to build the code.
#include<iostream>
#include"stack.h"
#include<stdlib.h>
using namespace std;
stack ::stack()
{
mytop=NULL;
}
bool Stack :: empty()
{
if(mytop==NULL)
return 1;
else return 0;
}
void Stack::push(StackElement X)
{
struct node *temp;
if(mytop==NULL)
{
mytop=(struct node*)malloc(sizeof(struct node));
mytop->data=X;
mytop->next=NULL;
}
else
{
temp=(struct node*)malloc(sizeof(struct node));
temp->data=X;
temp->next=top;
top=temp;
}
}
int Stack:: top()
{
return top->data;
}
void Stack :: pop()
{
if(top==NULL)
{
cout<<"underflow!!"
return;
}
struct node *temp;
temp=top;
top=top->next;
free(temp);
}
void Stack:: Sdisplay()
{
struct node *temp;
temp=top;
while(temp) // while there are elemnt in stack
{
cout<<temp->data;
temp=temp->data;
}
}
Now the following file is Queue.cpp , which is the implementation file of Queue.h header file.Here queue is implemented using Linked list .Dev C++ IDE is Used to build the code.
#include<iostream>
#include"stack.h"
#include<stdlib.h>
using namespace std;
Queue::Queue()
{
myfront=NULL;
myback=NULL;
}
void Queue:: AddQ(QueueElement x )
{
struct node *temp;
if (myback == NULL)
{
myback = (struct node *)malloc(1*sizeof(struct node));
myback->next = NULL;
myback->data = x;
myfront = myback;
}
else
{
temp=(struct node *)malloc(1*sizeof(struct node));
myback->next = temp;
temp->data = x;
temp->next = NULL;
myback = temp;
}
}
QueueElement Queue:: Front()
{
return (myfront->data);
}
void Queue :: RemoveQ()
{
struct node *front1 = front;
if (front1 == NULL)
{
cout<<"underflow";
return;
}
elseif (front1->next != NULL) //means more than 1 node are there
{
front1 = front1->next;
free(front);
myfront = front1;
}
else //only one node is there
{
free(front1);
myfront = NULL;
myback = NULL;
}
}
void Queue :: Qdisplay()
{
struct node *temp;
if( myfront == NULL)
cout<<"Empty Queue ";
else
{
temp=myfront;
while(temp)
{
cout<<temp->data;
temp=temp->next;
}
}
}
Now the following file is Client.cpp. Here evaluation of Reverse Polish Notation Expresssion is done using the above 2 files Stack.cpp and Queue.cpp.
#include"Stack.h"
#include"Queue.h"
#include<iostream>
#include<stdio.h>
#include<stack>
bool isoprtr(char ch) ;
void evaluate(char array[50]);
int applyOperation(int p1, int p2, char op);
using namespace std
int main()
{
int i; //variable for user choice
char str[50]; //temporary character array used for calculation
printf(" 1. Enter the expression");
printf(" 2. Evaluate an expression");
printf(" 3. printing all expression that have been evaluated");
printf(" 4. Exit ");
while(1)
{
printf(" Choose Option: ");
scanf("%d",&i);
switch(i)
{
case 1:
{
printf(" Enter the arithmetic expression to be evaluated: ");
gets(str)
AddQ(str); //the string is added to the queue
break;
}
case 2:
{
str=Front(); // the front string of queue is copied
RemoveQ(); // the front elemnt is copied.
evaluate(str);// function is called to evaluate the expression.
display();
break;
}
case 3:
{
Qdisplay(); // displaying all expression of queue
break;
}
case 4:
{
exit(0);
}
default:
{
printf(" wrong choice for operation");
}
}
}
return 0;
}
void evaluate(char array[50])
{
int len,i,j,buf[50],x;
stack<int> s;
len=strlen(array);
j = 0;
for(i=0; i<len;i++)
{
if(array[i]>='0' && array[i]<='9')
{
buf[j++] = array[i];
}
else if(array[i]==' ') //end of string
{
if(j>0)
{
buf[j] = '';
x = atoi(buf); //string to integer conversion
s.push(x); //using local stack
j = 0;
}
}
else if(isoprtr(array[i]))
{
oprtr1 = s.top();
s.pop();
oprtr2 = s.top();
s.pop();
s.push(performOperation(oprtr1, oprtr2, array[i]));
}
}
printf(" expression is %s and evaluated_answer is %d ",array, s.top());
}
bool isoprtr(char ch) //to check weather the character is operator or not?
{
if (ch=='+' || ch=='-' || ch=='*' || ch=='/')
return true;
else
return false;
}
int applyOperation(int p1, int p2, char op) //module for applying operation and returning resulted answer
{
int answer;
switch(op){
case '+':
answer = p2 + p1;
break;
case '-':
answer = p2 - p1;
break;
case '*':
answer = p2 * p1;
break;
case '/':
answer = p2 / p1;
break;
}
return answer;
}