Infix to Prefix conversion Algorithm with example

In infix notation, the operator (like +, -, *, /) is written between the two numbers or operands. For example, in the expression A + B, the plus sign comes in the middle. This is the form we use in everyday math, but computers need extra rules like brackets to know the order of operations.

In prefix notation (also called Polish notation), the operator is written before the operands. For example, the infix expression A + B is written as + A B in prefix form. Prefix notation does not need brackets to show which operation comes first, so it is easier for computers to evaluate expressions.

To convert Infix to prefix using the stack, first reverse the infix expression and at last again reverse the output expression to get prefix expression. We have operator’s stack, output’s stack and one input string. Operator’s stack works as FILO(First In Last Out). Output’s stack works as FIFO (First In First Out).

Stack-Based Method for Infix to Prefix Conversion

To convert an infix expression to a prefix expression using a stack, we follow these steps: First, reverse the infix expression. Then, we process it using two stacks – one for operators and one for the output – and at the end, reverse the output to get the final prefix expression.

• The operator stack follows FILO (First In Last Out), meaning the last operator pushed is used first.
• The output stack works like FIFO (First In First Out), meaning the first element pushed comes out first.
• We also have the input string, which is the expression we want to convert.

By carefully pushing operators and operands into these stacks and following precedence rules, we can successfully convert an infix expression into its equivalent prefix form.

Infix to Prefix Conversion Algorithm

Iterate the given expression from left to right, one character at a time.

Step 1:

• Reverse the given expression.

Step 2:

• If the scanned character is an operand, put it into the prefix expression.

Step 3:

• If the scanned character is an operator and the operator’s stack is empty, push the operator into the operator’s stack.

Step 4:

• If the operator’s stack is not empty, check the following possibilities:
  • If the precedence of the scanned operator is greater than the topmost operator of the operator’s stack, push this operator into the stack.
  • If the precedence of the scanned operator is less, pop operators from the operator’s stack until you find a lower precedence operator.
  • If the precedence is equal, then:
    • Check the associativity of the operator.
    • If left-to-right, simply push into the stack.
    • If right-to-left, pop operators from the stack until a lower precedence operator is found.
  • If the scanned character is an opening bracket (, push it into the operator’s stack.
  • If the scanned character is a closing bracket ), pop operators from the stack until an opening bracket ( is found.
• Repeat Steps 2, 3, and 4 until all characters of the expression are processed.

Step 5:

• Pop out all the remaining operators from the operator’s stack and append them to the prefix expression.

Step 6:

• Exit

Infix to Prefix conversion example

Infix Expression: (A+B)+C-(D-E)^F

First reverse the given infix expression

After Reversing: F^)E-D(-C+)B+A(

Now reverse the expression to get prefix expression ++AB-C^-DEF