Conversion Infix notation to Prefix notation

Last Updated on April 25, 2023 by Prepbytes

The conversion from infix notation to prefix notation involves reversing the order of the expression, replacing each operator with its corresponding prefix operator, and swapping the positions of each operand. The final result is a prefix expression with the operator appearing before the operands.

Arithmetic Notations

Arithmetic notations are different ways of writing arithmetic expressions using symbols and rules. There are three common arithmetic notations:

• Infix notation: Infix notation is a way of writing mathematical expressions where the operator is placed between the two operands.. For example, the expression "3 + 4" is in infix notation.
• Prefix notation: Prefix notation is also known as Polish notation. It eliminates the need for parentheses and can be evaluated without the use of precedence rules. For example, the expression "+ 3 4" is in prefix notation.
• Postfix notation: Postfix notation is also known as Reverse Polish notation. It eliminates the need for parentheses and can be evaluated without the use of precedence rules. In postfix notation, the operator appears after the operands. For example, the expression "3 4 +" is in postfix notation.

How to Convert Infix to Prefix?

Given an infix arithmetic expression , convert the infix expression into an equivalent prefix expression.

Expression will be given in the form of string , where alphabetic characters i.e a-z or A-Z denotes operands and operators are ( + , – , * , / ) . Expression can also have brackets i.e ‘(’ and ‘)’.

Sample example :

Input infix expression : a * ( b + c + d)

Output prefix expression : *a+b+cd

Input infix expression : b*c

Output prefix expression : *bc

Precedence order and Associativity of Operators

Infix to Prefix Examples

Here, is the infix to prefix examples:

• Consider the infix expression: (3 + 4 * 2) / (1 – 5)
• Reverse the infix expression: )5 – 1(/ )2 * 4 + 3(
• Convert all opening brackets to closing brackets and vice versa: ( )2 * 4 + 3( )/ 1 – 5(
• The modified infix expression is: )5 – 1(/ )2 * 4 + 3(
• Apply the infix to postfix algorithm on the modified infix expression:
• The postfix expression is: / * 4 + 3 ( – 1 5 ) 2 5
• Reverse the postfix expression to obtain the prefix expression: 5 2 ) ( 3 + 4 * / 1 – 5
• Therefore, the prefix notation of the given infix expression is: 5 2 ) ( 3 + 4 * / 1 – 5

Note: Parentheses are used to override the precedence of operators , and it can be nested parentheses which need to be evaluated from inner to outer .

Precedence Order

In descending order => / , * , + , –

Infix to Prefix Algorithm

Here,is the infix to prefix algorithm:

• Create an empty stack and an empty output string.
• Reverse the infix expression: Reverse the order of all elements in the infix expression, including operands and operators.
• Iterate through the reversed infix expression from left to right.
• If the current character is an operand (number or variable), append it to the output string.
• If the current character is a closing bracket ‘)’, push it onto the stack.
• If the current character is an operator or an opening bracket ‘(‘, compare its precedence with the precedence of the operator at the top of the stack.
• If the current operator has higher precedence than the operator at the top of the stack or the stack is empty, push the current operator onto the stack.
• If the current operator has lower or equal precedence than the operator at the top of the stack, pop the operators from the stack and append them to the output string until an operator with lower precedence is encountered or the stack becomes empty. Then push the current operator onto the stack.
• If the current character is an opening bracket ‘(‘, pop the operators from the stack and append them to the output string until the corresponding closing bracket ‘)’ is encountered. Discard the closing bracket.
• Repeat steps 4 to 9 until all characters in the reversed infix expression have been processed.
• Pop the remaining operators from the stack and append them to the output string.
• Reverse the output string to obtain the prefix expression.

How to Design Infix to Prefix Algorithm

Dry Run for Infix to Prefix Example

Code Implementation

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

int precedence(char ch){
	switch(ch){
		case '-':
		case '+':
			return 1;
		case '*':
		case '/':
			return 2;
		default:
			return -1;
	}
}
bool isOperand(char ch){
	return (ch>='a' && ch<='z') || (ch>='A' && ch <='Z');
}

string infixToPostfix(string infix){
	int n=infix.size();
	stack<char> st;
	string postfix;
	for(int i=0;i<n;i++){
		if(isOperand(infix[i])){
			//step 2
			postfix.push_back(infix[i]);
		}
		else if(infix[i] == '('){
			//step 3
			st.push('(');
		}
		else if(infix[i] == ')'){
			//step 4
			while( st.top() != '(' ){
				postfix.push_back(st.top());
				st.pop();
			}
			st.pop();
			
		}
		else{
			//step 5
			while(!st.empty() && st.top() != '(' && precedence(st.top()) >= precedence(infix[i])){
				postfix.push_back(st.top());
				st.pop();
			}
			st.push(infix[i]);
		}
	}
	
	while(!st.empty()){
		postfix.push_back(st.top());
		st.pop();
	}
	return postfix;
}
string infixToPrefix(string infix){
	reverse(infix.begin(),infix.end());
	for(int i=0;i<infix.size();i++){
		if(infix[i] == ')')infix[i]='(';
		else if(infix[i] =='(')infix[i]=')';
	}
	string prefix=infixToPostfix(infix);
	reverse(prefix.begin(),prefix.end());
	return prefix;
}
int main() {
	// your code goes here
	string infix="a*(b+c+d)";
	string prefix=infixToPrefix(infix);
	cout<<"Infix expression : "<<infix<<endl; 
	cout<<"Prefix expression : "<<prefix<<endl;
	return 0;
}

Conclusion

In conclusion,Infix to prefix notation conversion is a powerful tool for manipulating arithmetic expressions in various contexts, including computer programming and mathematics. By reversing the order of the expression, replacing each operator with its corresponding prefix operator, and swapping the positions of each operand, we can generate a prefix notation that is easier to parse and evaluate, without the need for parentheses or precedence rules.

Frequently Asked Questions(FAQs):

Q1. What is an infix expression? Ans: An infix expression is a mathematical expression where operators are placed between operands, e.g. 3 + 4, (6 – 2) * 5, etc.

Q2. What is a prefix expression? Ans: A prefix expression is a mathematical expression where the operator appears before the operands, e.g. + 3 4, * – 6 2 5, etc.

Q3. Why do we need to convert infix to prefix notation? Ans: Prefix notation is useful for evaluating mathematical expressions in computer programs since it eliminates the need for parentheses and ensures a consistent order of operations. It is also easier to parse and evaluate than infix notation.

Q4. What is the algorithm for converting infix to prefix notation? Ans: The algorithm involves reversing the infix expression, iterating through it from left to right, and using a stack and an output string to keep track of the operators and operands. At the end, the output string is reversed to obtain the prefix expression.

Q5. What is the difference between infix and prefix notation? Ans: In infix notation, the operators are placed between the operands, while in prefix notation, the operator appears before the operands. Infix notation can be ambiguous due to the use of parentheses and the order of operations, while prefix notation eliminates these ambiguities

Q6. Why is it necessary to reverse the infix expression before converting it to prefix notation? Ans: Reversing the infix expression allows us to process the operators in the correct order when converting to prefix notation. By iterating from left to right through the reversed expression, we can ensure that the operators are applied in the correct order.