Conversion of Prefix expression to Infix expression

Last Updated on April 27, 2023 by Prepbytes

Conversion of prefix expression to infix expression involves rearranging the operators and operands to follow the rules of infix notation while maintaining the order of operations. This can be achieved through recursive parsing of the prefix expression.

How to Convert Prefix to Infix?

You are given an arithmetic expression. Your task is Convert an arithmetic expression in prefix notation into the equivalent infix notation.

Sample Example :

Prefix Input : *-a/bc-/ade
Infix output : ((a-(b/c))*((a/d)-e))
Prefix input : *ab
Infix expression : (a*b)

Introduction to Arithmetic Notations

Any arithmetic expression consists of operands and operators. Notation is how we arrange our operators and operands to write the arithmetic expression.

There are three different notations for writing the Arithmetic expression :

• Infix expression: An infix expression is a mathematical or logical expression in which operators are written between the operands.

  For example => a + b * c Infix expressions are easy to read, write and understand by humans, but not by computer It’s costly, in terms of time and space, to process Infix expressions.

• Postfix expression: It is also known as Reverse Polish Notation. An expression is said to be in postfix notation if the operators in the expression are placed after the operands on which the operator works.

  For example => abc*+ It’s the most used notation for evaluating an arithmetic expression

• Prefix expression: It is known as Polish Notation. An expression is said to be in prefix notation if the operators in the expression are placed before the operands on which the operator works.

  For example => +a*bc

Precedence Order and Associativity of Operators

Approach for Prefix to Infix Converter

Here, is the prefix to infix using stack. The stack helps us store the operands. Whenever an operator is found, we pop two operands from the stack and push a new operand, which is the result of the current operator on the popped operands, into the stack with parenthesis. The final element at the top of the stack will be our infix expression.

Algorithm for Prefix to Infix Converter

Here, is the algorithm for prefix to infix converter:

• Start scanning the prefix expression from right to left.
• If the current character is an operand (a number or a variable), push it onto a stack.
• If the current character is an operator (+, -, *, /, ^), pop two operands from the stack and concatenates them with the operator in between to form an infix sub-expression. Then push the infix sub-expression onto the stack.
• Repeat steps 2 and 3 until the entire prefix expression has been scanned.
• The final infix expression will be the only item remaining on the stack.

NOTE: ‘+’ denotes the concatenation of strings.

Prefix to Infix Conversion Example with Dry Run

Code Implementation

#include <bits/stdc++.h>
using namespace std;

bool isOperand(char ch){
	return (ch>='a' && ch<='z') || (ch>='A' && ch <='Z');
}

string prefixToInfix(string prefix) {
  stack<string> st;
 
  int len = prefix.size();
  for (int i = len - 1; i >= 0; i--) {
  	if(isOperand(prefix[i])){
  		
  		st.push(string(1,prefix[i]));
  	   
  	}
  	else{
  		string operand1=st.top();
  		st.pop();
  		
  		string operand2=st.top();
  		st.pop();
  		
  		st.push("(" + operand1 + string(1,prefix[i]) + operand2 + ")");
  	}
  }
  return st.top();
}

int main() {
	
	string prefix="*-a/bc-/ade";
	string infix=prefixToInfix(prefix);
	cout<<"Prefix expression : "<<prefix<<endl;
	cout<<"Infix expression : "<<infix<<endl;
	
	return 0;
}

Conclusion In conclusion, a prefix to infix conversion using stack involves rearranging the operators and operands of the prefix expression to a format where the operators appear between the operands. This can be achieved by recursively evaluating the expression and adding parentheses around the sub-expressions as needed to maintain the correct order of operations. The resulting infix expression will have the same meaning as the original prefix expression but in a more traditional format.

Frequently Asked Questions(FAQs)

Q1. Why would I need to convert a prefix expression to infix? Ans: Infix notation is a more familiar and easier-to-read format for mathematical expressions than prefix notation. Converting a prefix expression to an infix can make it easier to understand and work with.

Q2. Is there a specific algorithm for prefix to infix conversion? Ans: Yes, there is a specific algorithm that can be used to convert a prefix expression to an infix. The algorithm involves scanning the expression from right to left, and for each operator encountered, forming a new sub-expression by combining the next two operands and the operator. The sub-expression is then added to a stack and the process is repeated until the entire expression is processed.

Q3. Can all prefix expressions be converted to infix notation? Ans: Yes, all prefix expressions can be converted to infix notation. However, some expressions may require the use of additional parentheses to maintain the correct order of operations.