In: Computer Science
GIVEN THE FOLLOWING PSOSTFIX EXPRESSION, SHOW TO USE A STACK TO
EVALUATE ITS FINAL VALUE. SHOW STACK CONFIGURATION DETAILS
20 3 18 8 - * 10 + +10 12 - /
Solution:
Given,
=>Postfix expression = 20 3 18 8 - * 10 + + 10 12 - /
Explanation:
=>To evaluate postifix expression operand stack is used means operands are pushed into the stack.
=>While traversing the expression from left to right if we find an operator then we need to pop off two operands from the top of the stack one by one and need to perform the operation and result is pushed back into the stack.
Initially:
=>Let say stack of size = 5
=>Top is the pointer which keeps track of elements inside the stack. Initially there is no element in the stack so top = -1 when an element is inserted into the stack top pointer is incremented by 1. When an element is deleted from the stack top pointer is decremented by 1.
top = -1
Step 1:
=>Push 20 into the stack.
20 |
top = 0
Step 2:
=>Push 3 into the stack.
3 |
20 |
top = 1
Step 3:
=>Push 18 into the stack.
18 |
3 |
20 |
top = 2
Step 4:
=>Now push 8 into the stack.
8 |
18 |
3 |
20 |
top = 3
Step 5:
=>Now pop off operands 8 and 18, result = 18 - 8, result = 10 and push back 10 into the stack.
10 |
3 |
20 |
top = 2
Step 6:
=>Now pop off operands 10 and 3 , result = 3*10, result = 30 and push back 30 into the stack.
30 |
20 |
top = 1
Stpe 7:
=>Now push 10 into the stack.
10 |
30 |
20 |
top = 2
Step 8:
=>Now pop off 10 and 30, result = 30 + 10, result = 40 and push back 40 into the stack.
40 |
20 |
top = 1
Stpe 9:
=>Now pop off operands 40 and 20, result = 20 + 40, result = 60 and push back 60 into the stack.
60 |
top = 0
Step 10:
=>Now push 10 into the stack.
10 |
60 |
top = 1
Step 11:
=>Now push 12 into the stack.
12 |
10 |
60 |
top = 2
Step 12:
=>Now pop off 12 and 10, result = 10 - 12, result = -2 and push back -2 into the stack
-2 |
60 |
top = 1
Step 13:
=>Now pop off -2 and 60, result = 60/-2, result = -30 and push back -30 into the stack.
-30 |
top = 0
Step 14:
=>As whole expression is traversed so final result will be last value present inside the stack hence final result = -30.
I have explained each and every part with the help of statements attached to it.