Prefix to Infix Conversion in Python

Infix: Infix expressions contain the operator in between the two operands. The operands can themselves contain operators. Though with respect to the middle operator, the expression will be an infix expression.

Infix expressions are of the form

Example: (X + Y) * (X1 + Y1)

Prefix: Prefix expressions contain the operator in front of the two operands. The operands can themselves contain operators. Though with respect to the operator present at the beginning, the expression will be a prefix expression.

Prefix expressions are of the form

Example: *+ XY - X1Y1 (Infix : (X + Y) * (X1 + Y1))

The task is if we are given a prefix expression, we have to convert it to an infix expression.

Computers are designed to compute the expressions most often in postfix or sometimes in prefixes. However, it is not easy for us to understand and compute a prefix expression. We are trained to solve infix expressions. Therefore, we need to convert a prefix expression to an infix expression.

Here are some sample inputs and outputs for a better understanding of the problem at hand.

Examples

Input Prefix: *+ XY - X1Y1

Output Infix: ((X + Y) * (X1 + Y1))

Input Prefix: *+ P / QR -/ STU

Output Infix: ((P - (Q / R)) * ((P / T) - U))

Algorithm for Prefix to Infix Conversion

1. First, we will read the given prefix expression in reverse order, i.e., from right to left.
2. We will use a stack to store the operands. So, if we encounter a symbol, we will push it into the stack
3. If we encounter an operator, then we will pop two operands out of the stack.
4. At last, we will create a concatenated Python string of the two operands and put the operator between them.
5. infix = (operand_1 + operator + operand_2)
6. Then we will push the infix string back into the stack.
7. We will repeat the above steps until we reach the end of the given prefix expression.
8. At the end of the execution, we will be left with a single string of the infix expression.

Code

Output:

The infix string is: ((P+(Q/R))*((S/T)-U))

Time Complexity: This algorithm has O(n) time complexity, where n is the length of the given prefix string.

Auxiliary Space: Since we are string the symbols of the string in the stack, this program takes O(n) memory space.