Data Structures Using C (BEC405D)

Module 2
The Stack and Recursion

Dr. Maya B S
Assistant Professor
Department of CSE
BIT

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 1

 Syllabus
The Stack
• Definition and examples, primitive operations, Example.
• Representing Stacks in C
• Example: Infix, Postfix and Prefix,converting an Expression from Infix to Prefix and
Program.
• Text Book -1-Chapter – 2.1-2.3
Recursion
• Recursive Definition and Processes
• Recursion in C
• Writing Recursive Programs
Recursions - Text Book -1-Chapter – 3.1-3.3

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 2

 Contents
❖Stacks
❖Definition
❖ Stack Operations,
❖Array Representation of Stacks,
❖Stacks using Dynamic Arrays.
❖ Different representation of expression.
❖Stack Applications:
❖Infix to postfix conversion,
❖Infix to prefix conversion,
❖evaluation of postfix expression,
❖recursion.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 3

 Stack
❖ Stack is a linear data structure which follows a particular order
in which the operations are performed.
❖ Insertion of element into stack is called PUSH and deletion of
element from stack is called POP.
❖ The order may be LIFO(Last In First Out) or FILO(First In
Last Out).

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

4
 Application of Stacks
❖ It is used to reverse a word. You push a given word to stack
❖ – letter by letter and then pop letter from the stack.
❖ “Undo” mechanism in text editor.
❖ Backtracking: This is a process when you need to access the most recent
data element in a series of elements. Once you reach a dead end, you must
backtrack.
❖ Language Processing: Compiler’ syntax check for matching braces in
implemented by using stack.
❖ Conversion of decimal number to binary.
❖ To solve tower of Hanoi.
❖ Conversion of infix expression into prefix and postfix.
❖ Quick sort
❖ Runtime memory management.
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT
5
 Operation on Stacks:
❖ Stack( ): It creates a new stack that is empty. It needs no
parameter and returns an empty stack.
❖ push(item): It adds a new item to the top of the stack.
❖ pop( ): It removes the top item from the stack.
❖ peek( ): It returns the top item from the stackbut does not remove
it.
❖ isEmpty( ): It tests whether the stack is empty.
❖ size( ): It returns the number of items on the stack.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

6
Representation of Stack in Memory
The stack can be implemented into two
ways:

◦ Using arrays (Static implementation)

◦ Using pointer (Dynamic implementation)

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

7
Array Representation of Stacks
#define MAX _STK 25
int stack[MAX_SIZE];
top = -1;
OR
#define MAXSTK 10
typedef struct {
int item[MAXSTK];
int top;
}STACK;

STACK s;
[Link] = -1;

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 8

Stack after – PUSH( ‘A’), PUSH( ‘B’), PUSH( ‘C’), PUSH( ‘D’)
Stack Conditions

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

9
PUSH Operation
The process of adding one element or item tothe stack is
represented by an operation called as the PUSH operation.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

10
PUSH Operation:
The process of adding one element or item to the stack is
represented by an operation called as the PUSH operation.
The new element is added at the topmost position of the stack.
ALGORITHM:
PUSH (STACK, TOP, SIZE, ITEM)
STACK is the array with N elements. TOP is the pointer to the top of the
element of the array. ITEM to be inserted.
Step 1: if TOP = SIZE-1 then [Check Overflow]
PRINT “ STACK is Full or Overflow”
Exit
[End if]
Step 2: TOP = TOP + 1 [Increment the TOP]
Step 3: STACK[TOP] = ITEM [Insert the ITEM]
Step 4: Return
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT
11
 POP Operation
The process of deleting one element or item from
the stack is represented by an operation called as
the POP operation.
When elements are removed continuously from a
stack, it shrinks at same end i.e., top

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

12
 POP Operation
The process of deleting one element or item from the stack
is represented by an operation called as the POP
operation.
ALGORITHM: POP (STACK, TOP, ITEM)
STACK is the array with N elements. TOP is the pointer to the top of the
element of the array. ITEM to be inserted.
Step 1: if TOP = -1 then [Check Underflow]
PRINT “ STACK is Empty or Underflow”
Exit
[End if]
Step 2: ITEM = STACK[TOP] [copy the TOP Element]
Step 3: TOP = TOP - 1 [Decrement the TOP]
Step 4: Return

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT

13
 PEEK Operation
The process of returning the top item from the
stack but does not remove it called as the POP
operation.

