Infix to Prefix Conversion

Steps to convert infix expression to prefix

1. First, reverse the given infix expression.
2. Scan the characters one by one.
3. If the character is an operand, copy it to the prefix notation output.
4. If the character is a closing parenthesis, then push it to the stack.
5. If the character is an opening parenthesis, pop the elements in the stack until we find the corresponding closing parenthesis.
6. If the character scanned is an operator

• If the operator has precedence greater than or equal to the top of the stack, push the operator to the stack.
• If the operator has precedence lesser than the top of the stack, pop the operator and output it to the prefix notation output and then check the above condition again with the new top of the stack.

   7. After all the characters are scanned, reverse the prefix notation output.

 

Precedence order

 

Associativity order

 

Conversion of Infix to Prefix using Stack

K + L - M * N + (O^P) * W/U/V * T + Q

If we are converting the expression from infix to prefix, we need first to reverse the expression.

The Reverse expression would be:

Q + T * V/U/W * ) P^O(+ N*M - L + K

 

 The above expression, i.e., QTVUPO^*//*NM*LK+-++, is not a final expression. We need to reverse this expression to obtain the prefix expression.