Unit 3

Development Of Algorithms

3.1                       Notations and Analysis

To express the running time complexity of algorithm three asymptotic notations are available. Asymptotic notations are also called as asymptotic bounds. Notations are used to relate the growth of complex function with the simple function. Asymptotic notations have domain of natural numbers. These notations are as follows

1. Big-oh notation : Big-oh notations can be express by using ‘o’ symbol. This notation indicates the maximum number of steps required to solve the problem. This notation expresses the worst case growth of an algorithm. Consider the following diagram in which there are two functions f(x) and g(x). f(x) is more complex than the function g(x).

Fig. 3.7

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always greater than f(n).

Now f(n)=Og(n)if there is some constant ‘c’ and some initial value ‘n0’. Such that f(n)<=c*g(n) for all n>n0

In the above expression ‘n’ represents the input size

f(n) represents the time that algorithm will take

f(n) and g(n) are non-negative functions.

Consider the following example

Fig. 3.8

In the above example g(n) is ‘’n’ and f(n) is ‘2n+1’ and value of constant is 3. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always greater than f(n) for constant ‘3’. We can write the conclusion as follows

f(n)=O g(n)    for constant ‘c’ =3 and ‘n0’=1

Such that f(n)<=c*g(n) for all n>n0

2. Big-omega notation : Big-omega notations can be express by using ‘Ω’ symbol. This notation indicates the minimum number of steps required to solve the problem. This notation expresses the best case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.9

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c(n) which bound function f(n) at some point n0. Beyond the point ‘n0’ function c*g(n) is always smaller than f(n).

Now f(n)=Ωg(n)if there is some constant ‘c’ and some initial value ‘n0’. Such that c*g(n) <= f(n)for all n>n0

In the above expression ‘n’ represents the input size

f(n) represents the time that algorithm will take

f(n) and g(n) are non-negative functions.

Consider the following example

In the above example g(n) is ‘2n’ and f(n) is ‘2n-2’ and value of constant is 0.5. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c*g(n) is always smaller than f(n) for constant ‘0.5’. We can write the conclusion as follows

f(n) = Ω g(n)    for constant ‘c’ =0.5 and ‘n0’=2

Such that  c*g(n)<= f(n) for all n>n0

Fig. 3.10

Big-theta notation : Big-theta notations can be express by using ‘Ɵ’ symbol. This notation indicates the exact number of steps required to solve the problem. This notation expresses the average case growth of an algorithm. Consider the following diagram in which there are two functions f(n) and g(n). f(n) is more complex than the function g(n).

Fig. 3.11

In the above diagram out of two function f(n) and g(n), more complex function is f(n), so need to relate its growth as compare to simple function g(n). More specifically we need one constant function c1 and c2 which bound function f(n) at some point n0. Beyond the point ‘n0’ function c1*g(n) is always smaller than f(n) and c2*g(n) is always greater than f(n).

Now f(n) =  g(n) if there is some constant ‘c1 and c2’ and some initial value ‘n0’. Such that c1*g(n) <= f(n)<=c2*g(n)for all n>n0

In the above expression ‘n’ represents the input size

f(n) represents the time that algorithm will take

f(n) and g(n) are non-negative functions.

f(n) =  g(n) if and only if f(n)=O g(n) and f(n)=Ω g(n)

Consider the following example

Fig. 3.12

In the above example g(n) is ‘2n’ and f(n) is ‘3n-2’ and value of constant c1 is 0.5 and c2 is 2. The point where c*g(n) and f(n) intersect is ‘’n0’. Beyond ‘n0’ c1*g(n) is always smaller than f(n) for constant ‘0.5’ and c2*g(n) is always greater than f(n) for constant ‘2’. We can write the conclusion as follows

f(n)=Ω g(n)    for constant ‘c1’ =0.5 , ‘c2’ = 2 and ‘n0’=2

Such that  c1*g(n)<= f(n)<=c2*g(n) for all n>n0

3.2                       Storage structures for arrays-sparse matrices

3.3                       Stacks and Queues: Representations and applications

Stack

Stack is a list of elements in which insertion and deletion of elements can be done only at one end called as top of stack.

To construct a stack we insert element from top of stack.

The operation of inserting an element to stack is called as push and the operation of deleting an element from a stack is called as pop.

Imagine stacking a set of books on top of each other, we can push a new book on top of the stack, and we can pop the book that is currently on the top of the stack.

