Lets see the precedence of the operators that will be used to convert the given infix to prefix expression and understand the logic for conversion.

Precedence

Logic for conversion

Do refer the code available the end of this section to understand the following theory.

1. Create two stacks using arrays of type character, one for operand stack and another one for operator stack.
2. There occurs a situation to perform the following operation:
   1. Pop the top of operand stack and save it as operand2.
   2. Once again pop the top of operand stack and save it as operand1.
   3. Copy the incoming operator into a temporary expression.
   4. Concat the operand1 and then operand2 to this temporary expression.
   5. Finally push this temporary expression to the operand stack.
3. Scan the infix expression from left to right.
4. If the character read is an operand then push it to the operand stack.
5. Else loop until the operator stack is not empty and stack precedence of top(of operator stack) is more than the input precedence.
   1. If the input character is ')' then perform step 2 operation until the top of stack is not '('.
   2. Pop the top of operator stack because it will obviously be '(' and break the loop(step 5).
   3. Else if the input character is not ')' then perform step 2 operation.
6. If the step 5 condition fails and input character is not ')' then push the operator into the operator stack.
7. After scanning all the characters of the infix expression, perform step 2 operation until the operator stack is not empty.
8. Return the top of operand stack.

Similar posts: Stack | Infix VS Postfix VS Prefix | Infix to Postfix | Evaluation of Postfix & Prefix Expressions