- It’s special data structure based on LIFO (Last In First Out Concept).
- It can be implemented using One dimensional Array as well as Singly linked list.
- TOP is the external pointer points to last node element pushed.
- There are two operation which is performed on stack i.e., Push (Insertion) and Pop (Deletion).
- Push and Pop operation is performed through TOP end.( means insertion and deletion is restricted through one end i.e., TOP end)
Write an algorithm to perform push operation.
PUSH(TOP)
[ PUSH is the name of algorithm and TOP is the external pointer points to last inserted node. ]
NEW<--FREE
FREE <-- FREE --> NEXT
If NEW=NULL Then:
Write : ‘ Memory allocation errot’
Exit
[ End of If]
Read : NEW-->INFO
NEW --> NEXT <-- TOP
TOP <--NEW
END
Write an algorithm to perform pop operation.
POP(TOP)
[ POP is the name of algorithm]
If TOP = NULL Then:
Write: ‘ Stack is empty’
Exit
[ End of If]
I <-- TOP --> INFO
Write: ‘Poped element is’, TOP --> INFO
TOP <-- TOP --> NEXT
END
Write the program to perform PUSH and POP operation:
#include<stdio.h>
#include<conio.h>
struct node
{
int info;
struct node *next;
};
struct node *top=NULL;
void push(int i);
{
struct node *new;
if(new==NULL)
{
printf(“Memory allocation error\n”);
exit(0);
}
new->info=i;
new->next=top;
top=new;
}
void pop(void)
{
if(top==NULL)
{
printf(“Stack is empty”);
exit(0);
}
printf(“%d->”,top->info);
top=top->next;
}
void main()
{
int i;
char ch;
clrscr();
do
{
printf(“Enter your choice\n”);
printf(“1. PUSH\n”);
printf(“2. POP\n”);
scanf(“%d”,&choice);
switch(choice)
{
case 1:
printf(“Enter the value to push in stack\n”);
scanf(“%d”,&i);
push(i);
break;
case 2:
pop();
break;
default:
printf(“Invalid choice try again\n”);
}
printf(“Do you want to continue press ‘Y’\n);
ch=getche();
}while(ch==’Y’);
getch();
}
Algorithm to Push an element on Stack using One dimensional Array:
PUSH( S, TOP, N, ITEM )
[S is the name of Array , TOP is the current index of a STACK , N is the size of an Array, ITEM is the element to be inserted]
If TOP==N Then:
Write: ‘Overflow’
Exit
[ End of If]
TOP <--TOP+1
S[TOP]=ITEM
END
Algorithm to Pop the Stack using One dimensional Array:
POP(S, TOP)
[ S is the name of an array and TOP is the current index]
If TOP=-1 Then:
Write: ‘Underflow’
Exit
[ End of If]
I <-- S[TOP]
TOP <-- TOP-1
Return I
END
WACP to perform Push and Pop operation on Stack using One dimensional Array:
/* Function to perform push operation */
void push(int s[], int n, int *top, int i)
{
if (top==n)
{
printf(“Over flow”);
exit(0);
}
s[++top]=i;
}
/* Functio to perform pop operation */
int pop( int s, int *top)
{
int i;
if( top==-1)
{
printf(“Underflow”);
exit(0);
}
i=s[top--];
return i;
}
main( )
{
int s[8],top,item,choice;
char ch;
do
{
printf(“Enter your choice\n”);
printf(“1.Push Operation\n”);
printf(“2. Pop operation\n”);
scanf(“%d”,&choice);
switch(choice)
{
case 1: printf(“Enter the element to push\n”);
scanf(“%d”,&item);
push(s, 8,&top,item);
break;
case 2: printf(“Poped element=%d”,pop(s, &top));
break;
default: printf(“Invalid choice\n”);
}
printf(“Do you want to continue press ‘Y’\n”);
ch=getche();
}while(ch==’Y’);
getch(); }
Polish Notation:
Infix expression takes much time and scanning to evaluate in computer due to operator hierarchy and
parenthesis. so to overcome this problem French Mathematician Polish has given parenthesis free
notation. i.e., Postfix and Prefix notation.
In Postfix notation operator is placed after the operand.
And in Prefix notation operator is placed before operand.
Conversion of Infix expression into prefix and postfix notation:
Infix exp: 5*9^2/3
First place parenthesis according to operator hierarchy
((5*(9^2))/3)
Postfix Conversion:
Step 1: Conversion done from higher order operator and place the operator at the place of left parenthesis. Remove the both of parenthesis.
((5*^92)/3)
Step 2: Place the operator again at the left of parenthesis and remove according to operator hierarchy.
(*5^92/3)
Step 3:
/5*92^3
Prefix Converesion:
Step 1: Conversion done from higher order operator and place the operator at the place of right parenthesis. Remove the both of parenthesis.
((5*92^)/3)
Step 2: Place the operator again at the Right of parenthesis and remove according to operator hierarchy.
(592^*/3)
Step 3:
592^*3/
Algorithm to Convert an INFIX expression to POSTFIX expression using stack:
INFIX_TO_POSTFIX(I)
[ I is the INFIX expression]
STEP 1: Add ‘) ‘ at the end of I. and push ‘ ( ‘ on to the stack.
STEP 2: Repeat scanning the characters of I from left to right while stack is not empty
STEP 2(a): If the scanned character is an operand Then:
Add it to P (PostFix expression)
[ End of If]
STEP 2(b): If the scanned character is ‘(‘ Then:
Push it on the stack
[End of If]
STEP 2(c): If the scanned character is’)’ Then:
Repeatedly POP the stack till ‘(‘ , add the poped operators to P
and remove ‘(‘ from the stack
[End of If]
STEP 2(d): If the scanned character is operator Then:
Check the top of stack repeatedly for higher or same hierarchy of operators till lower hierarchy. if any pop them and add to P
and push the scanned character onto Stack
[End of If]
[ End of While]
STEP 3: Write: P
STEP 4: EXIT
Convert the Infix exp. I: (A+B) / ( C-D ) ^ E + F * G
Add ) to I at the end, PUSH ( on to the stack.
[ P is a POSTFIX expression]
Repeat Scanning P from left to right While Scanned Character != #
If Scanned character = operand Then:
STACK[TOP] <-- operand
TOPßTOP+1
Else
B<-- STACK[TOP], TOP<--TOP-1
A<-- STACK[TOP], TOP<--TOP-1
RES<--A operator B
STACK[TOP] <--RES
[ End of If]
[End of While]
VAL <-- STACK[TOP]
Write: ‘ Value of postfix expression’, VAL
END
Start scanning the exp. from left to right.
S. NO.
|
Scanned Character
|
STACK
|
POSTFIX exp P
|
1.
|
(
|
(
|
|
2.
|
(
|
((
|
|
3.
|
A
|
A
|
|
4.
|
+
|
((+
|
A
|
5.
|
B
|
((+
|
A B
|
6.
|
)
|
(
|
A B +
|
7.
|
/
|
( /
|
A B +
|
8.
|
(
|
( / (
|
A B +
|
9.
|
C
|
( / (
|
A B + C
|
10.
|
-
|
( / ( -
|
A B + C
|
11.
|
D
|
( / ( -
|
A B + C D
|
12.
|
)
|
( /
|
A B + C D -
|
13.
|
^
|
( / ^
|
A B + C D -
|
14.
|
E
|
( / ^
|
A B + C D – E
|
15.
|
+
|
( +
|
A B + C D – E ^ /
|
16.
|
F
|
( +
|
A B + C D – E ^ / F
|
17.
|
*
|
( + *
|
A B + C D – E ^ / F
|
18.
|
G
|
A B + C D – E ^ / F * +
|
Evaluation of POSTFIX expression using STACK.
POSTFIXEVAL(P)[ P is a POSTFIX expression]
Repeat Scanning P from left to right While Scanned Character != #
If Scanned character = operand Then:
STACK[TOP] <-- operand
TOPßTOP+1
Else
B<-- STACK[TOP], TOP<--TOP-1
A<-- STACK[TOP], TOP<--TOP-1
RES<--A operator B
STACK[TOP] <--RES
[ End of If]
[End of While]
VAL <-- STACK[TOP]
Write: ‘ Value of postfix expression’, VAL
END
Example: Evaluate the Postfix exp 5 6 * 3 + 5 –
Soln : Add # at the end of Postfix expressionStart scanning the exp. from left to right.
S.NO.
|
Scanned
Character
|
STACK
|
1.
|
5
|
5
|
2.
|
6
|
5,
6
|
3.
|
*
|
30 // (5*6)
|
4.
|
3
|
30,
3
|
5.
|
+
|
33 // (30+3)
|
6.
|
5
|
33,
5
|
7.
|
-
|
28 // (33-5)
|