We cannot add to or remove the book from middle of the stack.

Book can only be added to the top and the only book that can be taken out of the stack is the most recently added one; Thus stack is a "Last In First Out" (LIFO) data structure.

ADT of Stack

An ADT is a collection of data and associated operations for manipulating that data. Stack ADT contains following data members and member functions.

Data members:   1. Top: Index of top of stack.

2. A[size]: Array to hold elements of stack:

Member Functions:

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.

2.  Insert element in Stack: push()

3.Remove element from stack: pop()

4.Find top of stack(tos):peek

5.Check if the stack is empty: isEmpty()

6. Check if the stack is full: isFull()

7.Find total number of elements in stack: stackcount()

Destroy stack:~stack()

Stack is destroyed using destructor.

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.

1. Reversing data
2. Parsing
3. Expression evaluation
4. Expression conversion

1. 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

A=

Fig. Original Array

After reversing array becomes

A=

Algorithm to reverse list of integers is as follows.

Another application of reversing data is conversion of decimal number to binary number. Algorithm for conversion of decimal to binary number is as follows.

***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.

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++.

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

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

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+

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

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

Infix to Postfix

Infix to Prefix

Postfix to Infix

Postfix to prefix

Prefix to Infix

Prefix to Postfix

Infix to Postfix

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

Hence Postfix expression is 459*1/+

Eg.2 Convert (2+4)*(5-6)/((1-2)*(9+2)) to Postfix expression.

Eg.3:Convert the following arithmetic expression into postfix

A+(B*C-(D/E-F)*G)*H MAY 2007

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

2. A*(B+C)/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( ) ;

}

Infix to Prefix

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

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

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( ) ;

}

Postfix to Infix

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*

Hence resultant infix expression is ((a*b)+(c*d))*e

Eg.2:Convert the following postfix expression to infix using stack.

Abcde^^*- May 2006

Hence resultant expression is a-b*c^(d^e)

Postfix to prefix

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

Hence resultant prefix expression is -a*b^c^de

Prefix to Infix

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

Hence resultant infix expression is (A+B)/(C-D)+E

Prefix to Postfix

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

Hence resultant postfix expression is AB+/CD-E+

Queue

ADT of Queue

A Queue is a linear list in which data is inserted at one end called as rear and deleted from other end called as front. Queue removes elements in the same order in which they were inserted i.e. element inserted first is removed first. Hence they are called as First-in-First out( FIFO) data structure.

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 check out 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.

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.

Now let us add an element in a queue. So queue becomes

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

Adding one more element ‘C’ in queue

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.

Removing ‘B’ and ‘C’ we get

Now queue is empty. If we try to remove elements from queue, queue underflow occurs.

Operations on Queue:

Bool enqueue(TYPE in): Insert elements at rear of queue.

Bool dequeue(TYPE  & out): Remove elements from front of queue.

Bool Front(TYPE& out): Determines element at the front of queue.

Bool Rear(TYPE& in): Determines element at the rear of queue.

Int Count():Determines total number of elements present in queue.

Bool isEmpty():Determines if queue is empty.

Bool isFull():Determines if queue is full.

Array Implementation of Queue

Template <class TYPE>

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

1. Linear Queue

2. Circular Queue

2.9.1 Array implementation for Linear Queue

Algorithms:

Create queue: Queue(int size)

We assume queue of size 5.Initially queue is empty. So

Count=0

Front=rear=-1

Max=5

Data
       Index        0  1  2   3  4

Enqueue: Insert element in queue

Let us add element ’10’ to queue. After adding an element in queue

Count =1

Front=rear=0

Max=5

       Data

Index         0  1     2    3      4

Front     rear

Add one more element ‘20’ to queue.

Count =2

Front=0

Rear=1

       Data

Index         0  1     2    3      4

Front          rear

Dequeue: Removes element from front of queue.

We continue with same example.

Count =2

Front=0

Rear=1

       Data

Index         0  1     2    3      4

Front          rear

Elements can be deleted only from front. Deleting an element ‘10’ from queue we get

Count =1

Front=1

Rear=1

       Data

Index         0  1     2    3      4

Front rear

Now queue has only one element(20). Deleting it we get

Count=0

Front=rear=-1

Data
       Index        0  1  2   3  4

QFront: Returns element at front of Queue.

QRear: Returns element at rear of Queue.