Data Structures and Algorithms - Old Questions
1. Trace out Infix to Postfix conversion algorithm with given Infix expression.
A + (((B-C) * (D-E) + F)/G) $ (H-I)
Evaluate the postfix expression acquired from above for the given values:
A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1.
Given Infix expression.
A + (((B-C) * (D-E) + F)/G) $ (H-I)
Converting it to postfix:
|
Characters |
Stack |
Postfix
expression |
|
A |
|
A |
|
+ |
+ |
A |
|
( |
+( |
A |
|
( |
+(( |
A |
|
( |
+((( |
A |
|
B |
+((( |
AB |
|
- |
+(((- |
AB |
|
C |
+(((- |
ABC |
|
) |
+(( |
ABC- |
|
* |
+((* |
ABC- |
|
( |
+((*( |
ABC- |
|
D |
+((*( |
ABC-D |
|
- |
+((*(- |
ABC-D |
|
E |
+((*(- |
ABC-DE |
|
) |
+((* |
ABC-DE- |
|
+ |
+((+ |
ABC-DE-* |
|
F |
+((+ |
ABC-DE-*F |
|
) |
+( |
ABC-DE-*F+ |
|
/ |
+(/ |
ABC-DE-*F+ |
|
G |
+(/ |
ABC-DE-*F+G |
|
) |
+ |
ABC-DE-*F+G/ |
|
$ |
+$ |
ABC-DE-*F+G/ |
|
( |
+$( |
ABC-DE-*F+G/ |
|
H |
+$( |
ABC-DE-*F+G/H |
|
- |
+$(- |
ABC-DE-*F+G/H |
|
I |
+$(- |
ABC-DE-*F+G/HI |
|
) |
+$ |
ABC-DE-*F+G/HI- |
|
|
+ |
ABC-DE-*F+G/HI-$ |
|
|
|
ABC-DE-*F+G/HI-$+ |
Now,
Evaluating the postfix expression for the given values:
A = 6, B = 2, C = 4, D = 3, E = 8, F = 2, G = 3, H = 5, I = 1
ABC-DE-*F+G/HI-$+
6 2 4 - 3 8 - * 2 +3 / 5 1 - $ +
|
Input symbol |
Stack |
operation |
|
6 |
6 |
|
|
2 |
6, 2 |
|
|
4 |
6, 2, 4 |
|
|
- |
6 |
2
- 4 = -2 |
|
|
6, -2 |
|
|
3 |
6, -2, 3 |
|
|
8 |
6, -2, 3, 8 |
|
|
- |
6, -2 |
3
– 8 = -5 |
|
|
6, -2, -5 |
|
|
* |
6 |
(-2)*(-5)
= 10 |
|
|
6, 10 |
|
|
2 |
6, 10, 2 |
|
|
+ |
6 |
10+2
= 12 |
|
|
6, 12 |
|
|
3 |
6, 12, 3 |
|
|
/ |
6 |
12/3
= 4 |
|
|
6, 4 |
|
|
5 |
6, 4, 5 |
|
|
1 |
6, 4, 5, 1 |
|
|
- |
6, 4 |
5
-1 = 4 |
|
|
6, 4, 4 |
|
|
$ |
6 |
4$4
= 256 |
|
|
6, 256 |
|
|
+ |
|
6
+ 256 = 262 (Result) |