Infix, Prefix and Postfix Conversion in Stack

One of the most important applications of a stack is in the conversion and evaluation of mathematical expressions. In programming and computation, expressions are written in different notations depending on how operators and operands are arranged.

An expression is a combination of:

• Operands (numbers or variables)
• Operators (such as +, −, ×, ÷)

There are three main types of expression notations:

• Infix Notation
• Prefix Notation
• Postfix Notation

Types of Expression Notations

1. Infix Notation

In infix notation, the operator is written between the operands.

• General form: A + B
• This is the most common form used in mathematics

However, infix expressions require rules of precedence and parentheses, which makes them slightly complex for computers to evaluate directly.

Example:

3 + 4 × 2

2. Prefix Notation (Polish Notation)

In prefix notation, the operator is written before the operands.

• General form: + A B
• No need for parentheses

Example:

+ 3 * 4 2

3. Postfix Notation (Reverse Polish Notation)

In postfix notation, the operator is written after the operands.

• General form: A B +
• No need for parentheses
• Easy for computers to evaluate using a stack

Example:

3 4 2 * +

Operator Precedence and Associativity

To correctly convert infix expressions, we must understand precedence rules.

Operator Precedence (Highest to Lowest):

• Parentheses ( ) → Highest priority (forces evaluation order)
• Exponentiation ^
• Multiplication, Division *, /, %
• Addition, Subtraction +, -

Associativity Rules:

• Operators like +, -, *, / are left to right
• Exponentiation ^ is usually right to left

These rules are important because they determine how expressions are evaluated and converted.

Infix to Postfix Conversion using Stack

Since infix expressions are not easy for machines to evaluate directly, they are converted into postfix form using a stack.

The stack is mainly used to:

• Store operators temporarily
• Ensure correct precedence handling

Algorithm

The process of converting infix to postfix involves scanning the expression from left to right and applying rules based on the type of symbol encountered.

• Start with an empty stack and an empty output
• Read each symbol one by one

Processing Rules:

• If the symbol is an operand
  • Directly add it to the output
• If it is an opening parenthesis (
  • Push it onto the stack
• If it is a closing parenthesis )
  • Pop from the stack until opening parenthesis is found
• If it is an *operator (+, -, , /, ^)
  • Compare precedence with top of stack
  • Pop higher or equal precedence operators
  • Then push the current operator
• After scanning the entire expression
  • Pop all remaining operators from the stack

Example of Infix to Postfix Conversion

Given Expression:

3 + 4 * 2 / (1 - 5)

Step-by-Step Idea:

• Operands go directly to output
• Operators are pushed based on precedence
• Parentheses control grouping

Step-by-Step Table

Final Answer:

Postfix: 3 4 2 * 1 5 - / +

Another Example (Conceptual)

Infix Expression:

(A + (B * C - (D / E ^ F) * G) * H)

Step-by-Step Table

Final Answer Postfix: A B C * D E F ^ / G * - H * +

This example shows how stacks handle:

• Nested parentheses
• Multiple operators
• Precedence correctly

Evaluation of Postfix Expression

After conversion, postfix expressions are evaluated using a stack:

• Push operands into stack
• When an operator is found:
  • Pop two operands
  • Perform operation
  • Push result back

Example:

3 4 2 * +

Steps:

• Push 3, 4, 2
• Multiply 4 × 2 = 8
• Add 3 + 8 = 11

Final Answer = 11

Infix to Prefix Conversion using Stack

Prefix notation (also called Polish Notation) is a way of writing expressions where the operator comes before the operands.

Example

Idea Behind Infix to Prefix Conversion

In infix notation, operators are written between operands:

A + B

In prefix notation, operators are written before operands:

+ A B

Stacks are commonly used to convert infix expressions into prefix expressions.

Algorithm for Infix to Prefix Conversion

1. Reverse the infix expression
2. Replace '(' with ')' and ')' with '('
3. Convert the reversed expression into postfix
4. Reverse the postfix expression
5. The result is the prefix expression

Steps to Convert Infix to Prefix

The easiest method is:

Step 1: Reverse the Infix Expression

While reversing:

