Given an Infix arithmetic expression , convert it into an equivalent postfix expression .
Expression will be given in the form of string , where alphabetic characters i.e az or AZ denotes operands and operators are ( + , – , * , / ) . Expression can also have brackets i.e β(β and β)β.
Sample example :
Input infix expression : a * ( b + c + d)
Output postfix expression : abc+d+*
Input Infix expression : a*b
Output postfix expression : ab*
What is 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 :
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
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
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
Precedence  Type  Operators  Associativity 
1  Postfix  () [] > . ++ —  Left to Right 
2  Unary  + – ! ~ ++ — (type)* & sizeof  Right to Left 
3  Multiplicative  * / %  Left to Right 
4  Additive  + –  Left to Right 
5  Shift  <<, >>  Left to Right 
6  Relational  < <= > >=  Left to Right 
7  Equality  == !=  Left to Right 
8  Bitwise AND  &  Left to Right 
9  Bitwise XOR  ^  Left to Right 
10  Bitwise OR    Left to Right 
11  Logical AND  &&  Left to Right 
12  Logical OR    Left to Right 
13  Conditional  ?:  Right to Left 
14  Assignment  = += + *= /= %= >>= <<= &= ^= =  Right to Left 
15  Comma  ,  Left to Right 
In this article we are going to see how we can convert Infix expressions to postfix expressions . For the simplicity and understanding purpose , we will consider only β+β , ββ ,β/β , β*β , β(β and β)β .
How to Covert Infix to Postfix
Conversion of Infix to postfix can be done using stack . The stack is used to reverse the order of operators. Stack stores the operator , because it can not be added to the postfix expression until both of its operands are added . Precedence of operator also matters while converting infix to postfix , which we will discuss in the algorithm .
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 .
Algorithm for Conversion of Infix to postfix

Scan all the symbols one by one from left to right in the given 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.

If the input is over, pop all the remaining symbols from the stack and append them to the postfix .
Infix to Postfix Conversion Example
Code Implementation For Infix to Postfix Conversion
#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; } int main() { // your code goes here string infix="a*(b+c+d)"; string postfix=infixToPostfix(infix); cout<<"Infix expression : "<<infix<<endl; cout<<"Postfix expression : "<<postfix<<endl; return 0; }
This article tried to discuss Infix to postfix conversion using stack. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE  Competitive Programming at PrepBytes.