The
Stack
Definition
The stack is an ordered
collection of items into which items may be inserter and from which items may
be deleted from one end which is known as top of the stack i.e. a single end of
the stack is designated as the stack top.
So, the above
definition specifies that-
-
New items are
inserted on the top of the stack and
-
Deleted from the
top of the stack.
This means that data
can be added or removed only from top of the stack. So the stack is called a list-in-first-out (LIFO) list.
Stack as an ADT
An ADT is the
mathematical model that contains set of values and functions that operates on
those values without specifying the detail of those functions. The
specification of stack ADT is given below.
AbstractDataType
Stack
{
Instances: ordered finite collections of
zero or more elements from a given base type; the right extreme of the sequence
is the top
Operations
CreateStack
Input: nothing
Output: a new
stack data object containing the empty sequence
DeleteStack
Input: an
existing stack data object
Output: nothing
Effect: destroys
the object given in input
EmptyStack
Input: a stack
data object
Output: boolean value; TRUE if the stack
contains the empty sequence, FALSE otherwise
StackSize
Input: a stack
data objcect
Output: an integer value identifying the
length of the sequence currently stored in the input data object
StackTop
Input: a stack
data object
Output: the element in position in the
top position of the sequence stored in the stack
PrintStack
Input: a stack
data object
Output: prints on the screen the
sequence of elements currently stored in the input data object.
Push
Input: a stack
data object; an element of the base type
Output: a
boolean indicating whether the operation was successful
Effect: the
element is added to the sequence in the stack, in the top position
Pop
Input: a stack
data object
Output: a
boolean indicating whether the operation was successful
Effect: the
element in the top position in the sequence in the stack is removed.
}
In the above ADT definition
1. StackSize
used to compute the size of a stack (i.e., the number of elements present in a
given stack)
–Preconditions:
receives a stack as input
–
Postconditions: produces a number representing the count of the elements in the
stack
2. EmptyStack
used to verify whether a given stack is empty or not
–
Preconditions: receives a stack as input
– Postconditions: produces true (i.e.,
1 in C) if the stack is empty, false (i.e., 0 in C) otherwise
3. StackTop
returns the information which is currently stored as top element in the stack.
–
Preconditions: receives a stack s
– Postconditions: if the stack is not
empty, then it returns the first element in the stack s, otherwise it
gives an error
4. Push used to insert a new element as the top
of the stack.
–
Preconditions: receives as input a stack s, and an element x
– Postconditions: if x is of the
correct type (i.e., it has the same type as all the other elements in s),
and then the stack is modified introducing the element x in the first
position of the stack; otherwise it returns an error
5. Pop removes the top element from the stack.
–
Preconditions: receives as input a stack s
– Postcondtions: if the stack is not
empty, then the stack is modified by removing the element in first position in s;
otherwise it returns an error
Operation
on Stack
The possible operations
on stack are
1.
Create empty
stack.
2.
Isfull: To check
whether the stack is full or not.
3.
Isempty: To
check whether the stack is empty or not.
4.
Push operation:
To push element in the stack (if stack is not full in case of implementing
stack using array).
5.
Pop operation:
To access and remove the top element of the stack.
6.
Print the entire
stack.
Stack implementation
Stack can be
implemented as
-
Array
implementation (static implementation)
-
Linked list
implementation using pointer(Dynamic implementation)
Algorithm to check
whether the stack is full or not?
When Stack is empty
In stack to check
whether the stack is full or not, we use isfull function. This function returns
true if the stack is full and returns false otherwise. This function takes
pointer to stack as an argument.
Algorithm
1.
Is full( stack
s)
2.
If the top of
the stack is max-1
3.
return true
4.
Otherwise return
false
int full(stack *s)
{
if(s->top == MAX-1) //Stack is Full
return(1);
else
return(0);
}
Check whether stack is empty or not
To check the stack is
empty or not, we use empty function. This function takes stack variable as
argument and returns true if the stack is empty and false otherwise.
Algorithm
Isempty(stack s)
If the top of the stack is -1
Then return true
Otherwise return false
Empty module for
checking whether stack is empty or not
int empty(stack *s)
{
if(s->top == -1) //Stack is Empty
return(1);
else
return(0);
}
Push an element
in to the stack
This function is used to insert an element into the
top of the stack.
Algorithm
1.
Check whether
the stack is full or not
2.
If true
a.
Display stack is
full
3.
Else
a.
Increment the
top of the stack
b.
Push an element
into the top
C function
Void
push(stack *s, int x)
{
If(s->top==SIZE-1)
{
Printf(“Stack
is full”);
Exit(0);
}
Else
{
s->top++;
s->data[s->top]=x;
}
}
Pop operation on
stack
This function is used to remove the top element from
the stack
Algorithm
1.
Check whether
the stack is empty or not
2.
If true
a.
Display stack is
empty
b.
Exit
3.
Else
a.
Remove top
element from the stack
b.
Decrease top by
1
c.
Return top
element
C function
Int pop(stack *s)
{
int
x;
if(s->top==-1)
{
printf(“Stack
is empty”);
exit(0);
}
else
{
X=s->data[s->top];
s->top--;
}
return x;
}
Array
implementation of stack
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
#define SIZE 5
Void main()
{
int
stack[SIZE];
int
data, choice, I;
int
top=0;//stack is empty
while(1)
{
Print(“\n1.
Push data”);
Print(“\n2.
Pop data”);
Printf(“\n3.
View all data”);
Printf(“\n4.
Exit”);
Printf(“Enter
your choice”);
Scanf(“%d”,
&choice);
Switch(choice)
{
Case
1:
if(top<SIZE)
{
printf(“Enter
any data”);
scanf(“%d”,&data);
stack[top]=data;
top++;
}
else
printf(“Stack is already full”);
break;
case 2:
if(top>0)
{
top--;
printf(“Deleted data item is:%d”,
stack[top]);
}
else
printf(“Stack is empty”);
break;
case 3:
if(top==0)
printf(“Stack is empty”);
else
{
for(i=top-1;i>=0;i++)
{
printf(“\nStack[i]th
element is:%d”, stack[i]);
}
}
break;
case 4:
exit(0);
default:
printf(“Enter your choice from 1 to 4”);
}
}
getch();
}
Application of
stack
1.
Balancing
symbols
2.
Infix to postfix
conversion
3.
Infix to prefix
conversion
4.
Expression
evaluation
a.
Prefix
expression evaluation
b.
Postfix
expression evaluation
5.
Recursion
1.
Balancing symbols
Stack is used to
check whether the given expression is valid or not by checking the number of
opening and closing braces used in the given expression.
Algorithm
1.
Scan one
character at a time from left to right from the given expression
2.
If the scan
character is [ or { or ( push it into the stack.
3.
If scan
characters are other than braces leave it and scan remaining characters
4.
If the scanned
character is ) or } or ]
a.
Pop the matching
( or { or [ character from the top of the stack
5.
After all
character scanned,
a.
If the stack is
empty, the given expression is valid
b.
Else given
expression is not valid.
e.g.
1. Check whether the given expression is balanced or
not
{x+(y-[a+b])*c-[(d+e)]}
Step
|
Scan char
|
Opstack
|
1
|
{
|
{
|
2
|
X
|
{
|
3
|
+
|
{
|
4
|
(
|
{(
|
5
|
Y
|
{(
|
6
|
-
|
{(
|
7
|
[
|
{([
|
8
|
A
|
{([
|
9
|
+
|
{([
|
10
|
B
|
{([
|
11
|
]
|
{(
|
12
|
)
|
{
|
13
|
*
|
{
|
14
|
C
|
{
|
15
|
-
|
{
|
16
|
[
|
{[
|
17
|
(
|
{[(
|
18
|
D
|
{[(
|
19
|
+
|
{[(
|
20
|
E
|
{[(
|
21
|
)
|
{[
|
22
|
]
|
{
|
23
|
}
|
Null
|
Here,
in this example after the scanning of all characters, the stack is empty. So
the expression is balanced.
Expression
Any arithmetic expression can be represented in
three different ways as:
Infix, Prefix and Postfix,
Infix expression
It is the traditional way of writing arithmetic
expression where an operator is placed in between its two operands that means
(operand1 operator operand2>
Eg. A+b, a-b, a/b, a%b etc.
Prefix
expression
In prefix notation an operator is placed before its
two operands. It is also known as Polish notation. That means <operator
operand1 operand2>
Eg. +ab, -ab, /ab, %ab etc.
Postfix
expression
In postfix notation an operator is placed after the
operand. It is also known as reverse polish notation. That means <operand1
operand2 operator>
Eg. Ab+,ab-, ab/ ab% etc.
Algorithm to
convert infix expression to prefix expression
1.
Scan one
character at a time from right to left.
2.
Repeat while
there is data
a.
If ‘)‘- push it
into the stack
b.
If operand,
append it into the prefix string.
c.
If operator-
i.
If stack is
empty, push into opstack
ii.
If not-
1.
Repeat till precedence
of tos char>= scan char
2.
Pop and append
into prefix string
3.
Push into
opstack
d.
If ‘(‘ is found
i.
Pop and push
into prefix string until matching ‘)’ found and ignore both.
3.
Pop and append
into prefix string until stack is empty
4.
Pop and print
from prefix stack until stack is empty.
e.g.
Convert following infix expression to prefix
A+(B*C-(D/E$F)*G)*H
S. no.
|
Scan char
|
Prefix
String
|
Opstack
|
1
|
H
|
H
|
|
2
|
*
|
H
|
*
|
3
|
)
|
H
|
*)
|
4
|
G
|
GH
|
*)
|
5
|
*
|
GH
|
*)*
|
6
|
)
|
GH
|
)*)*
|
7
|
F
|
FGH
|
)*)*
|
8
|
$
|
FGH
|
$)*)*
|
9
|
E
|
EFGH
|
$)*)*
|
10
|
/
|
$EFGH
|
/)*)*
|
11
|
D
|
D$EFGH
|
/)*)*
|
12
|
(
|
/D$EFGH
|
*)*
|
13
|
-
|
*/D$EFGH
|
-)*
|
14
|
C
|
C*/D$EFGH
|
-)*
|
15
|
*
|
C*/D$EFGH
|
*-)*
|
16
|
B
|
BC*/D$EFGH
|
*-)*
|
17
|
(
|
-*BC*/D$EFGH
|
*
|
18
|
+
|
*-*BC*/D$EFGH
|
+
|
19
|
A
|
A*-*BC*/D$EFGH
|
+
|
20
|
NULL
|
+A*-*BC*/D$EFGH
|
Therefore the
resulting postfix expression is:
+A*-*BC*/D$EFGH
Algorithm to
evaluate the prefix expression
1.
Scan prefix
string from right to left.
2.
If scan
character is operand, push it into stack
3.
If operator, pop
2 operand from the stack. First one is operand2 and second is operand1.
4.
Perform result =
operand1 operator operand1
5.
Push result onto
the stack.
6.
Repeat above
step till the end of input.
Example
Evaluate the above prefix expression where the value
of A=1, B=2, C=3, D=4, E=3, F = 2, G=1 and H=4.
s.no
|
Scan char
|
Operand1
|
Operand2
|
Opstack
|
1
|
H(4)
|
4
|
||
2
|
G(1)
|
1,4
|
||
3
|
F(2)
|
2,1,4
|
||
4
|
E(3)
|
3,2,1,4
|
||
5
|
$
|
2
|
3
|
8,1,4
|
6
|
D(4)
|
4,8,1,4
|
||
7
|
/
|
8
|
4
|
2,1,4
|
8
|
*
|
1
|
2
|
2,4
|
9
|
C(3)
|
3,2,4
|
||
10
|
B(2)
|
2,3,2,4
|
||
11
|
*
|
3
|
2
|
6,2,4
|
12
|
-
|
2
|
6
|
-4,4
|
13
|
*
|
4
|
-4
|
-16
|
14
|
A(1)
|
1, -16
|
||
15
|
+
|
-16
|
1
|
-15
|
Algorithm to
convert infix expression to postfix expression
1.
Scan one
character at a time from left to right.
2.
Repeat while
there is data.
a.
If ‘(‘ push it
into the stack
b.
If operand,
Append it into postfix string
c.
If operator
i.
If stack is
empty push it onto opstack
ii.
If not repeat
till precedence of tos>=scan char
iii.
Pop and append
into postfix string
iv.
Push into
opstack
d.
If ‘)’ is found
i.
Pop and append
to postfix until matching ‘(‘ is found and ignore both.
3.
Pop and append
to postfix until stack is empty
4.
Return.
Convert
following infix string to postfix string
A+(B*C-(D/E$F)*G)*H
s.no
|
Scan char
|
Postfix string
|
Opstack
|
1
|
A
|
A
|
|
2
|
+
|
A
|
+
|
3
|
(
|
A
|
+(
|
4
|
B
|
AB
|
+(
|
5
|
*
|
AB
|
+(*
|
6
|
C
|
ABC
|
+(*
|
7
|
-
|
ABC*
|
+(-
|
8
|
(
|
ABC*
|
+(-(
|
9
|
D
|
ABC*D
|
+(-(
|
10
|
/
|
ABC*D
|
+(-(/
|
11
|
E
|
ABC*DE
|
+(-(/
|
12
|
$
|
ABC*DE
|
+(-(/$
|
13
|
F
|
ABC*DEF
|
+(-(/$
|
14
|
)
|
ABC*DEF$/
|
+(-
|
15
|
*
|
ABC*DEF$/
|
+(-*
|
16
|
G
|
ABC*DEF$/G
|
+(-*
|
17
|
)
|
ABC*DEF$/G*-
|
+
|
18
|
*
|
ABC*DEF$/G*-
|
+*
|
19
|
H
|
ABC*DEF$/G*-H
|
+*
|
20
|
NULL
|
ABC*DEF$/G*-H*+
|
NULL
|
So the resulting expression is
ABC*DEF$/G*-H*+
Algorithm to
check whether the converted postfix expression is valid or not
1.
Rank each symbol
of an expression
2.
Rank -1 if it is
operator
3.
Rank +1 if it is
operand
4.
Calculate total
rank as follows
a.
If operand is
placed in postfix expression, increment rank by 1
b.
If operator is
placed in postfix expression, decrease rank by 1
c.
At any point of
time, while converting infix expression to postfix expression, the rank of the expression
can be greater than or equal to 1. If the rank is anytime less than 1, the
expression is invalid.
d.
Once the entire
expression is converted, the rank must be equal to 1. Else the expression in
invalid.
Evaluation of a postfix expression
1. Scan one character at a time from
left to right.
2. If scan character is an operand,
push it onto the stack
3. If an operator, pop 2 operand from
the stack, the first one popped is called operand2 and the second one is called
operand1.
4. Perform result = operand1 operator
operand2
5. Push result onto the stack.
6. Repeat the above steps till the end
of the input.
Example
Evaluate the following postfix
expression AB+C*DE—FG+$. Where A=1, B=2, C=3, D=4,E=3, F=2 and G=1.
s.no
|
Scan char
|
Operand1
|
Operand2
|
Opstack
|
1
|
A(1)
|
1
|
||
2
|
B(2)
|
1,2
|
||
3
|
+
|
1
|
2
|
3
|
4
|
C(3)
|
3,3
|
||
5
|
*
|
3
|
3
|
9
|
6
|
D(4)
|
9,4
|
||
7
|
E(3)
|
9,4,3
|
||
8
|
-
|
4
|
3
|
9,1
|
9
|
-
|
9
|
1
|
8
|
10
|
F(2)
|
8,2
|
||
11
|
G(1)
|
8,2,1
|
||
12
|
+
|
2
|
1
|
8,3
|
13
|
$
|
8
|
3
|
512
|
Hence the result of the above
postfix expression is 512
No comments:
Post a Comment