ALGORITHM: PEEK (STACK, TOP)

STACK is the array with N elements. TOP is the pointer to
the top of the element of the array.
Step 1: if TOP = -1 then [Check Underflow]
PRINT “ STACK is Empty or Underflow”
Exit
[End if]
Step 2: Return (STACK[TOP] [Return the top
element of the stack]
Step 3:Exit Dr. Maya B S, Associate Professor, Dept. of CSE, BIT
14
 Stacks using Dynamic Arrays
In static array or array based implementation an array of fixed size is used to create a
stack where as in dynamic array based implementation, an array of predefined initial
capacity is used to create a stack and if the array has reached its max capacity, a new
array of double the current capacity is created and the values from old array will be
copied to new array and the new array will be considered as our stack.
Below are the points to be aware about implementation of stack using resizable
arrays
•Capacity :
• An array of initial capacity is defined and once the array reaches max capacity,
arrays grow double the current size.
• For simplicity the stack array can be initialized with 1 as the current capacity.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 15

 Stacks using Dynamic Arrays
•No Overflow :
• There is no chance of overflow as whenever the array reaches its
capacity, the array gets resized to double to the current capacity.
•Waste of Space :
• Once the stack size grows reasonably high in size and frequent pop
operations make waste of space.
•Underflow:
• When no elements are left in the stack.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 16

Stacks using Dynamic Arrays
#define MAX 25
typedef struct {
int item;
}Element;
Element *stack;
int top= -1; top =0
capacity = 1; 10 (1000-1004)
stack = (Element *) malloc (sizeof (*stack)); 1000-1004

int IsFull( )
{
• if ( top >= capacity – 1) // stack capacity =1
• return 1;
• return 0;
}

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 17

void Push(Element item)
{
• if(IsFull( ))
• Stackfull( );
• top++;
• * stack=item;
• return;
}

void Stackfull( )
{
• stack=realloc(stack, 2*capacity*sizeof (*stack));
• capacity*=2;
}

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 18

int isempty( )
{
if(top <0)
• return 1;
• return 0;
}
Element Pop( )
{
• Element x;
• if(!Isempty(s)
• {
• x=*stack;
• top--;
• return x;
}
}
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 19
Array doubling

void StackFull()
{
realloc(stack , 2*capacity*sizeof(*stack));
capacity * = 2;
}

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 20

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 21
 Application of Stacks
❖ It is used to reverse a word. You push a given word to stack
❖ – letter by letter and then pop letter from the stack.
❖ “Undo” mechanism in text editor.
❖ Backtracking: This is a process when you need to access the most recent
data element in a series of elements. Once you reach a dead end, you must
backtrack.
❖ Language Processing: Compiler’ syntax check for matching braces in
implemented by using stack.
❖ Conversion of decimal number to binary.
❖ To solve tower of Hanoi.
❖ Conversion of infix expression into prefix and postfix.
❖ Quick sort
❖ Runtime memory management.
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT
22
Stack Applications ([Link])
Conversion of infix expression into prefix and postfix. Ex. a+b →
+ab or ab+
It is used to reverse a word. You push a given word to stack
• – letter by letter and then pop letter from the stack.
• Expression Evaluation: 23+ →5 D
• Recursion. Sum() S=ABCD C
B
{ sum()
A
{ sum()

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 23

 Arithmetic Expression
An expression is a combination of operands and operators that after evaluation
results in a single value.
· Operand consists of constants and variables.
· Operators consists of {, +, -, *, /, ), ] etc.
Expression can be
1. Infix Expression: If an operator is in between two operands, it is called infix expression.
Example: a + b, where a and b are operands and + is an operator.
2. Prefix Expression (POLISH ): an operator precedes the two operands, it is called prefix
expression.
Example: +ab
3. Postfix Expression(REVERSE POLISH or SUFFIX): If an operator follows the two operands, it
is called postfix expression.
Example: ab +
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT
24
 Arithmetic Expression Representation
• INFIX
• PREFIX – POLISH
• POSTFIX – REVERSE POLISH or SUFFIX
INFIX POLISH REVERSE POLISH

A+B*C +A*BC ABC*+

(A+B)*C *+ABC AB+C*

• Note
• The order of operators and operands in an INFIX expression does not uniquely determine the order in
which operations to be performed
• In POLISH and REVERSE POLISH notation the order in which the operations to be preformed is
completely determined by the position of the operators and the operands in the expression
• No parenthesis required to determine the order
• Computer evaluates arithmetic expressions in INFIX notation in two steps
• 1) Convert INFIX expression to POSTIX
• 2) Evaluate the POSTFIX expression

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 25

Precedence of Operators during conversion and Evaluation without
parenthesis
• Three levels of precedence for the 5 binary operations
• Highest : Exponentiation ( ) or ($) or (^) or (**)
• Next Highest : Multiplication (*) and Division(/)
• Lowest: Addition (+) and Subtraction (-)

• Note: If we have parenthesis in the infix expression, parenthesis

takes the highest precedence.

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 26

Infix: 3+4 (operator between operands)
Postfix (REVERSE POLISH or SUFFIX ): 34+(operator is at end)
Prefix (polish): +34 (operator is at the beginning)

Infix: D=3+6*(8-7) 1.() 2.$ ^ 3. *,/ 4.+,-

Postfix: 3+6*(87-)=3+6(87-)*=3687-*+
Prefix= 3+6*(-87)= 3+*6-87= +3*6-87
A$B*C-D+E/F/G+H
((A+B)*C-(D-E))$(F+G)

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 27

Converting infix to postfix and Prefix -Examples
INFIX
1. A+B*C : A+[BC*] ABC*+ is POSTFIX
A+[*BC] +A*BC is PREFIX
2 (A+B)*C : [AB+]*C AB+C* is POSTFIX
[+AB]*C *+ABC is PREFIX
3 A$B*C-D+E/F/G+H: [AB$]*C-D+E/F/G+H
(Converting to postfix ) [AB$C*]-D+[EF/G/]+H
AB$C*D-EF/G/+H+ is POSTFIX
(Converting to prefix) [$AB]*C-D+E/F/G+H
[*$ABC]-D+[//EFG]+H
++-*$ABCD//EFGH is PREFIX

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 28

Converting infix to postfix and Prefix -Examples
INFIX to POSTFIX Conversion
Given Infix Expression: ((A+B)*C-(D-E))$(F+G)
([AB+]*C-[DE-])$[FG+]
([AB+C*]-[DE-])$[FG+]
[AB+C*DE--]$[FG+]
AB+C*DE--FG+$ is Post expression
INFIX to PREFIX Conversion
Given Infix Expression: ((A+B)*C-(D-E))$(F+G)
([+AB]*C-[-DE])$[+FG]
([*+ABC]-[DE-])$[+FG]
[-*+ABC-DE]$[+FG]
$-*+ABC-DE+FG is Prefix expression

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 29

Algorithm to evaluate POSTFIX expression
• EVALUATE (P)
This algorithm finds the VALUE of an arithmetic expression P written in
postfix notation
1. Append a right parenthesis “)”/# at the end of P.[this acts as a sentinel]
2. Scan P from left to right and repeat Steps 3 and 4 for each element of P
until the sentinel “)” is encountered
3. If an operand is encountered, place it on to STACK
4. If an operator is encountered, then,
(a) Remove the two top elements of STACK, where A is the top element and B
is the next-to-top element
(b) Evaluate B operator A
(c) Place the result of (b) back on stack
[End of If structure]
[End of Step 2 loop]
5. Set VALUE equal to the top element on STACK
6. Exit
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 30
Evaluate the given Postfix Expression :
Postfix: 6 2/ 3– 42*+ ,Initially top = -1
Step Symbol Top of Stack Opnd2 Opnd1 Result
i Read Stack [0] [1] [2]
-1
i=0 6 0 6
1 2 1 6, 2
2 / Pop both the 2 6 6/2 = 3
elements Push 3 onto the stack
0 3
3 3 1 3, 3
4 - Pop both the 3 3 3-3 = 0
elements Push 0 onto the stack
0 0
5 4 1 0, 4
6 2 2 0, 4, 2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 31

 Evaluate the given Postfix Expression :
