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++
// C++ Program to convert prefix to Infix#include <iostream>#include <stack>using namespace std;// function to check if character is operator or notbool isOperator(char x) { switch (x) { case '+': case '-': case '/': case '*': case '^': case '%': return true; } return false;}// Convert prefix to Infix expressionstring preToInfix(string pre_exp) { stack<string> s; // length of expression int length = pre_exp.size(); // reading from right to left for (int i = length - 1; i >= 0; i--) { // check if symbol is operator if (isOperator(pre_exp[i])) { // pop two operands from stack string op1 = s.top(); s.pop(); string op2 = s.top(); s.pop(); // concat the operands and operator string temp = "(" + op1 + pre_exp[i] + op2 + ")"; // Push string temp back to stack s.push(temp); } // if symbol is an operand else { // push the operand to the stack s.push(string(1, pre_exp[i])); } } // Stack now contains the Infix expression return s.top();}// Driver Codeint main() { string pre_exp = "*-A/BC-/AKL"; cout << "Infix : " << preToInfix(pre_exp); return 0;} |
Java
// Java program to convert prefix to Infix import java.util.Stack;class GFG{// Function to check if character// is operator or not static boolean isOperator(char x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false;}// Convert prefix to Infix expression public static String convert(String str){ Stack<String> stack = new Stack<>(); // Length of expression int l = str.length(); // Reading from right to left for(int i = l - 1; i >= 0; i--) { char c = str.charAt(i); if (isOperator(c)) { String op1 = stack.pop(); String op2 = stack.pop(); // Concat the operands and operator String temp = "(" + op1 + c + op2 + ")"; stack.push(temp); } else { // To make character to string stack.push(c + ""); } } return stack.pop();}// Driver codepublic static void main(String[] args){ String exp = "*-A/BC-/AKL"; System.out.println("Infix : " + convert(exp));}}// This code is contributed by abbeyme |
Python3
# Python Program to convert prefix to Infixdef prefixToInfix(prefix): stack = [] # read prefix in reverse order i = len(prefix) - 1 while i >= 0: if not isOperator(prefix[i]): # symbol is operand stack.append(prefix[i]) i -= 1 else: # symbol is operator 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# Driver codeif __name__=="__main__": str = "*-A/BC-/AKL" print(prefixToInfix(str)) # This code is contributed by avishekarora |
C#
// C# program to convert prefix to Infix using System;using System.Collections;class GFG{ // Function to check if character// is operator or not static bool isOperator(char x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false;} // Convert prefix to Infix expression public static string convert(string str){ Stack stack = new Stack(); // Length of expression int l = str.Length; // Reading from right to left 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(); // Concat the operands and operator string temp = "(" + op1 + c + op2 + ")"; stack.Push(temp); } else { // To make character to string stack.Push(c + ""); } } return (string)stack.Pop();} // Driver codepublic static void Main(string[] args){ string exp = "*-A/BC-/AKL"; Console.Write("Infix : " + convert(exp));}}// This code is contributed by rutvik_56 |
Javascript
<script> // Javascript program to convert prefix to Infix // Function to check if character // is operator or not function isOperator(x) { switch(x) { case '+': case '-': case '*': case '/': case '^': case '%': return true; } return false; } // Convert prefix to Infix expression function convert(str) { let stack = []; // Length of expression let l = str.length; // Reading from right to left 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() // Concat the operands and operator let temp = "(" + op1 + c + op2 + ")"; stack.push(temp); } else { // To make character to string stack.push(c + ""); } } return stack[stack.length - 1]; } let exp = "*-A/BC-/AKL"; document.write("Infix : " + convert(exp)); // This code is contributed by suresh07.</script> |
Output
Infix : ((A-(B/C))*((A/K)-L))
Time Complexity: O(n)
Auxiliary Space: O(n)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
