Page 509 - Computer science 868 Class 12
P. 509
Step 5: If the symbol scanned is a left parenthesis, then push it to the stack.
Step 6: If the symbol scanned is a right parenthesis, then pop one operator at a time from the top and append it to
the postfix string until the matching left parenthesis is reached. The brackets are discarded.
Step 7: If the symbol scanned is an operator and has precedence higher or equal to the operator currently at the top,
then push the new operator onto the stack.
Step 8: If the symbol scanned is an operator and has precedence lower than the operator currently at the top, then
the operators are popped one by one until we get an operator with lower or equal precedence than the new
scanned operator. The operators popped are appended to the postfix expression.
Step 9: When the reversed infix string is fully scanned, the stack may still contain some operators. All the remaining
operators are popped and appended to the postfix string.
Step 10: Reverse the postfix expression to get the prefix equivalent.
Step 11: Stop.
Let us understand the concept with the following example.
5. Convert the following infix expression to its prefix form. [ISC 2020]
(X + Y)/(Z*W/V)
a. Stack Method
Ans. The reverse of the given expression = (V / W * Z) / (Y + X)
Symbol scanned Stack Postfix expression
Left parenthesis pushed
to stack (
Operand V sent to V
output (
Operator / pushed to
stack /
(
Operand W sent to V W
output /
(
Operator * has same
precedence as the * V W
operator / on top. So /
* pushed to stack (
Operand Z sent to V W Z
output *
/
(
507
Data Structures 507

