Prefix to Infix Conversion
Last Updated :
03 Aug, 2022
Infix : An expression is called the Infix expression if the operator appears in between the operands in the expression. Simply of the form (operand1 operator operand2).
Example : (A+B) * (C-D)
Prefix : An expression is called the prefix expression if the operator appears in the expression before the operands. Simply of the form (operator operand1 operand2).
Example : *+AB-CD (Infix : (A+B) * (C-D) )
Given a Prefix expression, convert it into a Infix expression.
Computers usually does the computation in either prefix or postfix (usually postfix). But for humans, its easier to understand an Infix expression rather than a prefix. Hence conversion is need for human understanding.
Examples:
Input : Prefix : *+AB-CD
Output : Infix : ((A+B)*(C-D))
Input : Prefix : *-A/BC-/AKL
Output : Infix : ((A-(B/C))*((A/K)-L))
Algorithm for Prefix to Infix:
- Read the Prefix expression in reverse order (from right to left)
- If the symbol is an operand, then push it onto the Stack
- If the symbol is an operator, then pop two operands from the Stack
Create a string by concatenating the two operands and the operator between them.
string = (operand1 + operator + operand2)
And push the resultant string back to Stack
- Repeat the above steps until the end of Prefix expression.
- At the end stack will have only 1 string i.e resultant string
Implementation:
C++
#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char x) {
switch (x) {
case '+':
case '-':
case '/':
case '*':
case '^':
case '%':
return true;
}
return false;
}
string preToInfix(string pre_exp) {
stack<string> s;
int length = pre_exp.size();
for (int i = length - 1; i >= 0; i--) {
if (isOperator(pre_exp[i])) {
string op1 = s.top(); s.pop();
string op2 = s.top(); s.pop();
string temp = "(" + op1 + pre_exp[i] + op2 + ")";
s.push(temp);
}
else {
s.push(string(1, pre_exp[i]));
}
}
return s.top();
}
int main() {
string pre_exp = "*-A/BC-/AKL";
cout << "Infix : " << preToInfix(pre_exp);
return 0;
}
|
Java
import java.util.Stack;
class GFG{
static boolean isOperator(char x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
public static String convert(String str)
{
Stack<String> stack = new Stack<>();
int l = str.length();
for(int i = l - 1; i >= 0; i--)
{
char c = str.charAt(i);
if (isOperator(c))
{
String op1 = stack.pop();
String op2 = stack.pop();
String temp = "(" + op1 + c + op2 + ")";
stack.push(temp);
}
else
{
stack.push(c + "");
}
}
return stack.pop();
}
public static void main(String[] args)
{
String exp = "*-A/BC-/AKL";
System.out.println("Infix : " + convert(exp));
}
}
|
Python3
def prefixToInfix(prefix):
stack = []
i = len(prefix) - 1
while i >= 0:
if not isOperator(prefix[i]):
stack.append(prefix[i])
i -= 1
else:
str = "(" + stack.pop() + prefix[i] + stack.pop() + ")"
stack.append(str)
i -= 1
return stack.pop()
def isOperator(c):
if c == "*" or c == "+" or c == "-" or c == "/" or c == "^" or c == "(" or c == ")":
return True
else:
return False
if __name__=="__main__":
str = "*-A/BC-/AKL"
print(prefixToInfix(str))
|
C#
using System;
using System.Collections;
class GFG{
static bool isOperator(char x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
public static string convert(string str)
{
Stack stack = new Stack();
int l = str.Length;
for(int i = l - 1; i >= 0; i--)
{
char c = str[i];
if (isOperator(c))
{
string op1 = (string)stack.Pop();
string op2 = (string)stack.Pop();
string temp = "(" + op1 + c + op2 + ")";
stack.Push(temp);
}
else
{
stack.Push(c + "");
}
}
return (string)stack.Pop();
}
public static void Main(string[] args)
{
string exp = "*-A/BC-/AKL";
Console.Write("Infix : " + convert(exp));
}
}
|
Javascript
<script>
function isOperator(x)
{
switch(x)
{
case '+':
case '-':
case '*':
case '/':
case '^':
case '%':
return true;
}
return false;
}
function convert(str)
{
let stack = [];
let l = str.length;
for(let i = l - 1; i >= 0; i--)
{
let c = str[i];
if (isOperator(c))
{
let op1 = stack[stack.length - 1];
stack.pop()
let op2 = stack[stack.length - 1];
stack.pop()
let temp = "(" + op1 + c + op2 + ")";
stack.push(temp);
}
else
{
stack.push(c + "");
}
}
return stack[stack.length - 1];
}
let exp = "*-A/BC-/AKL";
document.write("Infix : " + convert(exp));
</script>
|
Output
Infix : ((A-(B/C))*((A/K)-L))
Time Complexity: O(n)
Auxiliary Space: O(n)
Please Login to comment...