Stacks
Stacks are known as last in first out data structure (LIFO). In this the last item pushed on the stack is the first item popped from the stack. In stack the insertion and deletion can be taken placed at one only end called stack’s top. A stack is a nonprimitive linear data structure in which the insertion and the deletion of the elements take place from only one end, known as the top.
The fundamental operations that can be performed on stack are push and pop. Push operation causes a value to be stored in (pushed onto) the stack; whereas, Pop retrieves and removes a value from the stack. PUSH is an operation used to add a new element in to a stack. When implementing the push operation, overflow condition of a stack is to be checked. Insert a new data item on the TOP. TOP is set to a newly added item.
Pop is an operation used to remove an element from the TOP of the stack. When implementing the pop operation, underflow condition of a stack is to be checked. Stack can be implemented in two ways As an Array and as a Linked List.
To Access the full content, Please Purchase

Q1
Evaluate the given postfix expression, showing the stack at every stage.
20 10 + 12 10  * 4 1  3 ^ +
Marks:2Answer:
Stages are:
Element
Operation
Stack
1
20
push
20
2
10
push
20 10
3
+
pop
pop
perform 20 + 10
push result
30
4
12
push
30 12
5
10
push
30 12 10
6

pop
pop
perform 12  10
push result
30 2
7
*
pop
pop
perform 30 * 2
push result
60
8
4
push
60 4
9
1
push
60 4 1
10

pop
pop
perform 4  1
push result
60 3
11
3
push
60 3 3
12
^
pop
pop
perform 3 ^ 3
push result
60 27
13
+
pop
pop
perform 60 + 27
push result
87
Result  87

Q2
Evaluate the given postfix expression, showing the stack at every stage.
15 3 + 4 * 6 7 5  / 
Marks:2Answer:
Stages are:
Element
Operation
Stack
1
15
push
15
2
3
push
15 3
3
+
pop
pop
perform 15 + 3
push result
18
4
4
push
18 4
5
*
pop
pop
perform 18 * 4
push result
72
6
6
push
72 6
7
7
push
72 6 7
8
5
push
72 6 7 5
9

pop
pop
perform 7  5
push result
72 6 2
10
/
pop
pop
perform 6 / 2
push result
72 3
11

pop
pop
perform 72  3
push result
69

Q3
Convert the given infix expression to postfix, showing the stack at every stage.
(true AND false) OR NOT(false OR True)
Marks:2Answer:
: Input expression : (true AND false) OR NOT(false OR True)
Element
Stack
Expression Y in Postfix
1
(
2
(
((
3
true
((
true
4
AND
((AND
true
5
false
((AND
true false
6
)
(
true false AND
7
OR
(OR
true false AND
8
NOT
( OR NOT
true false AND
9
(
(OR NOT (
true false AND
10
false
(OR NOT(
true false AND false
11
OR
(OR NOT(OR
true false AND false
12
true
(OR NOT(OR
true false AND false true
13
)
(OR NOT
true false AND false true OR
14
)
true false AND false true OR NOT OR
The Postfix expression is : true false AND false true OR NOT OR 
Q4
Convert the given infix expression to postfix, showing the stack at every stage.
A * ( B + C ) / E – F – (D + G) / H
Marks:3Answer:
Input expression : A * ( B + C ) / E – F – (D + G) / H
Element
Stack
Expression Y in Postfix
1
A
(
A
2
*
(*
A
3
(
(*(
A
4
B
(*(
AB
5
+
(*(+
AB
6
C
(*(+
ABC
7
)
(*
ABC+
8
/
(/
ABC+*
9
E
(/
ABC+*E
10

(
ABC+*E/
11
F
(
ABC+*E/F
12

(
ABC+*E/F
13
(
((
ABC+*E/F
14
D
((
ABC+*E/FD
15
+
((+
ABC+*E/FD
16
G
((+
ABC+*E/FDG
17
)
(
ABC+*E/FDG+
18
/
(/
ABC+*E/FDG+
19
H
(/
ABC+*E/FDG+H
20
)
ABC+*E/FDG+H/
The Postfix expression is : ABC+*E/FDG+H/ 
Q5
What is ‘Polish String’ ? Give examples and describe its forms.
Marks:4Answer:
Polish string is a notation in which the operator is placed before or after the two operands it is working on. There are no brackets or parenthesis in his form. Prefix is the form in which operator is placed before the operands. Postfix is the form in which operator is placed after the operands.
Expression in Infix form
Expression in Prefix form
Expression in Postfix form
A + B
+ A B
A B +
(A – B) * C
* A B C
A B  C *
(A – B) / (C – D)
/  A B  C D
A B  C D  /