DS – Infix to Prefix Algorithm

Algorithm to convert Infix to Prefix using STACK:

1. Reverse the expression string.
2. Read next element in the input expression.
3. If it is an operand, output it.
4. If it is a closing parenthesis, push on to the Stack.
5. If it is an operator, then
   1. If the Stack is empty, push operator on Stack
   1. If the Top of stack is closing parenthesis, push operator on to the Stack.
   1. If the operator has “same or higher priority” than top of the Stack, push operator on to the Stack else Pop operator from the Stack and output it, repeat Step 5.
6. If the is an Opening parenthesis, pop operators from stack and output them until closing parenthesis is encountered. POP and discard closing parenthesis.
7. If there is more input go to step 2.
8. If no more input, un stack all operators and output.
9. Reverse Output expression that is Prefix