DS chapter 2.ppt................................

ppt

1. THE STACK
Def:
A stack is a special type of data structure, where elements
are inserted from one end and elements are deleted from the
same end.
The position from where elements are inserted and from
where elements are deleted is called top of the stack.
Stack is also called as Last In First Out(LIFO) data
structures.

2. Stack operations:
1. Push( Inserting an element on top of the stack)
2. Pop(Deleting an element from top of the stack)
3. Display(Display contents of stack).

3. Push Operation:
  Inserting an element into the stack is called push
operation.
  Only one item is inserted at a time & item has to be
inserted only from top of the stack.
Empty Stack Stack With elements

4 4
3 3 top
2 2
1 1
0 0
top = -1
12
05
15
24

4. Inserting an element to stack : (push operation )
4 4 4 4
3 3 3 3
2 2 2 top 2
1 2 top 1 1

0 top 0 0 0
top=-1
4 top 4
top 3 3
2 2
1 1
0 0
* If we try to insert one more element it results in a “ overflow of
Stack”
10
40
30
20
10
20
10
30
20
10
50
40
30
20
10

5. // C function for Push Operation.
 
void push() //function ---1
 {
/* check for overflow of stack */
  if (top == stack_size-1)
{
printf(“ stack overflow);
  return;
}
top = top+1;
S[top] = item;
  }

6. Pop operation:
 
Deleting an element from the stack is called
“ Pop operation”.
 
Only one item is deleted from the stack
and the item has to be deleted only from top of the stack.

7. Deleting an element to stack : (pop operation )
top 4 4 4 4
3 top 3 3 3
2 2 top 2 2
1 2 1 top 1

0 0 0 0
4 4
3 3
2 2
1 1
top 0 0
top = -1
* If we try to delete one more element it results in a “ underflow of Stack”
10
40
30
20
10
20
10
30
20
10
50
40
30
20
10

8. // C function to delete an item from stack.
 
int pop() //function----2
{
int item_deleted;
if (top == -1)
{
printf(“ Stack Underflow “);
return 0;
}
item_deleted = S[top--];
return item_deleted;
  }

9. Display stack items:
  The contents of the stack are displayed from the bottom
to top.
 // C function to display the contents of stack
  Void display() //function----3
 {
int i;
if ( top == -1 )
{ Printf(“ stack is empty”);}
for( i=0; i<=top; i++ )
{
printf(“%d”, S[i]);
}
}

10. // C program to implement stack using arrays;
 
#include <stdio.h>
#include < process.h>
#define STACK_SIZE 5;
 
int top;
int s[10];
int item;
 
//function ---1
//function----2
//function----3

11. Void main()
{
int item;
int item_deleted;
int choice;
 
top = -1;
for( ; ; )
  {
printf(“1. push, 2. pop, 3. Display, 4. Exit”);
printf(“enter the choice”);
Scanf(“%d”,&choice);

12. Switch(choice)
{
Case 1:
printf(“ Enter the item to be inserted”);
Scanf(“%d”, &item);
push();
break;
Case 2:
item_deleted = pop();
if (item_deleted == 0)
printf(“stack is empty”);
else
printf(“Item deleted= %d”, item_deleted);
break;

13. Case 3:
display();
break;
default:
exit(0);
}
}
}
 

14. Applications of stack:
 
The various applications in which stacks are used are :
 
1.Conversion of expressions
2.Evaluation of expressions
3.Recursion

15. Conversion of expressions
 
 
The sequence of operators and operands that reduces to a
single value after evaluation is called an expression.
 
There are three different types of expressions:
Prefix Expression:
Postfix expression:
Infix expression:

16. Infix expression:
In an expression, if an operator is in the b/w two
operands, the expression is called an infix expression.
Ex: a+b, (a-b), (a+b*c-(d*f))
Postfix expression:
In an expression, if an operator follows the two
operands ( operator comes after the two operands ) , the expression
is called “postfix expression”. It is also called as
“Suffixexpression”.
Ex: ab+, ab-, (a+b*c) ab*c+
 Prefix Expression:
In an expression, if an operator precede the two
operands(i.e., operator comes before the two operands), the
expression is called “Prefix Expression”.
Ex: +ab, -ab….
 

