Homework SourseLet a 5 b 7 c 4 d 2 e 3 f 1 g 6 Evaluate the followin
Let a = 5, b = 7, c = 4, d = 2, e = 3, f = 1, g = 6. Evaluate the following RPN expressions without converting to infix, then convert the expressions to infix and solve to double-check your answers:
A. abc*+de--
B. abc/*de*f*g/-
Solution
Given a = 5, b = 7, c = 4, d = 2, e = 3, f = 1, g = 6.
To evaluate above RPN, follow the steps
Scan the expression from left to right,
When all the symbols are scanned, set value=top item of the stack
Solution to Bit-A
abc*+de--
Evaluation of above RPN
Putting the value of a,b,c,d,e in above
5 7 4 * + 2 3 - -
Steps:
Symbols Stack Contents Action
5 5 Push(5)
7 5 7 push(7)
4 5 7 4 push(4)
* 5 28 x=pop()=4, y=pop()=7, z=y*x=28, push(28)
+ 33 x=pop()=28, y=pop()=5, z=y+x=33, push(33)
2 33 2 push(2)
3 33 2 3 push(3)
- 33 -1 x=pop()=3, y=pop()=2, z=y-x=-1, push(-1)
- 34 x=pop()=-1, y=pop()=33, z=y-x=34, push(34)
All symbol scanned, so value= top of stack=34
Conversion of RPN to infix
Process is same as above , but in this case , don’t evaluate x <operator> y. just concatenate ( , y ,Operator, z and )
Steps:
Symbol Stack Contents Action
5 5 Push(5)
7 5 7 push(7)
4 5 7 4 push(4)
* 5 (7*4) x=pop()=4, y=pop()=7, z=(|| y|| *||x||) push(z)
+ (5 +(7*4)) x=pop()=(7*4), y=pop()=5, z=(|| y|| *||x||) push(z)
2 (5 +(7*4)) 2 push(2)
3 (5 +(7*4)) 2 3 push(3)
- (5 +(7*4)) (2-3) x=pop()=3, y=pop()=2, z=(|| y|| *||x||) push(z)
- (5 +(7*4)) -(2-3) x=(2-3), y=,(5 *(7*4)) z=(|| y|| *||x||) push(z)
All symbol scanned, so infix=(5 *(7*4)) -(2-3) which evaluates 34.
Solution to Bit-B
abc/*de*f*g/-
Evaluation of above RPN
Putting the value of a,b,c,d,e in above
5 7 4 / * 2 3 * 1 * 6 / -
Steps:
Symbols Stack Contents Action
5 5 Push(5)
7 5 7 push(7)
4 5 7 4 push(4)
/ 5 1.75 x=pop()=4, y=pop()=7, z=y/x=1.75, push(1.75)
* 8.75 x=1.75, y=5, z=y*x=8.75, push(8.75)
2 8.75 2 push(2)
3 8.75 2 3 push(3)
* 8.75 6 x=3, y=2, z=y*x=-1, push(6)
1 8.75 6 1 push(1)
* 8.75 6 x=1, y=6, z=y*x=6, push(6)
6 8.75 6 6 push(6)
/ 8.75 1 x=6, y=6, z=y/x=1, push(1)
* 8.75 x=1, y=8.75,z=y/x=8.75, push(8.75)
All symbol scanned, so value= top of stack=8.75
Conversion of RPN to infix
Process is same as above , but in this case , don’t evaluate x <operator> y. just concatenate ( , y ,Operator, z and )
Steps:
Symbols Stack Contents Action
5 5 Push(5)
7 5 7 push(7)
4 5 7 4 push(4)
/ 5 (7/4) x=4, y=7,z=y/x=(7/4), push (7/4) nb: no evaluataion
* (5*(7/4)) x=(7/4), y=5, z=y*x= (5*(7/4)), push (5*(7/4))
2 (5*(7/4)) 2 push(2)
3 (5*(7/4)) 2 3 push(3)
* (5*(7/4)) (2*3) x=3, y=2, z=y*x=(2*3), push (2*3)
1 (5*(7/4)) (2*3) 1 push(1)
* (5*(7/4)) ((2*3)*1) x=1, y=(2*3), z=((2*3)*1), push ((2*3)*1)
6 (5*(7/4)) ((2*3)*1) 6 push(6)
/ (5*(7/4)) (((2*3)*1)/6) x=6, y=((2*3)*1) z=y/x , push (((2*3)*1)/6)
* ((5*(7/4)) * (((2*3)*1)/6)) x=(((2*3)*1)/6), y=(5*(7/4)) ,z=y/x, Push ((5*(7/4)) * (((2*3)*1)/6))
All symbol scanned, so infix ((5*(7/4)) * (((2*3)*1)/6)) which evaluates 8.75
