Scribd
Upload
2 views55 pages

Module 2

The document contains lecture notes on data structures, specifically focusing on the conversion of infix expressions to postfix expressions and the evaluation of postfix expressions. It includes detailed examples with tokens, stacks, and outputs for various expressions. The notes are compiled by Dr. Bhavanishankar K from the Department of Computer Science and Engineering.

Uploaded by

rajputadityasingh23cs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
2 views55 pages

Module 2

The document contains lecture notes on data structures, specifically focusing on the conversion of infix expressions to postfix expressions and the evaluation of postfix expressions. It includes detailed examples with tokens, stacks, and outputs for various expressions. The notes are compiled by Dr. Bhavanishankar K from the Department of Computer Science and Engineering.

Uploaded by

rajputadityasingh23cs
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Department of Computer Science and

Engineering
Preparing Better Computer Professionals for a Real World

Lecture Notes on

DATA STRUCTURES & APPLICATIONS


BCS304

Module 2

Compiled by :
Dr. Bhavanishankar K
Professor
Dept. of CSE
CONVERSION OF INFIX TO POSTFIX EXPRESSIONS

i. a+b*c

token stack top output


a --- -1 a
+ + 0 a
b + 0 ab
* + * 1 ab
c + * 1 abc
--- --- -1 abc*+

ii. a*b+c

token stack top output


a --- -1 a
* * 0 a
b * 0 ab
+ + 0 ab*
c + 0 ab*c
--- --- -1 ab*c+

iii. a/2*b+c*3/d

token stack top output


a --- -1 a
/ / 0 a
2 / 0 a2
* * 0 a2/
b * 0 a2/b
+ + 0 a2/b*
c + 0 a2/b*c
* + * 1 a2/b*c
3 + * 1 a2/b*c3
/ + / 1 a2/b*c3*
d + / 1 a2/b*c3*d
--- --- -1 a2/b*c3*d/+

iv. p/q/r*s/t*u+v-z

token stack top output


p --- -1 p
/ / 0 p
q / 0 pq
/ / 0 pq/
r / 0 pq/r
* * 0 pq/r/
s * 0 pq/r/s
/ / 0 pq/r/s*
t / 0 pq/r/s*t
* * 0 pq/r/s*t/
u * 0 pq/r/s*t/u
+ + 0 pq/r/s*t/u*
v + 0 pq/r/s*t/u*v
- - 0 pq/r/s*t/u*v+
z - 0 pq/r/s*t/u*v+z
--- --- -1 pq/r/s*t/u*v+z-

v. (8+6-7*6)

token stack top output


( ( 0 ---
8 ( 0 8
+ ( + 1 8
6 ( + 1 86
- ( - 1 86+
7 ( - 1 86+7
* ( - * 2 86+7
6 ( - * 2 86+76
) --- -1 86+76*-

vi. (6+((7/2-8)*(6+4-2/7))+5)

token stack top output


( ( 0 ---
6 ( 0 6
+ ( + 1 6
( ( + ( 2 6
( ( + ( ( 3 6
7 ( + ( ( 3 67
/ ( + ( ( / 4 67
2 ( + ( ( / 4 672
- ( + ( ( - 4 672/
8 ( + ( ( - 4 672/8
) ( + ( 2 672/8-
* ( + ( * 3 672/8-
( ( + ( * ( 4 672/8-
6 ( + ( * ( 4 672/8-6
+ ( + ( * ( + 5 672/8-6
4 ( + ( * ( + 5 672/8-64
- ( + ( * ( - 5 672/8-64+
2 ( + ( * ( - 5 672/8-64+2
/ ( + ( * ( - / 6 672/8-64+2
7 ( + ( * ( - / 6 672/8-64+27
) ( + ( * 3 672/8-64+27/-
) ( + 1 672/8-64+27/-*
+ ( + 1 672/8-64+27/-*+
5 ( + 1 672/8-64+27/-*+5
) --- -1 672/8-64+27/-*+5+
EVALUATION OF POSTFIX EXPRESSION

i. 86+76*-

token stack top


8 8 0
6 8 6 1
+ 14 0
7 14 7 1
6 14 7 6 2
* 14 42 1
- -28 -1

ii. 45/6*96*7/+

token stack top


4 4 0
5 4 5 1
/ 0 0
6 0 6 1
* 0 0
9 0 9 1
6 0 9 6 2
* 0 54 1
7 0 54 7 2
/ 0 7 1
+ 7 -1

You might also like