17. Precedence and Associativity of the operator :
While evaluating the expressions, some expressions are given
precedence over other expression and are evaluated first and some
are evaluated later.
“ The rules that determines the order in which the
different operators are evaluated are called precedence rules Or
precedence operators”.
 
 
 Ex : 6 * (2 + 3) – 5 6 * (2 + 3) – 5
6 * 5 – 5 6 * 5 – 5
30 – 5 6 * 0
25 0

18. 
The below table shows arithmetic operators along
with priority values, 
Description Operator Priority
Exponentiation $ 6
Multiplication * 4
Division / 4
Mod % 4
Addition + 2
Substraction - 2

19. Associativity of the operator :
“ The order in which the operators with same
precedence are evaluated in an expression is called associativity of
the operator”.
In such cases the precedence rules are considered with
associativity.
The associativity can be classified into two types,
left to right associative ( left associative)
right to left associative (right associative).

20. left to right associative ( left associative) :
In an expression, if there are two or more operators
having the same priority and are evaluated from left to right , then
the operators are called left associative operators.
Right to left associative (right associative) :
In an expression, if there are two or more operators
having the same priority and are evaluated from right to left , then
the operators are called right associative operators.
 

21. The below table shows arithmetic operators along with
priority values and there associativity. 
Description Operator Priority Associativity
Exponentiation $ 6 Right to left
Multiplication * 4 Left to right
Division / 4 Left to right
Mod % 4 Left to right
Addition + 2 Left to right
Subtraction - 2 Left to right

22. Conversion from Infix to Postfix expression :
Manual method:
Ex: 1) (( A+(B-C)*D)^E+F)
 Sol: (( A+(B-C)*D)^E+F) T1 = B-C  BC-
T1
 
(( A+T1*D)^E+F) T2 = T1*D T1D*
T2 
(( A+T2)^E+F) T3 = A+T2 AT2+
T3
 
T3^E+F T4 = T3^E T3E^
T4
T4+F
T4F+

23. Now substitute the values of T4,T3,T2,T1 we get postfix
expression,
 T4F+ T4 = T3E^
 
 T3E^F + T3 = AT2+
 
 AT2 + E^F + T2 = T1D*
 
 A T1 D * +E^F + T1 = BC-
 ABC-D*+E^F+
(( A+(B-C)*D)^E+F) = ABC-D*+E^F+

24. 2. X ^ Y ^ Z-M +N+P/Q
 
 X ^ Y ^ Z-M +N+P/Q T1 = Y^Z  YZ^
T1
 X ^ T1-M +N+P/Q T2 = X^T1  XT1^
T2
 T2-M +N+P/Q T3 = P/Q  PQ/
T3
 T2-M+N+T3 T4 = T2-M  T2M-
T4
 T4+N+T3 T5 = T4+N  T4N+
T5
 T5+T3
 T5T3+

25. By substituting the values of T5,T4,T3,T2,T1 we get postfix
expression,
 T5T3+ T5 = T4N+ and T3 = PQ/
 T4N +PQ/+ T4 = T2M-
T2M-N+PQ/+ T2 = XT1^
XT1^M-N+PQ/+ T1 = YZ^
 XYZ^^M-N+PQ/+
X ^ Y ^ Z-M +N+P/Q = XYZ^^M-N+PQ/+

26. To write a program by using stack data structure,
Let us use two precedence function F and G. The
function F contains the precedence values of symbols on top of
the stack and function G contains the precedence values of
symbols in the input string.
Shown in below table,( infix to postfix )
SymbolsStack precedence
“F”
Input precedence
“G”
Associativity
+ , - 2 1 Left
* , / 4 3 Left
$ or ^ 5 6 Right
Operands 8 7 Left
( 0 9 Left
) - 0 -
# -1 -

27. General procedure to convert from infix to postfix form :
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j = 0
Step 2 :
As long as the precedence value of the symbol on top of
the stack is greater than the precedence value of the current input
symbol, pop an item from the stack and place it in the postfix
expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}

28. Step 3 :
Once the condition in while loop is failed, if the
precedence of the symbol on top of the stack is not equal to the
precedence value of the current input symbol, push the current
symbol on to the stack. Otherwise , delete an item from the stack
but do not place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the complete execution of step 2 and step 3, pop
remaining symbols from stack to postfix expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]