• Replace ( with )
• Replace ) with (

Step 2: Convert the Reversed Expression into Postfix

• Use the normal infix-to-postfix algorithm.

Step 3: Reverse the Postfix Expression

• The final reversed result becomes the Prefix expression.

Example of Infix to Prefix Conversion

Given Infix Expression

(A + B) * C

Step 1: Reverse the Expression

Original: ( A + B ) * C

After reverse and swapping brackets: C * ( B + A )

Step 2: Convert Reversed Infix to Postfix

Expression: C * ( B + A )

Postfix Result: C B A + *

Step 3: Reverse the Postfix Expression

Reverse: * + A B C

Final Prefix Expression: * + A B C

Applications of Prefix Notation

• Expression evaluation in compilers
• Stack-based calculations
• Syntax tree generation
• Mathematical expression parsing
• Artificial Intelligence systems

Advantages of Prefix Notation

• No need for parentheses
• Faster expression evaluation
• Easy for stack implementation
• Removes ambiguity in expressions

Time and Space Complexity

Where n is the number of symbols in the expression.

Why Stack is Used in Conversion?

Stacks are ideal for this problem because:

• They temporarily store operators
• They help process operators in reverse order (LIFO)
• They ensure correct precedence and associativity

Without a stack, handling nested expressions and precedence would be very complex.

Conclusion

Expression conversion is an important application of stacks in computer science.

• Infix notation is human-friendly but complex for machines
• Postfix and prefix notations are machine-friendly
• Stack plays a key role in:
  • Handling precedence
  • Managing operators
  • Simplifying evaluation

Because of this, stacks are widely used in:

• Compilers
• Calculators
• Expression evaluators

Practice Questions

Convert the following Infix expression to Postfix notation using Stack.

1. ( A + B ) * ( C + D ) / E
2. A + ( B * C - ( D / E ^ F ) * G ) * H
3. ( A + B ) * ( C - D + E ) / ( F + G * H )
4. A * ( B + C * ( D - E ) ) + F / ( G - H + I )
5. ( A + B * ( C ^ D - E ) ) * ( F + G / H - I )
6. A + B * C - D / E + ( F * G - H / I ) * J
7. ( ( A + B ) * ( C - D ) ) / ( E + F * ( G - H ) )
8. ( A + ( B * C - ( D / E ^ F ) * G ) * H ) - I
9. ( ( A + B ) * ( C - D + E ) / ( F + G * H ) ) - I
10. A * ( B + C * ( D - E ) ) + F / ( G - H + I )
11. ( A + B * ( C ^ D - E ) ) * ( F + G / H - I )
12. ( ( A + B) * ( C - D ) ) / ( E + F * ( G - H ) )
13. ( A + B * C - D / E + ( F * G - H / I ) * J )
14. ( ( A * B ) + ( C / D ) - ( E ^ F + G * H ) ) / I
15. ( A * ( B + C ) - ( D / E ^ F ) + ( G - H * I ) / J)

Convert the following Infix expression into Prefix notation using stack

1. ( A + ( B * C - ( D / E ^ F ) * G ) * H )
2. ( ( A + B ) * ( C - D ) + E / F ) * ( G + H )
3. ( A * ( B + C ) - D / E + F ) * ( G - H )
4. ( ( A + B * C ) / ( D - E ) ) + ( F * G - H )
5. ( A + B * ( C ^ D - E ) ^ ( F + G * H ) - I )
6. ( A + ( B - C ) * ( D / E ^ F ) + G ) * H
7. ( ( A + B ) * ( C + D ) - ( E - F ) / G ) + H
8. A + B * ( C ^ D - E ) ^ ( F + G * H ) - I
9. ( A + ( B * C - ( D / E ^ F ) * G ) * H ) - I
10. ( ( A + B ) * ( C - D + E ) / ( F + G * H ) ) - I
11. A * ( B + C * ( D - E) ) + F / (G - H + I )
12. ( A + B * ( C ^ D - E ) ) * ( F + G / H - I )
13. ( A + B * C - D / E + ( F * G - H / I ) * J )
14. ( ( A * B ) + ( C / D ) - ( E ^ F + G * H ) ) / I
15. ( A * ( B + C ) - ( D / E ^ F ) + ( G - H * I ) / J )