An Arithmetic expression can be written in three different but equivalent ways called notations, based on the use of the operator in the expression. They are,
 Infix Notation
 Prefix (Polish) Notation
 Postfix (Reverse Polish) Notation
Infix Notation
Infix notation is of the form  operator in between operands. Eg, a + b * c. It is easy for humans to write and understand infix notation. But deriving an algorithm for evaluating an infix notation is difficult and costly in terms of space and time complexity. So, we convert infix notation to one of the latter notations before evaluating the result.
Prefix Notation
In prefix notation, the operators are prefixed to operands, eg, the equivalent prefix notation for Infix a+b is +ab. This notation is also termed as Polish Notation.
Postfix Notation
In Postfix Notation, the operators are postfixed to operands, eg, the postfix notation ab+ is equivalent to infix notation a+b. This style of notation is also called Reverse Polish Notation. Later in this section, we will study an algorithm which converts infix to prefix and postfix notations.
To convert an expression from infix to prefix or postfix, we need to take care of operator Precedence order and Associativity.
Precedence Order
When there are more than one operator in the expression, then the order of their evaluation is decided by the operator precedence over others. For eg, consider the expression a + b * c, here b*c should be evaluated first as the precedence of multiplication is higher than addition. The priority or precedence of the operators is shown in the tabular format later in this section.
Associativity
The rule for operators having the same precedence order is described by their Associativity. For example, consider the expression a + b  c. Here, the precedence order of “+” and “” is the same and both are left associative, therefore, (a+b) is evaluated first.
The Binary operator’s precedence order (tophighest to downlowest) and associativity is shown below in the table.
Sr. no 
Operator 
Associativity 
1 
Exponentiation (^) 
Right Associative 
2 
Multiplication(*) and Division (/) 
Left Associative 
3 
Addition(+) and Subtraction() 
Left Associative 
Note: The above behavior can be altered using parentheses in the expression. For example, in the expression (a+b)*c, the a+b part of the expression will be evaluated first in spite of multiplication having higher precedence than addition.
Infix to Postfix Algorithm
To convert infix notation to postfix notation, we will use a stack data structure and store the postfix result into a variable output. The algorithm is as follows,
 Scan the infix expression from left to right.
 If the scanned character is an operand, append it to the output variable.
 Else if it is an operator, then check the following condition.