29. * complete trace of the algorithm :
( A + ( B – C ) * D )
Stack S[top]Symbol F(s[top]) > G(symbol) Postfix
# #
# # ( ( -1 > 9 ) push (
#( ( A ( 0 > 7 ) push A
#(A
#(
A
(
+ ( 8 > 1 ) pop A
( 0 > 1 ) push +
A
#(+ + ( ( 2 > 9 ) push (A
#(+( ( B ( 0 > 7 ) push B A
#(+(B
#(+(
B
(
- ( 8 > 1 ) pop B
( 0 > 1 ) push -
AB
#(+(- - C ( 2 > 7 ) push CAB
#(+(-C
#(+(-
#(+(
C
-
(
) ( 8 > 0 ) pop C
( 2 > 0 ) pop –
( 0 = 0 ) pop (
Don’t place in postfix expr
ABC
ABC-

30. * complete trace of the algorithm :
( A + ( B – C ) * D )
Stack S[top]Symbol F(s[top]) > G(symbol) Postfix
#(+ + * ( 2 > 3 ) push *ABC-
#(+* * D (4 > 7) push D ABC-
#(+*D
#(+*
#(+
#(
D
*
+
(
) ( 8 > 0 ) pop D
( 4 > 0 ) pop *
( 2 > 0 ) pop +
( 0 = 0 ) pop (
Don’t place in postfix expr
ABC-D
ABC-D*
ABC-D*+
# # ABC-D*+

31. /* C function for stack precedence
  int F (char symbol) function 1
{
Switch (symbol)
{
 Case ‘+’ :
Case ‘-‘ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}

32. /* C function for input precedence
  int G (char symbol) function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘(’ : return 9;
Case ‘)’ : return 0;
default : return 7;
}
}

33. /* C function to convert from infix into postfix expression.
 
void infix_postfix(char infix[], char postfix[])
{
//function 3
int top; int j; int I;
char s[30]; char symbol;
top=-1; Step : 1
S[++top]= ‘#’;
j=0;
for(i=0; i<strlen(infix); i++)
{
Symbol=infix[i];

34. /* if stack precedence greater , remove symbol from
stack and place into postfix. */
 
while ( F(s[top]) > G(symbol) )step : 2
{
postfix[j] = s[top--];
j++;
}
 
if ( F(s[top]) != G(symbol) )step : 3
S[++top] = symbol;
else
top--;
}

35. /* pop remaining symbols and place them in
postfix expression
 
while ( s[top] != ’#’ ) step : 4
{
postfix[j++] = s[top--];
}
 
postfix[j]=’\0’;
}

36. // C program to convert an infix expression to postfix expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char postfix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_postfix ( infix, postfix);
printf (“ The postfix expression is “ );
printf (“%s”,postfix);
}

37. To write a program by using stack data structure,
Let us use two precedence function F and G. The function F
contains the precedence values of symbols on top of the stack and
function G contains the precedence values of symbols in the input
string.
Shown in below table,( infix to prefix )
SymbolsStack precedence
“F”
Input precedence
“G”
Associativity
+ , - 1 2 Left
* , / 3 4 Left
$ or ^ 6 5 Right
Operands 8 7 Left
( - 0 Left
) 0 9 -
# -1 - -

38. General procedure to convert from infix to prefix form :
Step 1 :
initialize top and stack of top
top = -1
s[++top] = ‘#’
j = 0.( reverse the infix expression )
Step 2 :
As long as the precedence value of the symbol on top of the stack
is greater than the precedence value of the current input symbol, pop an
item from the stack and place it in the postfix expression.
while ( F(s[top]) > G(symbol) )
{
postfix[ j++ ] = s[ top-- ]
}

39. Step 3 :
Once the condition in while loop is failed, if the precedence of
the symbol on top of the stack is not equal to the precedence value of the
current input symbol, push the current symbol on to the stack. Otherwise
, delete an item from the stack but do not place in the postfix expression.
if ( F(s[top]) != G(symbol) )
s[++top] = symbol
else
top--;
Step 4 :
After the execution of step 2 and step 3, pop remaining symbols
from stack to postfix expression.
while ( s[top] != ‘#’ )
postfix[j++] = s[top--]
reverse the resultant expression

40. * complete trace of the algorithm :
( A + ( B – C ))= ) ) C – B ( + A (
i.e.,CB-A+ = +A-BC
Stack S[top]Symbol F(s[top]) > G(symbol) Postfix
# # ) -1 > 9 push ‘)’
#) ) ) 0 > 9 push ‘)’
#)) ) C 0 > 7 push ‘C’
#))C
#))
C
)
- 8 > 2 pop ‘C’
0 > 2 push ‘-’
C
#))- - B 1 > 7 push ‘B’ C
#))-B
#))-
#))
B
-
)
( 8 > 0 pop ‘B’
1 > 0 pop ‘-’
0 > 0 pop ‘)’
CB
CB-
#) ) + 0 > 2 push ‘+’ CB-
#)+ + A 1 > 7 push ‘+’ CB-
#)+A
#)+
#)
A
+
)
( 8 > 0 pop ‘A’
1 > 0 pop ‘+’
0 > 0 pop ‘)’
CB-A
CB-A+

41. /* C function for stack precedence
  int F (char symbol) function 1
{
Switch (symbol)
{
 Case ‘+’ :
Case ‘-‘ : return 1;
Case ‘*’ :
Case ‘/’ : return 3;
Case ‘^’ :
Case ‘$’ : return 6;
Case ‘)‘ : return 0;
Case ‘#’: return -1;
default : return 8;
}
}

42. /* C function for input precedence
  int G (char symbol) function 2
{
Switch (symbol)
{
Case ‘+’ :
Case ‘-’ : return 2;
Case ‘*’ :
Case ‘/’ : return 4;
Case ‘^’ :
Case ‘$’ : return 5;
Case ‘(’ : return 0;
Case ‘)’ : return 9;
default : return 7;
}
}

43. /* C function to convert from infix into prefix expression.
 
void infix_prefix(char infix[], char prefix[])
{ // function 3
int top; int j; int I;
char s[30]; char symbol;
top=-1; Step : 1
S[++top]= ‘#’;
j=0;
strrev ( infix );
for(i=0; I < strlen (infix); i++)
{
Symbol=infix[i];

44. /* if stack precedence greater , remove symbol from
stack and place into prefix. */
 
while ( F(s[top]) > G(symbol) )step : 2
{
prefix[j] = s[top--];
j++;
}
 
if ( F(s[top]) != G(symbol) )step : 3
S[++top] = symbol;
else
top--;
}

45. /* pop remaining symbols and place them in
prefix expression
 
while ( s[top] != ’#’ ) step : 4
{
prefix[j++] = s[top--];
}
 
prefix[j]=’\0’;
strrev (prefix );
}

46. // C program to convert an infix expression to prefix expression
# include < stdio.h>
# include < string.h >
/* include function 1, function 2, function 3. */
void main ()
{
char infix[20];
char prefix[20];
printf (“ Enter the valid infix expression”);
scanf (“ %s ”, infix );
infix_prefix ( infix, prefix);
printf (“ The prefix expression is “ );
printf (“%s”, prefix);
}

47. Evaluation of postfix expression :
 
Algorithm:
 Step 1 : Scan the symbol from left to right.
Step 2: If the scanned symbol is an operand, push it on
to the stack.
Step 3: If the scanned symbol is an operator, pop two
elements from the stack
The first popped element is operand 2 and the
second popped element is operand1
Op2 = s[top--];
Op1 = s[top--];

48. Step 4: perform the indicated operation.
res = op1 op op2.
Step 5: push the result on to the stack.
Step 6: Repeat the above procedure till the end of the
i/p is encountered.

49. Ex: Evaluate the following postfix expression.
 
ABC-D*+E$F+ infix((A+(B-C)*D)$E+F)
with the values,
A=6, B=3, C=2, D=5, E=1, F=7.
Solution:
After substituting the values
 
632-5*+1$7+

50. Ex: Evaluate the following postfix expression.
 
 
Postfix Expression symbol
scanned
op2 op1 res = op1 op
op2
Stack
contents
632-5*+1$7+6 6
32-5*+1$7+3 6 3
2-5*+1$7+2 6 3 2
-5*+1$7+- 2 3 3 – 2 = 16 1
5*+1$7+5 6 1 5
*+1$7+* 5 1 1 * 5 = 56 5
+1$7+ + 5 6 6 + 5 = 1111
1$7+ 1 11 1
$7+ $ 1 1111 $ 1 = 1111
7+ 7 11 7
+ + 7 1111 + 7 = 1818

51. // c program to evaluate the postfix expression:
#include < stdio.h >
#include < math.h >
#include < string.h >
  double compute(char symbol, double op1, double op2)
{
switch ( symbol)
{
  Case ‘+’ : return op1+op2;
Case ‘-’ : return op1-op2;
Case ‘*’ : return op1*op2;
Case ‘/’ : return op1/op2;
Case ‘$’:
Case ‘^’: return pow(op1,op2);
} }

52. void main()
{
double s[20] , res , op1 , op2 ;
  int top, i ;
char postfix[20] , symbol ;
top = -1;
Printf(“ enter the postfix expression”);
Scanf(“%s”, postfix);
for ( i=0; i<strlen(postfix); i++ )
{

Symbol = postfix[i];

53. if ( isdigit(symbol))
S[++top]= symbol ;
else
{
op2 = s[top--];
op1 = s[top--];
res = compute(symbol, op1,op2);
S[++top] = res;
}
}
res = s[top--];
printf(“ the result is %f\n”, res);
  }

54. c program to convert a prefix expression to its equivalent
postfix expression.
 #include<stdio.h>
#include<conio.h>
#include<string.h>
void push(char item[], int *top, char s[][20])
{ *top = *top + 1;
strcpy(s[*top], item);
}
char *pop(int *top, char s[][20])
{
return s[(*top)--];
}

55. void prefix_postfix(char prefix[], char postfix[])
{
char s[20][20]; //stack to hold the postfix expression
int top; // points to topmost item
char symbol; // Symbol scanned from prefix expression
char temp[2];// To convert symbol scanned into a string
char *op1;// Holds operand 1 obtained after popping
char *op2;// Holds operand 2 obtained after popping
int i; // Index to scan each symbol from prefix
top = -1; // Stack empty state
strrev(prefix);

56. for(i=0; i<strlen(prefix); i++)
{
symbol = prefix[i]; // Obtain the next symbol
temp[0] = symbol;
temp[1] = '\0';
switch(symbol)
{
case '+' :
case '-' :
case '*' :
case '/' :
case '^' :
op1 = pop(&top, s);
op2 = pop(&top, s);

57. strcpy(postfix, op1);
strcat(postfix, op2);
strcat(postfix, temp);
push(postfix, &top, s);
break;
default:
push(temp, &top, s);
}
}
}

58. int main()
{
char prefix[20], postfix[20];
printf("Enter the prefix expression \n");
scanf("%s", prefix);
prefix_postfix(prefix, postfix);
printf("The postfix expression is %s\n", postfix);
getch();
}

59. Ex; to check whether a give string is palindrome or not using
stack.
 # include <stdio.h>
# include <string.h>
 
int is_palindrome( char str[])
{
int i, top = -1;
char s[30], stk_item;
/* push all the characters of the given string
  for( i=0; i<strlen(str); i++ )
{
S[++top]= str[i];
}

60.   /* check whether the string is palindrome or not.
 
for (i=0; i<strlen(str);i++)
{
Stk_item = s[top--];
if (str[i] != stk_item)
return 0;
}
return 1;
}

61.  
void main()
{
Char str[20];
printf(“enter string”);
Scanf(“%s”, str);
if (is_palindrome(str))
printf(“ the string is palindrome”);
else
printf(“ the string is not a palindrome”);
}

62. // c program to convert a postfix expression to its equivalent
infix expression.
#include <stdio.h>
#include<string.h>
/* include C functions implementing push and pop operations.
Void postfix_infix( char postfix[], char infix[])
{
char s[20][20] , symbol , temp[2] , op1 , op2 ;
int top , i ;
top = -1 ;

63. for ( i=0; i<strlen(postfix) ; i++ )
{
symbol = postfix[i];
temp[0] = symbol;
temp[1] = ‘\0’;
switch ( symbol )
{
case ‘+’ :
case ‘-’ :
case ‘*’ :
case ‘/’ :
case ‘^’ :
op2 = pop ( top , s );
op1 = pop ( top , s );

64. strcpy ( infix , “(“ );
strcat ( infix , op1 );
strcat ( infix , temp );
strcat ( infix , op2 );
strcat ( infix , “)” );
push (infix , top , s );
break;
default :
push ( temp , &top , s );
}
}

65. void main ( )
{
char postfix[20];
char infix[20];
printf ( “ Enter the postfix expression “ );
scanf (“%s”, postfix);
postfix_infix( postfix , infix);
printf ( “ the infix expression is %s “,infix);
}