1) Consider following arithmetic infix expression convert it to prefix & write algorithm
and symbol table which shows status of stack-
((A+B) *(C+D)/(E-F)) +G
S.NO Symbol Stack Expression P
Scanned
1 G G
2 + + G
3 ) +) G
4 F +) FG
5 - +)- FG
6 E +)- EFG
7 ( + -EFG
8 / +/ -EFG
9 ) +/) -EFG
10 D +/) D-EFG
11 + +/)+ D-EFG
12 C +/)+ CD-EFG
13 ( +/ +CD-EFG
14 * +*/ +CD-EFG
15 ) +*/) +CD-EFG
16 B +*/) B+CD-EFG
17 + +*/)+ B+CD-EFG
18 A +*/)+ AB+CD-EFG
19 ( +*/ +AB+CD-EFG
20 +* /+AB+CD-EFG
21 + */+AB+CD-EFG
22 +*/+AB+CD-EEFG
ALGORTHM:
(Polish P,O)
1. PUSH “)” onto STACK, and add “(” to the beginning of Q
2. Scan Q from right to left and repeat step 3 to step 6 for each element of Q until the STACK is
empty.
3. If an operand is encountered, add it to P
4. If a right parenthesis is encountered, push it onto STACK.
5. If an operator X is encountered then:
i) Repeatedly POP from STACK and add to P each operator (on the top of STACK) which has the
same precedence as or higher precedence than X
ii) Add X to STACK
[END of IF Structure]
6. If a left parenthesis is encountered then:
i) Repeatedly POP from STACK and add to P each operator (on the top of STACK) until a right
parenthesis is encountered.
ii) Remove the right parenthesis. [Do not add the right parenthesis to P]
[End of IF Structure]
[End of STEP 2 loop]
7. Exit
2) Evaluate converted prefix by assigning values: A=14, B= 12, C=10, D=8, E=6,
F=4, G=2.
Prefix expression: + * / + A B + C D - E F G
i) Evaluate + A B:
• A + B = 14 + 12 = 26 ii)
Evaluate + C D: C + D
= 10 + 8 = 18 iii)
Evaluate / ( + A B ) ( + C
D ):
• 26 / 18 = 1.4 iv) Evaluate
- E F: E – F = 6 – 4 = 2
v) Evaluate * ( / + A B + C D ) ( - E F ):
• 1.4 × 2 = 2.8 vi) Evaluate + ( * / + A B + C D - E F ) G:
• 2.8 + 2 = 4.8
3) Make a Queue using Array [5] and apply following functions: enqueue(10),
enqueue(50) enqueue(20), enqueue(70), dequeue(), enqueue(100), enqueue(40),
enqueue(140) dequeue(), dequeue(), dequeue()-
Initial state:
Queue: front -1, rear -1
i. Enqueue (10): front = 0, rear = 0
10
ii. Enqueue (50): front = 0, rear = 1
10 50
iii. Enqueue (20): front = 0, rear = 2
10 50 20
iv. Enqueue (70): front = 0, rear = 3
10 50 20 70
v. Dequeue (): front = 1, rear = 3
50 20 70
vi. Enqueue (100): front = 1, rear = 4
50 20 70 100
vii. Enqueue (40): front = 1, rear = 0 (circular wrap)
40 50 20 70 100 viii.
Enqueue (140): front = 1, rear = 0 (queue full cannot insert 140)
40 50 20 70 100
ix. Dequeue (): front = 2, rear = 0
40 20 70 100
x. Dequeue (): front = 3, rear = 0
40 70 100
xi. Dequeue (): front = 4, rear = 0
40 100