Postfix: 6 2/ 3– 42*+
Step Symbo Top of Stack Opnd2 Opnd1 Result
i l Read Stack [0] [1] [2]
7 * Pop both 2 4 4*2=8
the Push 8 onto the
elements stack
1 0, 8
8 + Pop both 8 0 0+8=8
the Push 8 onto the
elements stack
0 8
EOS Pop 8 from Res = 8
stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 32

Postfix Evaluation

Postfix expression
62/3–42*+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 33

stack

Postfix Expression
62 / 3 – 4 2 * +

Token
Operand,
6 PUSH onto
stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 34

stack

Postfix Expression
2/3–42*+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 35

stack

Postfix Expression
/3–42*+

Token
Operand,
2 PUSH onto
stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 36

stack

Postfix Expression
/3–42*+

2
6

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 37

stack

Postfix Expression
3–42*+

Token
Operator, POP
/ 2 top elements
from the stack
2
and store it in
6 opnd2 and
opnd1
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 38
stack

Postfix Expression
3–42*+

opnd1 opnd2
6 2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 39

stack

Postfix Expression
3–42*+
Evaluate
opnd1 opnd2
opnd1
6 2 operator
opnd2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 40

stack

Postfix Expression
3–42*+

opnd1 opnd2 Res

6 / 2 3

