Prefix To Infix | Stack

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

Initialize a Stack.
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.
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²).

References

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