In this tutorial We have explored an algorithm to convert a given Postfix expression to Infix expression using Stack.

## Algorithm For Postfix to Infix Conversion

Iterate the given expression from left to right, one character at a timeStep 1 :If a character is operand, push it to stack.Step 2:If a character is an operator, if there are fewer than 2 values on the stack give error "insufficient values in expression" goto Step 4 else pop 2 operands from stack create a new string and by putting the operator between operands. push this string into stack Repeat Steps 1 and 2Step 3:At last there will be only one value or one string in the stack which will be our infix expressionStep 4:Exit

## Some important terminology

**Postfix Expression**

In Postfix Expression operator appear after operand, this expression is known as Postfix operation.**Infix**

If Infix Expression operator is in between of operands, this expression is known as Infix operation.

## Steps to Convert Postfix to Infix

- Start Iterating the given Postfix Expression from Left to right
- If Character is operand then push it into the stack.
- If Character is operator then pop top 2 Characters which is operands from the stack.
- After poping create a string in which comming operator will be in between the operands.
- push this newly created string into stack.
- Above process will continue till expression have characters left
- At the end only one value will remain if there is integers in expressions. If there is character then one string will be in output as infix expression.

## Example to Convert Postfix to Infix

**Postfix Expression :** abc-+de-+

Token | Stack | Action |

a | a | push a in stack |

b | a, b | push b in stack |

c | a, b, c | push c in stack |

– | a , b – c | pop b and c from stack and put – in between and push into stack |

+ | a + b – c | pop a and b-c from stack and put + in between and push into stack |

d | a + b – c, d | push d in stack |

e | a + b – c, d , e | push e in stack |

– | a + b – c, d – e | pop d and e from stack and put – in between and push into stack |

+ | a + b – c + d – e | pop a + b – c and d – e from stack and put + in between and push into stack |

## Solution for Postfix expression

**postfix expression:** 752+*415-/-

Token | Stack | Action |

7 | 7 | push 7 in stack |

5 | 7, 5 | push 5 in stack |

2 | 7 , 5, 2 | push 2 in stack |

+ | 7, 7 | pop 2 and 5 from stack, sum it and then again push it |

* | 49 | pop 7 and 7 from stack and multiply it and then push it again |

4 | 49, 4 | push 4 in stack |

1 | 49, 4, 1 | push 1 in stack |

5 | 49, 4, 1, 5 | push 5 in stack |

– | 49, 4, -4 | pop 5 and 1 from stack |

/ | 49, -1 | pop 4 and 4 from stack |

– | 50 | pop 1 and 49 from stack |

## Java Program to Convert Infix to Postfix

```
import java.util.*;
public class Main {
public static String convert(String exp) {
int len = exp.length();
Stack<String> stack = new Stack<>();
for (int i = 0; i < len; i++) {
char c = exp.charAt(i);
if (c == '*' || c == '/' || c == '^' || c == '+' || c == '-') {
String s1 = stack.pop();
String s2 = stack.pop();
String temp = "(" + s2 + c + s1 + ")";
stack.push(temp);
} else {
stack.push(c + "");
}
}
String result = stack.pop();
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter Postfix Expression: ");
String exp = sc.nextLine();
System.out.println("Infix Expression: " + Main.convert(exp));
}
}
```

**Output**

```
Please enter Postfix Expression:
abc-+de-+
Infix Expression: ((a+(b-c))+(d-e))
```

#### Explanations

The Java program provided is designed to convert expressions from postfix notation to infix notation using a stack. It leverages the `Stack`

class from the Java `util`

package to perform this operation. Here’s a breakdown of how the program works:

##### Import Statement

`import java.util.*;`

This line imports the Java utility package, which contains the `Stack`

class used in this program.

##### The `Main`

Class

The class named `Main`

encapsulates the entire program.

##### The `convert`

Method

```
for (int i = 0; i < len; i++) {
char c = exp.charAt(i);
```

This is a static method that takes a single `String`

parameter (`exp`

) representing the postfix expression and returns a `String`

that represents the converted infix expression.

**Variables**:

`len`

: Stores the length of the postfix expression.

`stack`

: A `Stack<String>`

object used to hold parts of the expression during conversion.

**The Conversion Loop**:

```
for (int i = 0; i < len; i++) {
char c = exp.charAt(i);
```

This loop iterates over each character in the postfix expression.Inside the loop, the program checks if the current character (`c`

) is an operator (`*`

, `/`

, `^`

, `+`

, `-`

). If it is, the program performs the following steps:

**Result Compilation**:

```
String result = stack.pop();
return result;
```

`return result; `

After the loop completes, the only element left on the stack is the fully converted infix expression. This is popped from the stack and returned.

##### The main Method

```
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Please enter Postfix Expression: ");
String exp = sc.nextLine();
System.out.println("Infix Expression: " + Main.convert(exp));
}
```

This is the entry point of the program. It prompts the user to input a postfix expression, reads the input using a `Scanner`

object, and then calls the `convert`

method to transform the input into infix notation. Finally, it prints the resulting infix expression.

### How the Stack Works in This Context

The stack is used to temporarily hold operands. When an operator is encountered, the two most recent operands are popped from the stack, combined with the operator in infix format, and the resulting string is pushed back onto the stack. This process continues until the entire expression is converted to infix notation. The use of a stack is crucial for correctly handling the order of operations and parentheses in the resulting infix expression.