# Prefix To Infix

Convert a given Prefix Expression to Infix Expression using stack.

Example,

```Input: -*+abc/de
Output: ((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

1. Initialize a Stack.
2. Scan Prefix Expression from Right-To-Left.
1. If the scanned character is an operand, Push it to Stack.
2. 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.
3. Repeat step 2 until all characters of prefix expression are scanned.

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

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(N2).