Headers of Stack and Queue ( in .txt file ): [ http://goo.gl/i72VD8 ] Implement

Question

Headers of Stack and Queue (in .txt file): [http://goo.gl/i72VD8]

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 Explanation of options: 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. Programming guidelines 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

Stack implementation Using Single Linked List:

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class node
{
public:
class node *next;
int data;
};

class queue : public node
{
node *head;
int front,rare;
   public:
queue()
    {
   front=-1;
    rare=-1;
}
void push(int x)
    {
   if (rare < 0 )
        {
            head =new node;
       head->next=NULL;
   head->data=x;
    rare ++;
}
else
{
   node *temp,*temp1;
    temp=head;
   if(rare >= 4)
{
   cout <<"queue over flow";
    return;
}
rare++;
while(temp->next != NULL)
   temp=temp->next;
temp1=new node;
temp->next=temp1;
temp1->next=NULL;
temp1->data=x;
} }

void display()
    {
node *temp;
temp=head;
if (rare < 0)
{
cout <<" queue under flow";
return;
}
while(temp != NULL)
{
    cout <<temp->data<< " ";
temp=temp->next;
}
}
void pop()
{
   node *temp;
    temp=head;
if( rare < 0)
{
   cout <<"queue under flow";
    return;
}
if(front == rare)
{
   front = rare =-1;
    head=NULL;
return;
}
front++;
head=head->next;
}
};
main()
{
   queue s1;
   int ch;
   while(1)
{
       cout <<" 1.PUSH 2.POP 3.DISPLAY 4.EXIT enter ru choice:";
       cin >> ch;
       switch(ch)
       {
case 1:
    cout <<" enter a element";
   cin >> ch;
    s1.push(ch); break;

case 2: s1.pop();break;
case 3: s1.display();break;
   case 4: exit(0);
       }
}
return (0);
}

Queue using Single linked list:

#include<iostream>
using namespace std;

struct node
{
int data;
node *next;
}*front = NULL,*rear = NULL,*p = NULL,*np = NULL;

void push(int x)
{
np = new node;
np->data = x;
np->next = NULL;
if(front == NULL)
{
front = rear = np;
rear->next = NULL;
}
else
{
rear->next = np;
rear = np;
rear->next = NULL;
}
}
int remove()
{
int x;
if(front == NULL)
{
cout<<"empty queuen";
}
else
{
p = front;
x = p->data;
front = front->next;
delete(p);
return(x);
}
}
int main()
{
int n,c = 0,x;
cout<<"Enter the number of values to be pushed into queuen ";
cin>>n;
while (c < n)
{
cout<<"Enter the value to be entered into queuen ";
cin>>x;
push(x);
c++;
}
cout<<" Removed Values ";
while(true)
{
if (front != NULL)
cout<< " "<<remove()<<endl;
else
break;
}
return 0;
}

Program to evalate RPN(Reverse polish notation):

#include <iostream>
//#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
using namespace std;
const int MAX = 50 ;
class postfix
{
   private :

       int stack[MAX] ;
       int top, nn ;
       char *s ;
   public :
       postfix( ) ;
       void setexpr ( char *str ) ;
       void push ( int item ) ;
       int pop( ) ;
       void calculate( ) ;
       void show( ) ;
} ;
postfix :: postfix( )
{
   top = -1 ;
}
void postfix :: setexpr ( char *str )
{
   s = str ;
}
void postfix :: push ( int item )
{
   if ( top == MAX - 1 )
       cout << endl << "Stack is full" ;
   else
   {
       top++ ;
       stack[top] = item ;
   }
}
int postfix :: pop( )
{
   if ( top == -1 )
   {
       cout << endl << "Stack is empty" ;
       return NULL ;
   }
   int data = stack[top] ;
   top-- ;
   return data ;
}
void postfix :: calculate( )
{
   int n1, n2, n3 ;
   while ( *s )
   {
       if ( *s == ' ' || *s == ' ' )
       {
           s++ ;
           continue ;
       }
       if ( isdigit ( *s ) )
       {
           nn = *s - '0' ;
           push ( nn ) ;
       }
       else
       {
           n1 = pop( ) ;
           n2 = pop( ) ;
           switch ( *s )
           {
               case '+' :
                   n3 = n2 + n1 ;
                   break ;
               case '-' :
                   n3 = n2 - n1 ;
                   break ;
               case '/' :
                   n3 = n2 / n1 ;
                   break ;
               case '*' :
                   n3 = n2 * n1 ;
                   break ;
               case '%' :
                   n3 = n2 % n1 ;
                   break ;
               case '$' :
                   n3 = pow ( n2 , n1 ) ;
                   break ;
               default :
                   cout << "Unknown operator" ;
                   exit ( 1 ) ;
           }

           push ( n3 ) ;
       }
       s++ ;
   }
}
void postfix :: show( )
{
   nn = pop ( ) ;
   cout << "Result is: " << nn ;
}

int main( )
{
   char expr[MAX] ;
   cout << " Enter postfix expression to be evaluated : " ;
   cin.getline ( expr, MAX ) ;
   postfix q ;
   q.setexpr ( expr ) ;
   q.calculate( ) ;
   q.show( ) ;
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse H
• Subjects

---

---

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