Conversion Infix notation to Prefix notation

Problem statement

Given an Infix arithmetic expression , convert it 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

Introduction to Arithmetic Notations

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

There are three different notations for writing the Arithmetic expression :

  1. Infix expression An expression is said to be in infix notation if the operators in the expression are placed in between the operands on which the operator works.
    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

  2. Postfix expression (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 most used to notation for evaluating arithmetic expression

  3. Prefix expression (or 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

PrecedenceTypeOperatorsAssociativity
1Postfix() [] -> . ++ —Left to Right
2Unary+ – ! ~ ++ — (type)* & sizeofRight to Left
3Multiplicative* / %Left to Right
4Additive+ –Left to Right
5Shift<<, >>Left to Right
6Relational< <= > >=Left to Right
7Equality== !=Left to Right
8Bitwise AND&Left to Right
9Bitwise XOR^Left to Right
10Bitwise OR|Left to Right
11Logical AND&&Left to Right
12Logical OR||Left to Right
13Conditional?:Right to Left
14Assignment= += -+ *= /= %= >>= <<= &= ^= |=Right to Left
15Comma,Left to Right

In this article we are going to see how we can convert Infix expressions to prefix expressions . For the simplicity and understanding purpose , we will consider only β€˜+’ , β€˜-’ ,’/’ , β€˜*’ , β€˜(’ and β€˜)’ .

Approach

To convert Infix to prefix , we first reverse the input infix expression . We also change β€˜(’ to β€˜)’ and β€˜)’ to β€˜(’ . Then we apply infix to the postfix conversion algorithm on the obtained expression . The expression obtained by this is not the final prefix expression yet , we need to reverse it . After reversing the obtained postfix expression we get the required prefix expression .

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 => / , * , + , –

Algorithm

  • Reverse the given infix expression , change β€˜(’ to β€˜)’ and β€˜)’ to β€˜)’ .

  • Convert this expression to postfix using the following steps .

  • Scan all the symbols one by one from left to right in the obtained Infix Expression.

  • If the reading symbol is operand, then immediately append it to the Postfix Expression .

  • If the reading symbol is left parenthesis ‘( ‘, then Push it onto the Stack.

  • If the reading symbol is right parenthesis ‘)’, then Pop all the contents of the stack until the respective left parenthesis is popped and append each popped symbol to Postfix Expression.

  • If the reading symbol is operator (+ , – , * , /), then Push it onto the Stack. However, first pop the operators which are already on the stack that have higher or equal precedence than the current operator and append them to the postfix . If open parenthesis is there on top of the stack then push the operator into the stack.

  • Keep repeating the above steps until all symbols are exhausted . If the input is over, pop all the remaining symbols from the stack and append them to the postfix .

  • Now reverse this postfix expression , to get the final prefix expression .

Infix to Prefix example using dry run

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;
}

This article tried to discuss infix to prefix conversion. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at PrepBytes.

Leave a Reply

Your email address will not be published. Required fields are marked *