PUSH Res onto stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 41

stack

Postfix Expression
3–42*+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 42

stack

Postfix Expression
–42*+

Token
Operand,
3 PUSH onto
stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 43

stack

Postfix Expression
–42*+

3
3

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 44

stack

Postfix Expression
42*+

Token
Operator, POP
- 2 top elements
from the stack
3
and store it in
3 opnd2 and
opnd1
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 45
stack

Postfix Expression
42*+
Evaluate
opnd1 opnd2
opnd1
3 3 operator
opnd2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 46

stack

Postfix Expression
42*+

opnd1 opnd2 Res

3 - 3 0

PUSH Res onto stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 47

stack

Postfix Expression
42*+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 48

stack

Postfix Expression
2*+

Token
Operand,
4 PUSH onto
stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 49

stack

Postfix Expression
2*+

4
0

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 50

stack

Postfix Expression
*+

Token
Operand,
2 PUSH onto
stack
4
0

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 51

stack

Postfix Expression
*+

2
4
0

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 52

stack

Postfix Expression
+

Token
Operator, POP
2 * 2 top elements
from the stack
4
and store it in
0 opnd2 and
opnd1
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 53
stack

Postfix Expression
+
Evaluate
opnd1 opnd2
opnd1
4 2 operator
opnd2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 54

stack

Postfix Expression
+

opnd1 opnd2 Res

4 * 2 8

PUSH Res onto stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 55

stack

Postfix Expression
+

8
0

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 56

stack

Postfix Expression

Token
Operator, POP
+ 2 top elements
from the stack
8
and store it in
0 opnd2 and
opnd1
Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 57
stack

Postfix Expression

Evaluate
opnd1 opnd2
opnd1
0 8 operator
opnd2

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 58

stack

Postfix Expression

opnd1 opnd2 Res

0 + 8 8

PUSH Res onto stack

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 59

stack

Postfix Expression

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 60

 Evaluate the given Postfix Expression :
Postfix: 78+65+*
Initially
Step topTop
Symbo = -1
of Stack Opnd2 Opnd1 Result
i l Read Stack [0] [1] [2]
-1
i=0
1
2

3
4

5
6

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 61

 Evaluate the given Postfix Expression :
Postfix: 6 2/ 3– 42*+
Step Symbo Top of Stack Opnd2 Opnd1 Result
i l Read Stack [0] [1] [2]
7

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 62

 Infix to Postfix Conversion
Precedence of Operators
SYMBOLS Precedence Associativity