3.1 If the stack is empty or the top of the stack contains open braces ‘(‘ or the precedence order of the scanned (incoming) operator is greater than the operator at the top of the stack, then push the scanned (incoming) operator to the stack.
3.2 Else pop all the operators from the stack which are greater than or equal to the scanned operator or until open parenthesis is encountered or the stack becomes empty, and push the scanned operator to the stack.  If the scanned character is an open parenthesis “(“, then push it onto the stack.
 If the scanned character is a close parenthesis “)”, then pop all the operators to the output until open parenthesis “(“ is encountered, and discard the open parenthesis and the scanned character (close parenthesis).
 Repeat steps from 2 to 5 until all the characters in the infix are scanned.
 Pop all the remaining operators and empty the stack to the output variable.
 Print the output variable.
Find below the working of the Infix to Postfix algorithm for expression a * (b + c) / d,
Steps 
Stack 
Scanned Character 
Output 
Step used from Infix to Prefix algorithm 
Initially 
[Empty Stack] 



1 
[Empty Stack] 
d 
d 
4. 
2 
/ 
/ 
d 
5.1 
3 
/( 
( 
d 
6. 
4 
/( 
c 
dc 
4. 
5 
/(+ 
+ 
dc 
5.1 
6 
/(+ 
b 
dcb 
4. 
7 
/ 
) 
dcb+ 
7. 
8 
* 
* 
dcb+/ 
5.2 
9 
* 
a 
dcb+/a 
4. 
10 
[Empty Stack] 
End 
dcb+/a* 
9 
11 
Reverse the output variable 
*a/+bcd 
10. 
Therefore, the Postfix expression of a * (b + c) / d is abc+*d/
 C/C++
 Python
 Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator(including '(') or not.
int operatorOrNot(char ch)
{
if (ch == '^'  ch == '/'  ch == '*'  ch == '+'  ch == ''  ch == '(')
return 1;
return 0;
}
// Priority of operators.
int Priority(char op)
{
if (op == '^')
return 3;
else if (op == '/'  op == '*')
return 2;
else if (op == '+'  op == '')
return 1;
// When char is '(', While loop should not be executed.
return INT8_MAX;
}
string InfixToPostfix(string expression)
{
string output;
stack<char> Stack;
for (int i = 0; i < expression.length(); i++)
{
char character = expression[i];
// if character is operand.
if (isalnum(character))
{
output.push_back(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character))
{
// Pop and append operators greater than scanned operator.
while (!Stack.empty() && Stack.top() != '(' && Priority(Stack.top()) >= Priority(character))
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.push(character);
}
// if character is ')'
// then pop until '('.
else if (character == ')')
{
while (Stack.top() != '(')
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.pop();
}
}
// Pop all remaining elements.
while (!Stack.empty())
{
output.push_back(Stack.top());
Stack.pop();
}
return output;
}
int main()
{
char infix[] = "a*(b+c)/d";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << InfixToPostfix(infix);
}
Output
Infix: a*(b+c)/d
Postfix: abc+*d/
Infix to Prefix Algorithm
Steps to convert Infix expression to Prefix expression is same as Infix to Postfix with some additional steps involved. In the following algorithm, steps 1, 2 and 10 are added.
 Reverse the infix expression.
 Convert all open parenthesis “(“ to close parenthesis “)” and vice versa. (On executing step 1, the parenthesis present in the expression will also get reversed which we don’t want, hence this step is required.)
 Scan the infix expression from left to right.
 If the scanned character is an operand, append it to the output variable.
 Else if it is an operator, then check the following condition.
5.1 If the stack is empty or the top of the stack contains open braces ‘(‘ or the precedence order of the scanned (incoming) operator is greater than the operator at the top of the stack, then push the (scanned) incoming operator to the stack.
5.2 Else pop all the operators from the stack which are greater than or equal to the scanned operator or until open parenthesis is encountered or the stack becomes empty, and push the scanned operator to the stack.  If the scanned character is an open parenthesis “(“, then push it onto the stack.
 If the scanned character is a close parenthesis “)”, then pop all the operators to the output until open parenthesis “(“ is encountered, and discard the open parenthesis and the scanned character (close parenthesis).
 Repeat steps from 4 to 7 until all the characters in infix are scanned.
 Pop all the remaining operators and empty the stack to the output variable.
 Reverse the output variable.
 Print the output variable.
Find below the working of the Infix to Prefix algorithm for expression a * (b + c) / d,
After performing steps 1 and 2, the expression becomes d / (c + b ) * a
Steps 
Stack 
Scanned Character 
Output 
Step used from Infix to Prefix algorithm 
Initially 
[Empty Stack] 



1 
[Empty Stack] 
d 
d 
4. 
2 
/ 
/ 
d 
5.1 
3 
/( 
( 
d 
6. 
4 
/( 
c 
dc 
4. 
5 
/(+ 
+ 
dc 
5.1 
6 
/(+ 
b 
dcb 
4. 
7 
/ 
) 
dcb+ 
7. 
8 
* 
* 
dcb+/ 
5.2 
9 
* 
a 
dcb+/a 
4. 
10 
[Empty Stack] 
End 
dcb+/a* 
9 
11 
Reverse the output variable 
*a/+bcd 
10. 
Therefore, the Prefix expression of a * (b + c) / d is *a/+bcd/
 C/C++
 Python
 Java
#include <iostream>
#include <string>
#include <bits/stdc++.h>
using namespace std;
// Check if a character is operator(including '(') or not.
int operatorOrNot(char ch)
{
if (ch == '^'  ch == '/'  ch == '*'  ch == '+'  ch == ''  ch == '(')
return 1;
return 0;
}
// Priority of operators.
int Priority(char op)
{
if (op == '^')
return 3;
else if (op == '/'  op == '*')
return 2;
else if (op == '+'  op == '')
return 1;
// When char is '(', While loop should not be executed.
return INT8_MAX;
}
string InfixToPrefix(string expression)
{
reverse(expression.begin(), expression.end());
string output;
stack<char> Stack;
for (int i = 0; i < expression.length(); i++)
{
char character = expression[i];
if (character == '(')
character = ')';
else if (character == ')')
character = '(';
// if character is operand.
if (isalnum(character))
{
output.push_back(character);
}
// if character is an operator or '('.
else if (operatorOrNot(character))
{
// Pop and append operators greater than scanned operator.
while (!Stack.empty() && Stack.top() != '(' && Priority(Stack.top()) >= Priority(character))
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.push(character);
}
// if character is ')'
// then pop until '('.
else if (character == ')')
{
while (Stack.top() != '(')
{
output.push_back(Stack.top());
Stack.pop();
}
Stack.pop();
}
}
// Pop all remaining elements.
while (!Stack.empty())
{
output.push_back(Stack.top());
Stack.pop();
}
reverse(output.begin(), output.end());
return output;
}
int main()
{
string infix = "a*(b+c)/d";
cout << "Infix: " << infix << endl;
cout << "Postfix: " << InfixToPrefix(infix);
}
Output
Infix: a*(b+c)/d
Prefix: *a/+bcd