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
   504   505   506   507   508   509   510   511   512   513   514