( 0 Left

+ - 1 Left

* / % 2 Left

^ $ 3 Right

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 63

• Reverse polish(Q, P) // Q is an arithmetic expression in INFIX notation
Algorithm converts INFIX expression Q into POSTFIX expression P
1 Push “(“ onto STACK, and append “)” to the end of Q
2 Scan Q left to right and repeat Steps 3 to 6 for each element of Q until
the STACK is empty
3 If an operand is encountered place it in the POSTFIX expression P
4 If an left parenthesis is encountered, push it on to the STACK
5 If an operator is encountered, call it as incoming operator, then:
a) Repeatedly pop from the STACK and place it in the P which has the same
precedence or higher precedence than the incoming operator
b) Place the incoming operator to the STACK
[End of IF]
6 If a right parentheses is encountered
a) Repeatedly pop from the STACK and place it in the P until left
parenthesis is encountered
b) Remove the left parenthesis
[ End of If ]
[ End of Step 2 loop ]
• Complexity – Ø(n),[Link]
Maya B S, n be the
Associate number
Professor, Dept. ofof tokens
CSE, BIT in the expression 64
A^B*C-D+E/F/G/+H ) :
AB^c*D-EF/G//+H+
Step Symbol Top of Stack Postfix
i Read Stack [0] [1] [2] Expression
-1
0 (
i=0 A A
1 ^ 1 ( > ^ : 0 >2:F
So push ^ onto stack

2 B AB
3 * ^>*
4

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 65

Convert Infix to Postfix Expression:
Infix: A^B*C-D+E/F/G/+H
After Adding left and right parenthesis:
A^B*C-D+E/F/G/+H ) :
AB^c*D-EF/G//+H+ Initially top = -1
Step Symbol Top of Stack Postfix
i Read Stack [0] [1] [2] Expression
-1
0 (
i=0 A A
1 ^ 1 ( > ^ : 0 >2:F
So push ^ onto stack

2 B AB
3 * ^>*
4

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 66

 Convert Infix to Postfix Expression:
Infix: A^B*C-D+E/F/G/+H
After Adding left and right parenthesis:
A^B*C-D+E/F/G/+H ) :
AB^c*D-EF/G//+H+
Initially top = -1

• (3^2*5)/(3*2-3)+5

• ((A+B)*C-(D-E))^(F+G)

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 67

Infix to postfix conversion
infixVect
(a+b-c)*d–(e+f)

postfixVect

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 68

Infix to postfix conversion
stackVect

infixVect
a+b-c)*d–(e+f)

postfixVect

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 69

Infix to postfix conversion
stackVect

infixVect
+b-c)*d–(e+f)

postfixVect
a

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 70

Infix to postfix conversion
stackVect

infixVect
b-c)*d–(e+f)

postfixVect
a

+
(

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 71

Infix to postfix conversion
stackVect

infixVect
-c)*d–(e+f)

postfixVect
ab

+
(

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 72

Infix to postfix conversion
stackVect

infixVect
c)*d–(e+f)

postfixVect
ab+

-
(

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 73

Infix to postfix conversion
stackVect

infixVect
)*d–(e+f)

postfixVect
ab+c

-
(

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 74

Infix to postfix conversion
stackVect

infixVect
*d–(e+f)

postfixVect
ab+c-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 75

Infix to postfix conversion
stackVect

infixVect
d–(e+f)

postfixVect
ab+c-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 76

Infix to postfix conversion
stackVect

infixVect
–(e+f)

postfixVect
ab+c-d

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 77

Infix to postfix conversion
stackVect

infixVect
(e+f)

postfixVect
ab+c–d*

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 78

Infix to postfix conversion
stackVect

infixVect
e+f)

postfixVect
ab+c–d*

(
-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 79

Infix to postfix conversion
stackVect

infixVect
+f)

postfixVect
ab+c–d*e

(
-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 80

Infix to postfix conversion
stackVect

infixVect
f)

postfixVect

+ ab+c–d*e

(
-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 81

Infix to postfix conversion
stackVect

infixVect
)

postfixVect

+ ab+c–d*ef

(
-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 82

Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 83

Infix to postfix conversion
stackVect

infixVect

postfixVect
ab+c–d*ef+-

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 84

 Infix to Postfix Conversion using Stack: Example

Infix Expression : A *(B + C) / D

Token Stack top Postfix

[0] [1] [2]
A -1 A
* * 0 A
( * ( 1 A
B * ( 1 AB
+ * ( + 2 AB
C * ( + 2 A BC
) * 0 ABC+
/ / 0 ABC+*
D / 0 ABC+*D
eos -1 ABC+*D/

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 85

 Infix to Postfix Conversion using Stack: Example

Infix Expression : X^Y^Z-M+N+P/Q

Token Stack top Postfix

[0] [1] [2]
X -1 X
^ ^ 0 X
Y ^ 0 XY
^ ^ ^ 1 XY
Z ^ ^ 1 X YZ
- - 0 X YZ^^
M - 0 XYZ^^M
+ + 0 XYZ^^M-
N + 0 XYZ^^M-N
+ + 0 XYZ^^M-N+
P + 0 XYZ^^M-N+P
/ + / 1 XYZ^^M-N+P
Q + / 1 XYZ^^M-N+PQ/+

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 86

 THANK YOU

Dr. Maya B S, Associate Professor, Dept. of CSE, BIT 87