Convert a given Prefix Expression to Infix Expression using stack.

Example,

Input:-*+abc/deOutput:((a+b)*c)-(d/e)

**Why do we convert Prefix Expression To Infix Expression?**

Expressions are usually evaluated in Postfix/Prefix form. This is because Postfix/Prefix Expressions do not contain parenthesis and precedence rules.

But Prefix/Postfix Expressions are hard to read especially if the expression is very large. Thus, a Prefix Expression may be converted to Infix Expression.

### Prefix to Infix Algorithm

- Initialize a
**Stack**. - Scan
**Prefix Expression**from**Right-To-Left**.- If the
**scanned character**is an operand, Push it to**Stack**. - If the
**scanned character**is an operator.- Pop Operands.
- Concatenate the operands and the operator to form a string.
- Insert
**“(“**and**“)”**at the beginning and end of the string. - Push the string to
**Stack**.

For example, if the scanned character is**“/”**and v1, v2 are operands popped from the stack then Push string**“(“+v1+”/”+v2+”)”**to**Stack**.

- If the
- Repeat step 2 until all characters of prefix expression are scanned.

Example, let the Prefix Expression be **“-*+abc/de”**

Prefix Expression | Stack | Description |
---|---|---|

-*+abc/de | e | Push e to stack. |

-*+abc/d | e, d | Push d to stack. |

-*+abc/ | (e/d) | Pop d Pop e Push “(d+’/’+e)” to stack. |

-*+abc | (d/e), c | Push c to stack. |

-*+ab | (d/e), c, b | Push b to stack. |

-*+a | (d/e), c, b, a | Push a to stack. |

-*+ | (d/e), c, (a+b) | Pop a Pop b Push “(a+’+’+b)” to stack. |

–* | (d/e), ((a+b)*c) | Pop (a+b) Pop c Push “((a+b)+’*’+c)” to stack. |

– | (((a+b)*c)-(d/e)) | Pop (a+b)*c Pop (d/e) Push “(((a+b)*c)+’-‘+(d/e))” to stack. |

Infix Expression: **(((a+b)*c)-(d/e))**

#### Pseudo Code

```
prefix: Input Infix Expression
FOR i = prefix.LENGTH – 1 TO 0 DO
IF prefix[i] is operand THEN
PUSH prefix[i] TO stack
IF prefix[i] is operator THEN
POP operands
CONCATENATE operands AND prefix[i]
TO SHOW OPERATION IN INFIX FORM
PUSH THE STRING OBTAINED TO STACK
END FOR
```

#### Program For Prefix to Infix Conversion

```
#include<iostream>
#include<string>
#include<stack>
using namespace std;
// returns true if C is operand
bool isOperand(char c) {
return c >= 'a' && c <= 'z';
}
string ConvertPrefixToInfix(string prefix) {
stack<string> stk;
string token;
for (int i = prefix.length() - 1; i >= 0; --i) {
if (isOperand(prefix[i])) {
token = prefix[i];
stk.push(token);
}
else {
// we are assuming that expression only contain binary operations
// in case expression contains multiple types of operators
// then number of operands popped depend on the type of operator
// for unary 1 operand is popped, for binary 2, for ternary 3 and so on
string v1 = stk.top();
stk.pop();
string v2 = stk.top();
stk.pop();
stk.push("("+v1+prefix[i]+v2+")");
}
}
return stk.top();
}
int main() {
string prefix;
cout << "Enter Prefix Expression: ";
cin >> prefix;
string infix = ConvertPrefixToInfix(prefix);
cout << "Infix Expression: " << infix << endl;
}
```

##### Output

**Note:**

We assume the expression only contains binary operators. If the expression contains multiple types of operators like unary, binary, ternary, etc, we must check the operator type before popping the operands from the stack.

#### Time Complexity

We convert Prefix Expression to Infix Expression in one pass. Thus, complexity should be **O(N)**.

But during each iteration, we are also performing string manipulation whose complexity is **O(N)**.

Hence, the time complexity of the algorithm is **O(N ^{2})**.

### References

https://en.wikipedia.org/wiki/Polish_notation

https://en.wikipedia.org/wiki/Infix