Unit – 2
Stacks and Queues
Stack Example
A real-world stack allows operations at one end only. For example, we can place or remove a card or plate from the top of the stack only. Likewise, Stack ADT allows all data operations at one end only. At any given time, we can only access the top element of a stack.
This feature makes it LIFO data structure. LIFO stands for Last-in-first-out. Here, the element which is placed (inserted or added) last, is accessed first. In stack terminology, insertion operation is called PUSH operation and removal operation is called POP operation.
Stack Representation
A stack can be implemented by means of Array, Structure, Pointer, and Linked List. Stack can either be a fixed size one or it may have a sense of dynamic resizing. In stack we implement stack using arrays, which makes it a fixed size stack implementation.
Basic Operations
push() − Pushing (storing) an element on the stack.
pop() − Removing (accessing) an element from the stack.
Stack Push Operation
If the linked list is used to implement the stack, then in step 3, we need to allocate space dynamically.
Algorithm for PUSH Operation
A simple algorithm for Push operation can be derived as follows −
begin procedure push: stack, data
if stack is full
return null
endif
top ← top + 1
stack[top] ← data
end procedure
Implementation of this algorithm in C, is very easy.
See the following code −
Example
void push(int data) {
if(!isFull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
Pop Operation
Accessing the content while removing it from the stack, is known as a Pop Operation. In an array implementation of pop() operation, the data element is not actually removed, instead top is decremented to a lower position in the stack to point to the next value. But in linked-list implementation, pop() actually removes data element and deallocates memory space.
A Pop operation may involve the following steps −
Step 1 − Checks if the stack is empty.
Step 2 − If the stack is empty, produces an error and exit.
Step 3 − If the stack is not empty, accesses the data element at which top is pointing.
Step 4 − Decreases the value of top by 1.
Step 5 − Returns success.
Stack Pop Operation
Algorithm for Pop Operation
A simple algorithm for Pop operation can be derived as follows −
begin procedure pop: stack
if stack is empty
return null
endif
data ← stack[top]
top ← top - 1
return data
end procedure
Implementation of this algorithm in C, is as follows −
Example
int pop(int data) {
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
We need an effective mathematical theory to measure complexity and categorize the different implementations in terms of efficiency. The theory should be simple enough to allow us to study even the more complicated problems but at the same time it should be realistic. It should also be broad and unifying, allowing us to study and compare seemingly different cases.
Complexity functions that encounter include the following:
• O(1) – Constant
• O(logn) – Logarithmic
• O(n) – Linear
• O(nlogn) – (Linearithmic)
• O(n2 ) – Quadratic
Operations on Stack
There are three fundamental operations on stack.
Push: Insert element to the stack
Pop: Delete element from stack
Peek: Returns element at the top of stack
We will see these operations with respect to an example.
Here we assume stack size is 3.
Initially stack is empty. If pop operation is called on empty stack then stack underflow occurs.
----- (empty stack)
Push element ‘7’ to the stack. Then stack becomes
| 7 | <-- top
-----
Push element ‘2’ to the stack. So new top of stack is 2.
| 2 | <-- top
| 7 |
-----
Push element ‘10’ to the stack. Now top of stack becomes 10.
|10 | <-- top
| 2 |
| 7 |
-----
Now the stack becomes full as we are assuming stack size is 3. If we insert one more element onto stack then stack overflow occurs.
Pop element from stack. Element 10 is popped out. Hence new top is 2.
| 2 | <-- top
| 7 |
-----
Since Stack is LIFO data structure element inserted most recently will be popped out first.
Pop element 2 from stack. Hence new top is 7.
| 7 | <-- top
-----
Pop element 7 from stack. Now stack becomes empty.
----- (empty stack)
Array Implementation of Stack
Array implementation of stack is efficient if we know maximum size of stack.
Our stack must be able to store any type of data i.e.int, char, float or any other primitive data type.
Stack which is used to hold integer values must be able to hold float and character values.
For this we will not explicitly recode specific version of stack for each data type.
C++ provides this feature through class templates. Thus we implement stack ADT in C++ using class templates.
When we create class template, it can perform operations on any type of data.
The compiler will automatically generate correct type of object, depending on the type we specify when object is created.
Thus a stack ADT can be written as follows.
First we create node structure template.
template<class TYPE>
struct Node
{
Type value;
};
template<class TYPE> // class template
class stack
{
private:
Node<TYPE> *P; // pointer to structure
int count; // total no. of elements present in stack
int max; // total no. of elements allowed in stack
int top; // index of top of stack
public:
stack(int size=100); // constructor to create a stack
~stack(); // destructor to destroy stack
bool push(TYPE in); // function to insert element in stack
bool pop(TYPE &out); // function to delete element in stack
bool peek(TYPE& out); //return top element of stack
bool isempty(); //check if stack is empty
bool isfull(); //check if stack is full
int stackcount();// returns no. of elements currently in stack
};
Now we will see algorithms for these operations on stack in detail.
Create stack: stack()
Stack is created using constructor.
Steps
| Algorithm: stack(int size) | Description |
1 | template<class TYPE> stack<TYPE>::stack(int size) {
| Design constructor which takes stack size as an argument |
2 | max=size;
| Assign size to max. Value of size can be passed or default size of 100 is assumed. |
3 | P=new Node<TYPE>[max]; | allocate memory to P
|
4 | if(!P) { cout<<”Memory overflow”; abort(); }
| Check if memory is available. If memory is not available, abort and print “memory overflow “. |
5 | count=0; top=-1; }
| Initially stack is empty. So count is 0 and stack top is -1.
|
2. Insert element in Stack: push()
Steps
| Algorithm: bool push(TYPE in)
| Description |
1 | template<class TYPE> bool stack<TYPE>::push(TYPE in) {
| Design function push which inserts element ‘in’ to stack |
2 | if(count>=max) return false | Compare current total no. of elements with maximum stack size. If stack is full then return false to indicate element cannot be inserted. |
3 | P[top].value=in
| If stack is not full copy data to top of stack
|
4 | count++; top++; return true } | Increment count and top. Return true to indicate element is successfully inserted in stack. |
3.Remove element from stack: pop()
Steps
| Algorithm: bool pop(TYPE& out) | Description |
1 | template<class TYPE> bool stack<TYPE>::pop(TYPE& out) {
| Design function pop which deletes element on the top of stack. out is a reference variable to receive element to be popped out. |
2 | bool flag; if(count==0) flag=false; | If stack is empty then set flag to false |
3 | else { out=P[top].value;
| If stack has elements, copy element at top of stack to variable out. |
4 | top--; count--; flag=true; }
| Decrement count and top. Set flag to true to indicate pop is successful. |
5 | return flag; } | Return flag |
4.Find top of stack(tos):peek
Steps
| Algorithm: bool peek(TYPE& out) | Description |
1 | template<class TYPE> bool stack<TYPE>::peek(TYPE& out) {
| Design function peek which returns element on the top of stack without modifying stack. out is a reference variable to receive element at the top of stack. |
2 | bool flag; if(count==0) flag=false; | If stack is empty then set flag to false |
3 | else { out=P[top].value;
| If stack has elements, copy element at top of stack to variable out. |
4 | flag=true; }
| Set flag to true. |
5 | return flag; } | Return flag |
5.Check if the stack is empty: isEmpty()
Steps
| Algorithm: bool isEmpty() | Description |
1 | template<class TYPE> bool stack<TYPE>::isEmpty() {
| Design function isEmpty() which returns true if stack is empty and false otherwise. |
2 | bool flag; if(count==0) flag=true; | If stack is empty then set flag to true |
3 | else flag=false;
| If stack has elements set flag to false. |
4 | return flag; } | Return flag |
6. Check if the stack is full: isFull()
Steps
| Algorithm: bool isFull() | Description |
1 | template<class TYPE> bool stack<TYPE>::isFull() {
| Design function isFull() which returns true if stack is full and false otherwise. |
2 | bool flag; if(count==max) flag=true; | Compare count with maximum number of elements allocated for a stack. If they are equal set flag to true. |
3 | else flag=false;
| If count is not equal to max set flag to false. |
4 | return flag; } | Return flag |
7.Find total number of elements in stack: stackcount()
Steps
| Algorithm: int stackcount() | Description |
1 | template<class TYPE> int stack<TYPE>::stackcount() {
| Design function stackcount() which returns total number of elements present in stack. |
2 | return count; } | ‘count’ specifies total number of elements present in stack so return count |
Destroy stack:~stack()
Stack is destroyed using destructor.
Steps
| Algorithm: ~stack() | Description |
1 | template<class TYPE> stack<TYPE>::~stack() {
| Design destructor to destroy stack |
2 | delete[] P P=NULL; count=0; max=0; top=-1; } | Release memory of P. Set variables count,max to 0 and top to -1. |
Program in C++ to perform various operations on stack .
#include<iostream.h>
# define int MAX 100
template< class TYPE > //class template
class Stack {
int count; //number of elements present in stack
TYPE A[Max]; // Array of size MAX
TYPE out;
int top; // index of top of stack
public:
Stack(int MAX);
~Stack();
bool push(TYPE);
TYPE pop();
bool isEmpty();
bool isFull();
int stackcount();
void display();
};
template< class TYPE > //constructor to create stack
Stack< TYPE >::Stack(int MAX)
{
count=0;
top = -1;
}
template< class TYPE > //destructor to remove stack
Stack< TYPE >::~Stack()
{ delete[] A;
count=0;
MAX=0;
top=-1;
}
template< class TYPE>// function to push elements in stack
void Stack< TYPE >::push(TYPE in)
{
if(count>=MAX)
cout<<”stack overflow”
count++;
top++;
A[ top ] = in; //copy data to top of stack
}
template< class TYPE > // Function to pop elements from stack
TYPE Stack< TYPE >::pop()
{ return A[ top-- ];
count--;
}
template< class TYPE> //Function to check if stack is full
int Stack< TYPE>::isFull()
{
return (count == Max);
}
template< class TYPE> //Function to check if stack is empty
int Stack< TYPE>::isEmpty()
{
return (count == 0);
}
template< class TYPE>
int Stack< TYPE>::stackcount()
{
return count;
}
template< class TYPE> //Function to display stack elements
void Stack<TYPE>::display()
{
if(top<0)
cout<<”stack empty”;
for(int i=top;i>=0;i--)
cout<<A[i]<<” ”;
}
void main()
{
int choice,data;
Stack<int> S; //create stack of integers
while(1)
{
cout<<”Enter choice for operation”;
cout<<”\t 1.PUSH”<<endl;
cout<<”\t 2.POP”<<endl;
cout<<”\t 3.ISFULL”<<endl;
cout<<”\t 4.ISEMPTY”<<endl;
cout<<”\t 5.Stackcount”<<endl;
cout<<”\t 6.Display”<<endl;
cin>>choice;
switch(choice)
{
case 1:
cout<<”Enter element to be pushed”;
cin>>data
S.push(data);
break;
case 2:
out=S.pop();
cout<<”Popped element is”<<out;
break;
case 3:
int flag=S.isFull();
if(flag=1)
cout<<”stack is full”;
else
cout<<”stack is not full”;
break;
case 4:
int flag=S.isEmpty();
if(flag=1)
cout<<”stack is empty”;
else
cout<<”stack is not empty”;
break;
case 5:int c=S.stackcount();
cout<<”Stack count is”<<c;
break;
case 6: S.display();
break;
} //end of switch
} //end of while
} //end of program
Applications of Stack – Well form-ness of Parenthesis, Infix to Postfix Conversion and Postfix Evaluation
Applications of Stacks
Applications of stacks are as follows.
Reversing data
Parsing
Expression evaluation
Expression conversion
Reversing data
Data reversing is a technique of reordering data elements so that first element becomes last, second element becomes last but one and so on. Consider array A
10 | 5 | 2 | 4 | 9 |
A=
Fig. Original Array
After reversing array becomes
A=
9 | 4 | 2 | 5 | 10 |
Algorithm to reverse list of integers is as follows.
Steps
| Algorithm(Reverse) | Description |
1 | Create Stack | Create an empty stack |
2 | Read number | Accept integer from user |
3
3.1 3.2 | Loop(!fullstack(stack)) { push(stack.number) Read number } | Accept integers from user to fill the stack till it is not full. |
4
4.1 4.2 | Loop(!emptystack(stack)) { pop(stack.out) print(out) } | Pop elements from stack till stack is not empty. Print popped element to user. |
Another application of reversing data is conversion of decimal number to binary number. Algorithm for conversion of decimal to binary number is as follows.
Steps
| Algorithm(DecimaltoBinary) | Description |
1 | Create Stack | Create an empty stack |
2 | Read decimal number | Accept decimal number from user |
3
3.1 3.2 3.3
3.3.1 | Loop(number>0) { d=number%2 flag=push(stack.d) if(flag==false) { Print stack overflow } number=number/2 } | Convert the number to binary and push to stack. When stack becomes full print “stack overflow.” |
4
4.1 4.2 | Loop(!emptystack(stack)) { pop(stack.d) print(d) } | Pop elements from stack till stack is not empty. Print popped element to user |
***Program to convert decimal number to binary number****
#include <iostream>
#include <stdio.h>
#include <conio.h>
using namespace std;
struct Node
{
int value;
Node *next;
}*top = NULL, *P = NULL, *temp = NULL;
int x;
void push(int P)
{
temp = new Node;
temp->value = P;
temp->next = NULL;
if (top == NULL)
{
top = temp;
}
else
{
temp->next = top;
top = temp;
}
}
int pop()
{
if (top == NULL)
{
cout<<"underflow\n";
}
else
{
P = top;
top = top->next;
x = P->value;
delete(P);
return(x);
}
}
void main()
{
int num, a;
cout<<"enter the decimal number\n";
cin>>num;
while (num > 0)
{
a = num % 2;
num = num / 2;
push(a);
}
P = top;
cout<<"resultant binary no:";
while(1)
{
if (top != NULL)
cout<<pop()<<"\t";
else
break;
}
getch();
}
Parsing
Parsing breaks data into independent parts for processing.
For example a program parsing is breaking program into independent parts like keywords, identifiers, tokens and operators if any.
While writing any algebraic expression all of the parentheses should be properly paired. Unmatched parentheses in an algebraic expression pop errors such as missing of opening and closing parentheses.
We can use stacks for parsing so that all of the parentheses are paired properly.
Algorithm for parsing using stack is as follows.
Steps
| Algorithm(Parsing) | Description |
1
1.1 1.2
1.2.1 1.3
1.3.1
1.3.1.1
1.3.1.2 | While(1) { Read character if(character is an opening parenthesis) { push(stack.character) else { if(character is an closing parenthesis) { if(emptystack) print(“Closing parenthesis not matched”) else pop(stack.token) } } } }
|
Accept character from user If character is an opening parenthesis then push character in stack
If character is an closing parenthesis and if stack is empty then Closing parenthesis not matched If character is an closing parenthesis and if stack is not empty then pop its matching opening parenthesis from stack |
2 | if(!emptystack(stack)) print(“opening parenthesis not matched”); | If stack is not empty then opening parentheses not matched. |
Expression Evaluation
An expression can be represented in one of the following forms.
Infix: Infix expression has operator between operands. Eg. A + B
Prefix: Prefix expression has operator before operands. Eg. + A B
Postfix: Postfix expression has operator after operands. Eg. A B +
Evaluation of an Infix Expression:
Infix expressions are always evaluated from left to right. While evaluating it we must take care of operator precedence.
Following table shows priority of operators in C++.
Operators
|
Unary minus(-),! |
*,/,% |
+,- |
<,<=,>=,> |
==,!= |
&& |
|| |
Highest Priority
LeastPriority
Priority of operators in C++
According to above table – and ! have highest priority and logical OR has least priority. If an expression consists of operators with same priority(*,/,%)then evaluation is performed from left to right. If expression consists of parentheses then they are given top priority. Innermost parentheses are evaluated first.
Eg. Evaluate following infix expression
A / B – C + D * E. Given A=4,B=2,C=1,D=5,E=6
Considering above rules infix expression becomes.
((A / B) – C) + (D * E) Putting values in it
((4/2)-1)+(5*6)
(2-1)+(5*6)
1+30
31(Output)
Evaluation of prefix expression
Prefix expression has operator before operands. Prefix expression is always evaluated from right to left.
Eg. + 1 * 2 3
Evaluating from right to left, first operator we come across is ‘*’.so evaluate 2*3.so now expression becomes
+1 6
Again start evaluating from right to left. Next operator is +.
Add 1 and 6. So final output is 7.
Evaluation of prefix expression using Stack
Steps for Evaluation of prefix expression using Stack are as follows.
Accept prefix expression from user
Scan the expression from right to left
If token is an operand then push it in a stack.
If token is an operator then pop corresponding operands and perform operation.
Push result in stack.
Move to next token
Repeat steps 3 to 6 till the end of prefix expression.
Eg. -*+5 3 1 6
Prefix Input |
Stack |
Operand 1 |
Operand 2 |
Output |
Description |
-* 5 3 + 1 6
|
| - | - | - | Initially stack is empty. Evaluate expression from right to left. |
-* 5 3 + 1
|
| - | - | - | First token is an operand hence push operand 6 in stack |
-* 5 3 +
|
| - | - | - | Next token is again operand hence push operand 1 in stack |
-* 5 3 |
|
1 |
6 |
7 |
Next token is operator +, hence pop 1 and 6 and perform addition. Result is 7 .Push it in to stack
|
-* 5 |
| - | - | - | Next token is 3. Push it into stack.
|
-*
|
| - | - | - | Next token is 5. Push it into stack.
|
- |
| 5 | 3 | 15 | Next token is operator *, hence pop 5 and 3 and perform multiplication. Result is 15 .Push it in to stack
|
|
| 15 | 7 | 8 | Next token is operator -, hence pop 15 and 7 and perform subtraction. Result is 8 .Push it in to stack
|
Eg. 2: Evaluate the following prefix expression using stack for A= 16, B= 2, C=3, D=10, and E=4.Prefix Expression is
-+/A^BC*DE*AC DEC2007
Prefix Input |
Stack |
Op 1 |
Op 2 |
Output |
Description |
-+/A^BC*DE*AC |
| - | - | - | Initially stack is empty. Evaluate expression from right to left. |
-+/A^BC*DE*A
|
| - | - | - | First token is an operand C hence push operand 3 in stack
|
-+/A^BC*DE* |
| - | - | - | Next token is an operand A hence push operand 16 in stack |
-+/A^BC*DE |
|
16 |
3 |
48 |
Next token is operator *, hence pop 3 and 16 and perform multipliaction. Result is 48 .Push it in to stack
|
-+/A^BC*D |
| - | - | - | Next token is E. Push it into stack.
|
-+/A^BC* |
| - | - | - | Next token is D. Push it into stack.
|
-+/A^BC |
| 10 | 4 | 40 | Next token is operator *, hence pop 4 and 10 and perform multiplication. Result is 40 .Push it in to stack
|
-+/A^B |
| - | - | - |
Next token is C. Push it into stack
|
-+/A^ |
| - | - | - |
Next token is B. Push it into stack
|
-+/A
|
| 2 | 3 | 8 | Next token is operator ^, hence pop 2 and 3 and perform ^. Result is 8 .Push it into stack.
|
-+/
|
| - | - | - | Next token is A. Push it into stack
|
-+ |
| 16 | 8 | 2 | Next token is operator /, hence pop 16 and 8 and perform /. Result of 16/8 is 2 .Push it into stack.
|
- |
| 2 | 40 | 42 | Next token is operator +, hence pop 40 and 2 and perform +. Result of 40+2 is 42 .Push it into stack. |
|
|
42 |
48 |
-6 |
Next token is operator -, hence pop 42 and 48 and perform - . Result of 42-48 is -6 .Push it into stack. |
Hence final result is -6.
*****program for prefix expression evaluation.***
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
#include <string.h>
template <class TYPE> //class template
class stack
{
private:
TYPE *a;
int top,max;
public:
stack()
{
max = 50;
a = new TYPE[max];
top = 0;
}
stack(int n)
{
max = n + 1;
a = new TYPE[max];
top= 0;
}
~stack()
{
delete a;
}
friend void push(stack &,TYPE); // member functions for stack
friend TYPE pop(stack &);
friend int isEmpty(stack);
};
template <class TYPE>
void push(stack <TYPE> &s, TYPE x)
{
if(s.top != s.max)
{
s.top++;
s.a[s.top] = x;
}
else
cout << "\nStack Overflow.";
}
template <class TYPE>
TYPE pop(stack <TYPE> &s)
{
TYPE temp;
if(s.top != 0)
{
temp = s.a[s.top];
s.top--;
return temp;
}
else
{
temp = -999;
return temp;
}
}
template <class TYPE>
int isEmpty(stack <TYPE> s)
{
if(s.top == 0)
return 1;
else
return 0;
}
int main()
{
char prefix[30],b[2];
int i = 0;
float e;
cout << "Enter a Prefix Expression,\n";
prefix[i - 1] ='\0';
while(prefix[i-1] != '\n')
prefix[i++] = getchar(); // prefix expression
stack <float> O(50); //call constructor to create stack
float value,operand1,operand2;
int j = i - 2,pos,k;
while(j >= 0)
{
pos = 0;
if(prefix[j] >= '0' && prefix[j] <= '9')
{
b[0] = prefix[j]; // Save Prefix[j] to b
i = j - 1;
k = 1;
if(prefix[j-1] != ' ') //Check for next character, If not Space
{
while(prefix[i] != ' ') //While space is not found
{
b[k++] = prefix[i--]; //Save Prefix[i] to b
pos++; //Increase Position
}
pos += 2;//At Last Increase Position by 2 to Skip Space
}
else //If a Single Character
pos = 2; //Skip Space
b[k] = '\0'; //End String temp
strrev(b);
x = atof(b); //Convert string b to float and store to x
push(O,x); //Push to stack
}
else if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^' ) // check for operators
{
operand1 = pop(O);
if(operand1 == -999)
break;
if(prefix[j] == '+' || prefix[j] == '-' || prefix[j] == '*' || prefix[j] == '/' || prefix[j] == '^')
{
operand2 = pop(O);
if(operand2 == -999)
break;
}
if(prefix[j] == '+')
value = operand1 + operand2;
if(prefix[j] == '-')
value = operand1 - operand2;
if(prefix[j] == '*')
value = operand1 * operand2;
if(prefix[j] == '/')
{
if(operand2 != 0)
value = operand1 / float(operand2); //Cast one operand to float
else
{
cout << "\nError ! Cannot Divide by Zero";
getch();
return 0;
}
}
if(prefix[j] == '^')
value = pow(operand1,operand2);
push(O,value);
pos = 2;
}
else
{
cout << "\nError : Illegal Character";
getch();
return 0;
}
j -= pos;
}
float output = pop(O);
if(output == -999 || !isEmpty(O)) //If Underflow Condition or stack is not empty,
{
cout << "\nError : The Given Prefix Expression is Not Valid.";
getch();
return 0;
}
else
cout << "\nOutput = " << Output;
getch();
return 0;
}
Evaluation of Postfix expression
Postfix expression has operator after operands. Postfix expression is evaluated from left to right.
Eg.6 4 2 * +
Evaluating from left to right first operator we come across is ‘*’.so evaluate 4*2.so now expression becomes
6 8 +. Again start evaluating from left to right. Next operator is +. Add 6 and 8. So final output is 14.
Evaluation of postfix expression using Stack
Steps for Evaluation of postfix expression using Stack are as follows.
Accept postfix expression from user
Scan the expression from left to right
If token is an operand then push it in a stack.
If token is an operator then pop corresponding operands and perform operation.
Store result in stack.
Move to next token
Repeat steps 3 to 6 till the end of postfix expression.
Eg. : 623+-382/+*2^3+
Postfix Input
| Stack | Op1 | Op2 | Output | Description |
623+-382/+*2^3+
|
| - | - | - | Initially stack is empty. Evaluate expression from left to right. |
23+-382/+*2^3+
|
| - | - | - | First token is an operand 6. Push it into stack. |
3+-382/+*2^3+
|
| - | - | - | Next token is an operand 2. Push it into stack.
|
+-382/+*2^3+ |
| - | - | - | Next token is an operand 3. Push it into stack.
|
-382/+*2^3+
|
| 2 | 3 | 5 | Next token is operator +, hence pop 2 and 3 and perform +. Result of 2+3 is 5 .Push it into stack. |
382/+*2^3+
|
| 6 | 5 | 1 | Next token is operator -, hence pop 5 and 6 and perform -. Result of 6-5 is 1 .Push it into stack.
|
82/+*2^3+
|
| - | - | - | Next token is an operand 3. Push it into stack.
|
2/+*2^3+
|
| - | - | - | Next token is an operand 8. Push it into stack.
|
/+*2^3+
|
| - | - | - |
Next token is an operand 2. Push it into stack.
|
+*2^3+
|
| 8 | 2 | 4 | Next token is operator /, hence pop 2 and 8 and perform /. Result of 8/2 is 4 .Push it into stack.
|
*2^3+
|
| 3 | 4 | 7 | Next token is operator +, hence pop 4 and 3 and perform +. Result of 3+4 is 7 .Push it into stack.
|
2^3+
|
| 1 | 7 | 7 | Next token is operator *, hence pop 7 and 1 and perform *. Result of 1*7 is 7 .Push it into stack.
|
^3+ |
| - | - | - | Next token is an operand 2. Push it into stack.
|
3+
|
| 7 | 2 | 49 | Next token is operator ^, hence pop 2 and 7 and perform ^. Result of 7^2 is 49 .Push it into stack.
|
+ |
| - | - | - | Next token is an operand 3. Push it into stack.
|
|
|
49
|
3 |
52 | Next token is operator +, hence pop 3 and 49 and perform +. Result of 49+3 is 52 .Push it into stack.
|
Hence final result is 52.
Eg.2: Evaluate the following postfix expression and show stack after every step in tabular form. Given A= 5, B= 6, C=2, D=12, and E=4.POSTfix Expression is
ABC+*DE\- MAY2007
Postfix Input
| stack | Op1 | Op2 | Output | Description |
ABC+*DE\- |
| - | - | - | Initially stack is Empty. Evaluate expression from left to right. |
BC+*DE\- |
| - | - | - | First token is an operand A i.e.5. Push it into stack.
|
C+*DE\- |
| - | - | - | Next token is an operand B i.e.6. Push it into stack.
|
+*DE\-
|
| - | - | - | Next token is an operand C i.e.2. Push it into stack.
|
*DE\-
|
| 6 | 2 | 8 | Next token is operator +, hence pop 2 and 6 and perform +. Result of 6+2 is 8 .Push it into stack.
|
DE\- |
| 5 | 8 | 40 | Next token is operator *, hence pop 8 and 5 and perform *. Result of 8*5 is 40 .Push it into stack.
|
E\-
|
| - | - | - | Next token is an operand D i.e.12. Push it into stack.
|
\-
|
| - | - | - | Next token is an operand E i.e.4. Push it into stack.
|
- |
| 12 | 4 | 3 | Next token is operator \, hence pop 4 and 12 and perform \. Result of 12\4 is 3 .Push it into stack.
|
|
| 40 | 3 | 37 | Next token is operator -, hence pop 3 and 40 and perform -. Result of 40-3 is 37 .Push it into stack.
|
Hence final output is 37.
*******Program to evaluate Postfix expression********
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
# define int MAX = 50 ;
class stack
{
private :
int A[MAX] ;
int top, y ;
char *s ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( int x ) ;
int pop( ) ;
void calculate( ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
}
void stack :: exprn ( char *str )
{
s = str ;
}
void stack :: push ( int x )
{
if ( top == MAX - 1 )
cout << endl << "Stack is full" ;
else
{
top++ ;
A[top] = x ;
}
}
int stack :: pop( )
{
if ( top == -1 )
{
cout << endl << "Stack is empty" ;
return NULL ;
}
int data = A[top] ;
top-- ;
return data ;
}
void stack :: calculate( )
{
int n1, n2, n3 ;
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) )
{
y = *s - '0' ;
push ( y ) ;
}
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 stack :: display( )
{
y = pop ( ) ;
cout << "Result is: " << y ;
}
void main( )
{
char C[MAX] ;
cout << "\nEnter postfix expression to be evaluated : " ;
cin.getline ( C, MAX ) ;
stack o ;
o.exprn ( C ) ;
o.calculate( ) ;
o.display( ) ;
}
Expression conversion
Expression conversion is of following types
Manual Transformation
Infix expression can be manually converted to postfix in following steps.
Fully parenthesize the infix expression considering operator precedence. There should be one set of parentheses for each operator.
Evaluate innermost expression first. Replace right parenthesis with corresponding operator.
Remove left parentheses.
Eg. X+Y/Z
Step 1: (X+(Y/Z))
Step 2: (X+(YZ/)
(X(YZ/+
Step 3: XYZ/+
Stack Transformation
Infix expression can be converted to postfix using stack in following steps.
Initialize an empty stack.
While not to end of infix expression
Scan the expression from left to right.
Get the input token in the infix expression.
If the token is
A left parenthesis then push it onto the stack
A right parenthesis then Pop and display stack elements until a left parenthesis is encountered.
Note: Do not display parenthesis. Parenthesis has least priority in stack but highest priority when in input expression.
An operator: If the stack is empty or input token has higher priority than the top stack, push onto the stack. Otherwise, pop and display the top stack element. Repeat the comparison of input token with the new top stack element.
An operand: Just display it.
When end of infix expression is reached, pop and display stack elements until the stack is empty.
Eg1. 4+5*9/1
Infix | Stack | Postfix | Description |
4+5*9/1 |
|
| Initially stack is empty. scan expression from left to right. |
+5*9/1 |
| 4
| First token is an operand 4 so add to postfix expression. |
5*9/1 |
| 4 | Next token is operator + and stack is empty so push it into stack |
*9/1
|
| 45 | Next token is an operand 5 so add to postfix expression.
|
9/1
|
| 45 | Next token is operator *.Compare * with +. * has higher precedence over + so push it to stack. |
/1 |
| 459 | Next token is an operand 9 so add to postfix expression.
|
1 |
| 459* | Next token is operator /.Compare / with *. * has higher precedence over / so pop it from stack and push /.
|
|
| 459*1 | Next token is an operand 1 so add to postfix expression. |
|
| 459*1/+ | Pop remaining tokens from stack and add to postfix expression |
Hence Postfix expression is 459*1/+
Eg.2 Convert (2+4)*(5-6)/((1-2)*(9+2)) to Postfix expression.
Infix | stack | Postfix |
(2+4)*(5-6)/((1-2)*(9+2)) |
|
|
2+4)*(5-6)/((1-2)*(9+2)) | ( |
|
+4)*(5-6)/((1-2)*(9+2)) | ( | 2 |
)*(5-6)/((1-2)*(9+2)) | (+ | 24 |
*(5-6)/((1-2)*(9+2)) |
| 24+ |
(5-6)/((1-2)*(9+2)) | * | 24+ |
5-6)/((1-2)*(9+2)) | *( | 24+ |
-6)/((1-2)*(9+2)) | *( | 24+5 |
6)/((1-2)*(9+2)) | *(- | 24+5 |
)/((1-2)*(9+2)) | *(- | 24+56 |
/((1-2)*(9+2)) | * | 24+56- |
((1-2)*(9+2)) | / | 24+56-* |
(1-2)*(9+2)) | /( | 24+56-* |
1-2)*(9+2)) | /(( | 24+56-* |
-2)*(9+2)) | /(( | 24+56-*1 |
2)*(9+2)) | /((- | 24+56-*1 |
)*(9+2)) | /((- | 24+56-*12 |
*(9+2)) | /( | 24+56-*12- |
(9+2)) | /(* | 24+56-*12- |
9+2)) | /(*( | 24+56-*12- |
+2)) | /(*( | 24+56-*12-9 |
2)) | /(*(+ | 24+56-*12-9 |
)) | /(*(+ | 24+56-*12-92 |
) | /(* | 24+56-*12-92+ |
| / | 24+56-*12-92+* |
|
| 24+56-*12-92+*/ |
Eg.3:Convert the following arithmetic expression into postfix
A+(B*C-(D/E-F)*G)*H MAY 2007
Infix | stack | Postfix |
A+(B*C-(D/E-F)*G)*H
|
|
|
+(B*C-(D/E-F)*G)*H |
| A |
(B*C-(D/E-F)*G)*H | + | A |
B*C-(D/E-F)*G)*H | +( | A |
*C-(D/E-F)*G)*H | +( | AB |
C-(D/E-F)*G)*H | +(* | AB |
-(D/E-F)*G)*H | +(* | ABC |
(D/E-F)*G)*H | +(- | ABC* |
D/E-F)*G)*H | +(-( | ABC* |
/E-F)*G)*H | +(-( | ABC*D |
E-F)*G)*H | +(-(/ | ABC*D |
-F)*G)*H | +(-(/ | ABC*DE |
F)*G)*H | +(-(- | ABC*DE/ |
)*G)*H | +(-(- | ABC*DE/F |
*G)*H | +(- | ABC*DE/F- |
G)*H | +(-* | ABC*DE/F- |
)*H | +(-* | ABC*DE/F-G |
*H | + | ABC*DE/F-G*- |
H | +* | ABC*DE/F-G*-H |
| +* | ABC*DE/F-G*-H |
|
| ABC*DE/F-G*-H*+ |
EG. Convert the following expression into postfix.
(A+B)*D+E/(F+A*D)+C
A*(B+C)/D-G MAY 2008
1. (A+B)*D+E/(F+A*D)+C
Infix | stack | Postfix |
(A+B)*D+E/(F+A*D)+C
|
|
|
A+B)*D+E/(F+A*D)+C | ( |
|
+B)*D+E/(F+A*D)+C | ( | A |
B)*D+E/(F+A*D)+C | (+ | A |
)*D+E/(F+A*D)+C | (+ | AB |
*D+E/(F+A*D)+C |
| AB+ |
D+E/(F+A*D)+C | * | AB+ |
+E/(F+A*D)+C | * | AB+D |
E/(F+A*D)+C | + | AB+D* |
/(F+A*D)+C | + | AB+D*E |
(F+A*D)+C | +/ | AB+D*E |
F+A*D)+C | +/( | AB+D*E |
+A*D)+C | +/( | AB+D*EF |
A*D)+C | +/(+ | AB+D*EF |
*D)+C | +/(+ | AB+D*EFA |
D)+C | +/(+* | AB+D*EFA |
)+C | +/(+* | AB+D*EFAD |
+C | +/ | AB+D*EFAD*+ |
C | + | AB+D*EFAD*+/+ |
| + | AB+D*EFAD*+/+C |
|
| AB+D*EFAD*+/+C+ |
2. A*(B+C)/D-G
Infix | stack | Postfix |
A*(B+C)/D-G |
|
|
*(B+C)/D-G |
| A |
(B+C)/D-G | * | A |
B+C)/D-G | *( | A |
+C)/D-G | *( | AB |
C)/D-G | *(+ | AB |
)/D-G | *(+ | ABC |
/D-G | * | ABC+ |
D-G | / | ABC+* |
-G | / | ABC+*D |
G | - | ABC+*D/ |
| - | ABC+*D/G |
|
| ABC+*D/G- |
Hence postfix expression is ABC+*D/G-
*********PROGRAM FOR INFIX TO POSTFIX****************
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#define int MAX = 50 ;
class stack
{
private :
char S[MAX], A[MAX] ;
char *s, *t ;
int top ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
strcpy ( S, "" ) ;
strcpy ( A, "" ) ;
t = S ;
s = "" ;
}
void stack :: exprn ( char *str )
{
s = str ;
}
void stack :: push ( char c )
{
if ( top == MAX )
cout << "\nStack is full\n" ;
else
{
top++ ;
A[top] = c ;
}
}
char stack :: pop( )
{
if ( top == -1 )
{
cout << "\nStack is empty\n" ;
return -1 ;
}
else
{
char x = A[top] ;
top-- ;
return x ;
}
}
void stack :: convert( )
{
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t++ ;
}
}
if ( *s == '(' )
{
push ( *s ) ;
s++ ;
}
char opr ;
if ( *s == '*' || *s == '+' || *s == '/' || *s == '%' || *s == '-' || *s == '^' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) >= priority ( *s ) )
{
*t = opr ;
t++ ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == ')' )
{
opr = pop( ) ;
while ( ( opr ) != '(' )
{
*t = opr ;
t++ ;
opr = pop( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
char opr = pop( ) ;
*t = opr ;
t++ ;
}
*t = '\0' ;
}
int stack :: priority ( char c )
{
if ( c == '^' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void stack :: display( )
{
cout << S ;
}
void main( )
{
char Y[MAX] ;
stack O ;
cout << "\nEnter an expression in infix form: " ;
cin.getline ( Y, MAX ) ;
O.exprn ( Y ) ;
O.convert( ) ;
cout << "\nThe postfix expression is: " ;
O.display( ) ;
}
Manual Transformation
Infix expression can be manually converted to prefix in following steps.
Fully parenthesize the infix expression considering operator precedence. There should be one set of parentheses per operator.
Evaluate innermost expression first. Replace left parenthesis with corresponding operator.
Remove right parentheses.
Eg. X+Y/Z
step 1 :(X+(Y/Z))
Step 2:(X+/YZ))
+X/YZ))
Step 3 :+X/YZ
Stack Transformation
Infix expression can be converted to prefix using stack in following steps.
Reverse the given infix expression.
Convert every opening bracket( into closing bracket ) and vice versa.
Convert the resultant expression into postfix form by following algorithm.
Initialize an empty stack.
While not to end of infix expression
Scan the expression from left to right.
Get the input token in the infix expression.
3.5 If the token is
a) A left parenthesis then push it onto the stack
b) A right parenthesis then Pop and display stack elements until a left parenthesis is encountered.
Note: Do not display parenthesis. Parenthesis has least priority in stack but highest priority when in input expression.
c) An operator: If the stack is empty or input token has higher priority than the top stack, push onto the stack. Otherwise, pop and display the top stack element. Repeat the comparison of input token with the new top stack element.
d) An operand: Just display it.
When end of infix expression is reached, pop and display stack elements until the stack is empty.
Reverse the resultant expression.
Eg. (A-(B/C))*((D*E)-F)
Step 1: Reverse the given expression
Original expression is (A-(B/C))*((D*E)-F) By reversing we get )F-)E*D((*))C/B(-A(
Step 2: Convert every opening bracket( into closing bracket ) and vice versa.
(F-(E*D))*((C/B)-A)
Step 3:Convert the resultant expression in postfix form
Infix | stack | Postfix |
(F-(E*D))*((C/B)-A) |
|
|
F-(E*D))*((C/B)-A) | ( |
|
-(E*D))*((C/B)-A) | ( | F |
(E*D))*((C/B)-A) | (- | F |
E*D))*((C/B)-A) | (-( | F |
*D))*((C/B)-A) | (-( | FE |
D))*((C/B)-A) | (-(* | FE |
))*((C/B)-A) | (-(* | FED |
)*((C/B)-A) | (- | FED* |
*((C/B)-A) |
| FED*- |
((C/B)-A) | * | FED*- |
(C/B)-A) | *( | FED*- |
C/B)-A) | *(( | FED*- |
/B)-A) | *(( | FED*-C |
B)-A) | *((/ | FED*-C |
)-A) | *((/ | FED*-CB |
-A) | *( | FED*-CB/ |
A) | *(- | FED*-CB/ |
) | *(- | FED*-CB/A |
| * | FED*-CB/A- |
|
| FED*-CB/A-* |
Step 4:Reverse the postfix expression
*-A/BC-*DEF
Hence the prefix expression is *-A/BC-*DEF
Eg.2 4*(2-(6*3+4)*2)+1
Step 1: Step 1: Reverse the given expression
Original expression is 4*(2-(6*3+4)*2)+1
By reversing we get 1+)2*)4+3*6(-2(*4
Step 2: Convert every opening bracket( into closing bracket ) and vice versa.
1+(2*(4+3*6)-2)*4
Step 3:Convert the resultant expression in postfix form
Infix | stack | Postfix |
1+(2*(4+3*6)-2)*4
|
|
|
+(2*(4+3*6)-2)*4 |
| 1 |
(2*(4+3*6)-2)*4 | + | 1 |
2*(4+3*6)-2)*4 | +( | 1 |
*(4+3*6)-2)*4 | +( | 12 |
(4+3*6)-2)*4 | +(* | 12 |
4+3*6)-2)*4 | +(*( | 12 |
+3*6)-2)*4 | +(*( | 124 |
3*6)-2)*4 | +(*(+ | 124 |
*6)-2)*4 | +(*(+ | 1243 |
)-2)*4 | +(*(+* | 1243 |
-2)*4 | +(*(+* | 12436 |
2)*4 | +(* | 12436*+ |
)*4 | +(- | 12436*+* |
*4 | +(- | 12436*+*2 |
4 | + | 12436*+*2- |
| +* | 12436*+*2- |
| +* | 12436*+*2-4 |
|
| 12436*+*2-4*+ |
Step 4:Reverse the postfix expression
+*4-2*+*63421
Hence the prefix expression is +*4-2*+*63421
***program to convert infix to prefix**************
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#define int MAX = 50 ;
class stack
{
private :
char S[MAX], A[MAX] ;
char *s, *t ;
int top, len ;
public :
stack( ) ;
void exprn ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void display( ) ;
} ;
stack :: stack( )
{
top = -1 ;
strcpy ( S, "" ) ;
strcpy ( A, "" ) ;
len = 0 ;
}
void stack:: exprn ( char *str )
{
s = str ;
strrev ( s ) ;
len = strlen ( s ) ;
* ( S + len ) = '\0' ;
t = S + ( len - 1 ) ;
}
void stack :: push ( char c )
{
if ( top == MAX - 1 )
cout << "\nStack is full\n" ;
else
{
top++ ;
A[top] = c ;
}
}
char stack :: pop( )
{
if ( top == -1 )
{
cout << "Stack is empty\n" ;
return -1 ;
}
else
{
char x = A[top] ;
top-- ;
return x ;
}
}
void stack:: convert( )
{
char opr ;
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t-- ;
}
}
if ( *s == ')' )
{
push ( *s ) ;
s++ ;
}
if ( *s == '*' || *s == '+' || *s == '/' ||
*s == '%' || *s == '-' || *s == '^' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) > priority ( *s ) )
{
*t = opr ;
t-- ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == '(' )
{
opr = pop( ) ;
while ( ( opr ) != ')' )
{
*t = opr ;
t-- ;
opr = pop ( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
opr = pop( ) ;
*t = opr ;
t-- ;
}
t++ ;
}
int stack :: priority ( char c )
{
if ( c == '^' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void stack :: display( )
{
while ( *t )
{
cout << " " << *t ;
t++ ;
}
}
void main( )
{
char C[MAX] ;
stack O ;
cout << "\nEnter an expression in infix form: " ;
cin.getline ( C, MAX ) ;
O.exprn( C ) ;
O.convert( ) ;
cout << "The Prefix expression is: " ;
O.display( ) ;
}
Steps to convert postfix to infix are as follows
Scan the postfix expression from left to right.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in infix form(operator between two operands).Place parentheses for subexpression to ensure proper order of evaluation in final expression.
Note: We place parenthesis only if it is required(operator in subexpression has lower precedence than operator used to merge two subexpressions ).Otherwise proper order of evaluation is maintained without any additional parentheses.
Push resulting subexpression in stack.
Move to next token.
Repeat steps 2 to 5 till the end of postfix expression.
Eg1.ab*cd*+e*
Postfix Expression | Stack | Description |
ab*cd*+e* | Empty | Initially stack is empty |
b*cd*+e* | a | First token is operand hence push it to stack. |
*cd*+e* | a, b | Next token is an operand. Push it into stack. |
cd*+e* | (a*b) | Next token is an operator ‘*’.Pop two recent operands(a,b) and form subexpression(a*b) in infix form. Place parentheses for Resultant subexpression(a*b).Push it into stack. |
d*+e* | (a*b), c | Next token is an operand c. Push it into stack |
*+e* | (a*b), c,d | Next token is an operand d. Push it into stack |
*+e* | (a*b), (c*d) | Next token is an operator ‘*’.Pop two recent operands(c,d) and form subexpression in infix form. Place parentheses for Resultant subexpression(c*d).Push it into stack. |
+e* | ((a*b)+ (c*d)) | Next token is an operator ‘+’.Pop two recent operands(a*b)and(c*d). Form subexpression in infix form. Place parentheses for Resultant subexpression((a*b)(c*d)).Push it into stack. |
e* | (a*b)+(c*d),e | Next token is an operand e. Push it into stack |
* | ((a*b)+(c*d))*e | Next token is an operator ‘*’.Pop two recent operands((a*b)+(c*d))and e. Form subexpression in infix form ((a*b)+(c*d))*e. Push it into stack. |
| ((a*b)+(c*d))*e |
|
Hence resultant infix expression is ((a*b)+(c*d))*e
Eg.2:Convert the following postfix expression to infix using stack.
abcde^^*- May 2006
Postfix Expression | Stack | Description |
abcde^^*- | Empty | Initially token is empty |
bcde^^*- | A | Next token is an operand a. Push it into stack. |
cde^^*- | a,b | Next token is an operand b. Push it into stack. |
de^^*- | a,b,c | Next token is an operand c. Push it into stack. |
e^^*- | a,b,c,d | Next token is an operand d. Push it into stack. |
^^*- | a,b,c,d,e | Next token is an operand e. Push it into stack. |
^*- | a,b,c,(d^e) | Next token is an operator ‘^’.Pop two recent operands(d)and(e). Form subexpression in infix form. Place parentheses for Resultant subexpression(d^e).Push it into stack. |
*- | a,b,c^(d^e) | Next token is an operator ‘^’.Pop two recent operands(c)and(d^e). Form subexpression in infix form. Push it into stack. |
- | a, b*c^(d^e) | Next token is an operator ‘*’.Pop two recent operands.Form subexpression in infix form. Push it into stack. |
| a-b*c^(d^e) | Next token is an operator ‘-’.Pop two recent operands. Form subexpression in infix form. Push it into stack. |
Hence resultant expression is a-b*c^(d^e)
Postfix expression can be converted to prefix using following steps.
Scan the postfix expression from left to right.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in prefix form(operator before two operands).
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of postfix expression.
Eg.1: Convert the following postfix expression to prefix using stack.
abcde^^*- May 2006
Postfix Expression | Stack | Description |
abcde^^*- | Empty | Initially stack is empty |
bcde^^*- | a | Next token is an operand a. Push it into stack. |
cde^^*- | a,b | Next token is an operand b. Push it into stack. |
de^^*- | a,b,c | Next token is an operand c. Push it into stack. |
e^^*- | a,b,c,d | Next token is an operand d. Push it into stack. |
^^*- | a,b,c,d,e | Next token is an operand e. Push it into stack. |
^*- | a,b,c,^de | Next token is an operator ‘^’.Pop two recent operands(d)and(e). Form subexpression in prefix form. Push it into stack. |
*- | a,b,^c^de | Next token is an operator ‘^’.Pop two recent operands(c)and(^de). Form subexpression in prefix form. Push it into stack. |
- | a, *b^c^de | Next token is an operator ‘*’.Pop two recent operands.Form subexpression in prefix form. Push it into stack. |
| -a*b^c^de | Next token is an operator ‘-’.Pop two recent operands. Form subexpression in prefix form. Push it into stack. |
Hence resultant prefix expression is -a*b^c^de
Steps to convert prefix to infix are as follows
Scan the prefix expression from right to left.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in infix form(operator between two operands).Place parentheses for subexpression to ensure proper order of evaluation in final expression.
Note: We place parenthesis only if it is required(operator in subexpression has lower precedence than operator used to merge two subexpressions ).Otherwise proper order of evaluation is maintained without any additional parentheses.
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of prefix expression.
Eg1. +/+AB-CDE
prefix Expression | Stack | Description |
+/+AB-CDE | Empty | Initially stack is empty |
+/+AB-CD | E | Next token is an operand E. Push it into stack. |
+/+AB-C | E,D | Next token is an operand D. Push it into stack. |
+/+AB- | E,D,C | Next token is an operand C. Push it into stack. |
+/+AB | E,(C-D) | Next token is an operator ‘-’.Pop two recent operands(C)and(D). Form subexpression in infix form. Push it into stack. |
+/+A | E,(C-D),B | Next token is an operand B. Push it into stack. |
+/+ | E,(C-D),B,A | Next token is an operand A. Push it into stack. |
+/ | E,(C-D),(A+B) | Next token is an operator ‘+’.Pop two recent operands(A)and(B). Form subexpression in infix form. Push it into stack. |
+ | E,(A+B)/(C-D) | Next token is an operator ‘/’.Pop two recent operands(A+B)and(C+D). Form subexpression in infix form. Push it into stack. |
| (A+B)/(C-D)+E | Next token is an operator ‘+’.Pop two recent operands(A+B)/(C-D) and E. Form subexpression in infix form. Push it into stack. |
Hence resultant infix expression is (A+B)/(C-D)+E
Steps to convert prefix to postfix are as follows
Scan the prefix expression from right to left.
If token is an operand push it into stack.
If token is an operator pop recent two operands. Form new subexpression with this operator and operands in postfix form(operator after two operands).
Push resulting subexpression in stack.
Move to next token.
Repeat step 2 to 5 till the end of prefix expression.
Eg1. +/+AB-CDE
prefix Expression | Stack | Description |
+/+AB-CDE | Empty | Initially stack is empty |
+/+AB-CD | E | Next token is an operand E. Push it into stack. |
+/+AB-C | E,D | Next token is an operand D. Push it into stack. |
+/+AB- | E,D,C | Next token is an operand C. Push it into stack. |
+/+AB | E,CD- | Next token is an operator ‘-’.Pop two recent operands(C)and(D). Form subexpression in postfix form. Push it into stack. |
+/+A | E,CD-,B | Next token is an operand B. Push it into stack. |
+/+ | E,CD-,B,A | Next token is an operand A. Push it into stack. |
+/ | E,CD-,AB+ | Next token is an operator ‘+’.Pop two recent operands(A)and(B). Form subexpression in postfix form. Push it into stack. |
+ | E,AB+/CD- | Next token is an operator ‘/’.Pop two recent operands(AB+)and(CD+). Form subexpression in postfix form. Push it into stack. |
| AB+/CD-E+ | Next token is an operator ‘+’.Pop two recent operandsAB+/CD- and E. Form subexpression in postfix form. Push it into stack. |
Hence resultant postfix expression is AB+/CD-E+
Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.
Applications of stack:
Imagine a queue of people waiting for a bus. The person in the front of queue will get a first chance to board a bus. The person at the rear will be last one to board a bus. Same case is of checkout line in a grocery store or a cafeteria, list of jobs to be processed by computer or a list of calls on mobile phone.Fig.1 shows queue of alphabets. Alphabets are added at rear and removed from front end.
A front | B | C | D | E | F rear |
Fig 1. Queue of alphabets
We will see queue with respect to an example. Imagine queue of alphabets with size of three. Initially queue is empty.
front |
|
rear |
Now let us add an element in a queue. So queue becomes
Front |
| A rear |
Add one more element ’B’ in a queue. Since element can only be inserted at rear, A progresses through queue and B is inserted at rear. Now queue becomes
Front | A | B Rear |
Adding one more element ‘C’ in queue
A Front | B | C Rear |
Now queue is full. If we try to insert one more element in queue then queue overflow occurs.
Now remove elements from queue. Element in queue is always removed from front end. Currently ‘A’ is at front end and hence will be removed first.
B front | C |
Rear |
Removing ‘B’ and ‘C’ we get
front |
|
Rear |
Now queue is empty. If we try to remove elements from queue, queue underflow occurs.
struct Node //Node declaration
{
TYPE value; //data in a node
};
template <class TYPE> //class template for queue
class Queue
{
private:
Node<TYPE> * P; //pointer to node
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50);
~Queue();
bool enqueue(TYPE in);
bool dequeue(TYPE& out);
bool QFront(TYPE& out);
bool QRear(TYPE& out);
int QCount();
bool isEmpty();
bool isFull();
};
We will see array implementation for
struct Node //Node declaration
{
TYPE value; //data in a node
};
template <class TYPE> //class template for queue
class Queue
{
private:
Node<TYPE> * P; //pointer to node
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50);
~Queue();
bool enqueue(TYPE in);
bool dequeue(TYPE& out);
bool QFront(TYPE& out);
bool QRear(TYPE& out);
int QCount();
bool isEmpty();
bool isFull();
};
We will see array implementation for
C. Linear Queue
D. Circular Queue
We assume queue of size 7.Intially Queue is empty. So
count=0
front=rear=-1;
max=7
Steps | Algorithm: bool enqueue(TYPE in) | Description
|
1 | template<class TYPE> bool Queue<TYPE>::enqueue(TYPE in) { | Design function to insert element ‘in’ to queue. This function returns true if element is inserted successfully. |
2 | if(count==max) return false | If queue is full then return false to indicate element cannot be inserted. |
3 | rear++; | If queue is not full increment rear. |
4 | if(rear==max-1) rear=0; | If rear is last element wrap to the first element of queue. |
5 | P[rear].value=in; | Insert data at rear |
6 | if(count==0) front=0 | if count is 0 it means queue is empty. Set front pointer to 0. |
7 | count++;
| Increment count |
8 | return true } | Return true to indicate successful insertion of an element in queue. |
Let us add element to circular queue. After adding an element’10’ in queue
count =1
front=rear=0
max=7
Add one more element ‘2’ to queue.
count=2
front=0
rear=1
Dequeue: Removes element from front of queue.
A priority queue is an ADT where every element has a "priority" associated with it. This priority determines the order in which they exit the queue. The elements with highest priority are removed before elements with low priority. If two elements have the same priority, they are removed according to their order in the queue.
Consider the scenario of jobs sent to a printer. These jobs are usually placed in a queue, so job that is submitted first will be printed first. But every time this is not feasible as some of the jobs are more important though they are submitted later. So these important jobs should have precedence over other jobs which are submitted earlier. Such kind of application requires priority queue.
The common operations on priority queue are
Array implementation of Priority Queue:
Let us assume array Q[] of size n.
TYPE dequeue ()
{
int max = 0;
// finding the index of the element with the highest priority
for (int i=0; i<n-1; i++)
{
if (Q[i] > Q[max])
{
max = i;
}
}
TYPE maxnum = Q[max];
size--;
Q[max] = Queue[n];
return maxnum;
delete maxnum;
}
*******program for priority queue**********8
#include<iostream>
#include<conio.h>
#include<process.h>
using namespace std;
template <class TYPE>
struct Node //Node declaration
{
TYPE value; //data in a node
};
class Queue
{
private:
Node<TYPE> * P; //
int count;// number of elements present in queue
int max; // maximum queue size
int front; //index of element at front
int rear // index of element at rear
public:
Queue(int size=50)
{ max = x;
front=-1;
rear=-1;
count=0
P = new TYPE[max];
}
~Queue();
bool enqueue(TYPE in);
TYPE dequeue();
bool isEmpty();
bool isFull();
};
template <class TYPE>
bool Queue<TYPE>:: isEmpty()
{
return (count==0);
}
template <class TYPE>
bool Queue<TYPE>::isFull()
{
return (rear==(max-1));
}
template <class TYPE>
bool Queue<TYPE>:: enqueue(TYPE in)
{
if(isFull())
return false;
rear++;
P[rear].value=in;
return true;
if(count==0)
front=0;
count++;
return true;
}
template <class TYPE>
TYPE Queue<TYPE>::deQueue()
{
if(isEmpty())
cout<<”Queue is empty”;
int m = 0; { { return maxnum; delete maxnum;
|
|
|
|
|
} |
template <class TYPE>
void Queue<TYPE>:: display()
{
for(int i=front;i<=rear;i++)
{
cout<<P[i]<<" <-- ";
}
cout<<endl;
}
}
void main(){
Queue<int> Q; //create queue of integers
int ch;
int x,flag;
do{
cout<<"\nEnter your choice:\n1.enqueue\n2.dequeue\n3.isfull\n4.isempty\5.display\n6.exit"<<endl;
cin>>ch;
switch(ch){
case 1:
cout<<”Enter element to be inserted”;
cin>>x;
flag=Q.enqueue(x)
if(flag==0)
cout<<"The queue is full"<<endl;
else
cout<<”element is inserted ";
break;
case 2:
TYPE T;
T=Q.dequeue();
cout<<”Deleted element is”<<T;
break;
case 3:
flag=Q.isFull();
if(flag==1)
cout<<Queue is full<<endl;
else
cout<<"queue is not full"<<endl;
break;
case 4:
flag=Q.isEmpty();
if(flag==1)
cout<<Queue is empty<<endl;
else
cout<<"queue is not empty"<<endl;
case 5:
Q.display();
break;
case 6:exit(1);
}
}while(ch);
getch();
}
enqueue() − add (store) an item to the queue.
dequeue() − remove (access) an item from the queue.
Few more functions are required to make the above-mentioned queue operation efficient. These are −
peek() − Gets the element at the front of the queue without removing it.
isfull() − Checks if the queue is full.
isempty() − Checks if the queue is empty.
In queue, we always dequeue (or access) data, pointed by front pointer and while enqueing (or storing) data in the queue we take help of rear pointer.
Let's first learn about supportive functions of a queue −
peek()
This function helps to see the data at the front of the queue. The algorithm of peek() function is as follows −
Algorithm
begin procedure peek
return queue[front]
end procedure
Implementation of peek() function in C programming language −
Example
int peek() {
return queue[front];
}
isfull()
As we are using single dimension array to implement queue, we just check for the rear pointer to reach at MAXSIZE to determine that the queue is full. In case we maintain the queue in a circular linked-list, the algorithm will differ. Algorithm of isfull() function −
Algorithm
begin procedure isfull
if rear equals to MAXSIZE
return true
else
return false
endif
end procedure
Implementation of isfull() function in C programming language −
Example
bool isfull() {
if(rear == MAXSIZE - 1)
return true;
else
return false;
}
isempty()
Algorithm of isempty() function −
Algorithm
begin procedure isempty
if front is less than MIN OR front is greater than rear
return true
else
return false
endif
end procedure
If the value of front is less than MIN or 0, it tells that the queue is not yet initialized, hence empty.
Here's the C programming code −
Example
bool isempty() {
if(front < 0 || front > rear)
return true;
else
return false;
}
Enqueue Operation
Queues maintain two data pointers, front and rear. Therefore, its operations are comparatively difficult to implement than that of stacks.
The following steps should be taken to enqueue (insert) data into a queue −
Step 1 − Check if the queue is full.
Step 2 − If the queue is full, produce overflow error and exit.
Step 3 − If the queue is not full, increment rear pointer to point the next empty space.
Step 4 − Add data element to the queue location, where the rear is pointing.
Step 5 − return success.
Insert Operation
Sometimes, we also check to see if a queue is initialized or not, to handle any unforeseen situations.
Algorithm for enqueue operation
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue() in C programming language −
Example
int enqueue(int data)
if(isfull())
return 0;
rear = rear + 1;
queue[rear] = data;
return 1;
end procedure
Dequeue Operation
Accessing data from the queue is a process of two tasks − access the data where front is pointing and remove the data after access. The following steps are taken to perform dequeue operation −
Step 1 − Check if the queue is empty.
Step 2 − If the queue is empty, produce underflow error and exit.
Step 3 − If the queue is not empty, access the data where front is pointing.
Step 4 − Increment front pointer to point to the next available data element.
Step 5 − Return success.
Remove Operation
Algorithm for dequeue operation
procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure
Implementation of dequeue() in C programming language −
Example
int dequeue() {
if(isempty())
return 0;
int data = queue[front];
front = front + 1;
return data;
}
Reference Books
1. Algorithms, Data Structures, and Problem Solving with C++”, Illustrated Edition by Mark Allen Weiss, Addison-Wesley Publishing Company.
2. “How to Solve it by Computer”, 2nd Impression by R.G. Dromey, Pearson Education.
3. “Fundamentals of Data Structures”, Illustrated Edition by Ellis Horowitz, Sartaj Sahni, Computer Science Press.
