Infix to Postfix Conversion using Stack Data Structure (With C++ Program Code)

In this tutorial we will convert in Infix Expression to a Postfix Expression using Stack Data structure. We will understand the Rules to convert an infix expression to postfix and also understand the pseudocode. Lastly we will write a C++ program to perform infix to postfix expression conversion.

Rules for Infix to postfix using stack DS –

1. Scan Expression from Left to Right
2. Print OPERANDs as the arrive
3. If OPERATOR arrives & Stack is empty, push this operator onto the stack
4. IF incoming OPERATOR has HIGHER precedence than the TOP of the Stack, push it on stack
5. IF incoming OPERATOR has LOWER precedence than the TOP of the Stack, then POP and print the TOP. Then test the incoming operator against the NEW TOP of stack.
6. IF incoming OPERATOR has EQUAL precedence with TOP of Stack, use ASSOCIATIVITY Rules.
7. For ASSOCIATIVITY of LEFT to RIGHT –
   1. POP and print the TOP of stack, then push the incoming OPERATOR
8. For ASSOCIATIVITY of RIGHT to LEFT –
   1. PUSH incoming OPERATOR on stack.
9. At the end of Expression, POP & print all  OPERATORS from the stack
10. IF incoming SYMBOL is ‘(‘ PUSH it onto Stack.
11. IF incoming SYMBOL is ‘)’ POP the stack and print OPERATORs till ‘(‘ is found. POP that ‘(‘
12. IF TOP of stack is ‘(‘ PUSH OPERATOR on Stack

PSEUDOCODE –

C++ Program to Infix to Postfix Conversion using Stack DS –

#include<iostream>
#include<stack>
using namespace std;

bool isOperator(char c)
{
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
	{
		return true;
	}
	else
	{
		return false;
	}
}

int precedence(char c) 
{ 
    if(c == '^') 
    return 3; 
    else if(c == '*' || c == '/') 
    return 2; 
    else if(c == '+' || c == '-') 
    return 1; 
    else
    return -1; 
} 

string InfixToPostfix(stack<char> s, string infix)
{
	string postfix;
	for(int i=0;i<infix.length();i++)
	{
		if((infix[i] >= 'a' && infix[i] <= 'z')
		||(infix[i] >= 'A' && infix[i] <= 'Z'))
		{
			postfix+=infix[i];
		}
		else if(infix[i] == '(')
		{
			s.push(infix[i]);
		}
		else if(infix[i] == ')')
		{
			while((s.top()!='(') && (!s.empty()))
			{
				char temp=s.top();
				postfix+=temp;
				s.pop();
			}
			if(s.top()=='(')
			{
				s.pop();
			}
		}
		else if(isOperator(infix[i]))
		{
			if(s.empty())
			{
				s.push(infix[i]);
			}
			else
			{
				if(precedence(infix[i])>precedence(s.top()))
				{
					s.push(infix[i]);
				}	
				else if((precedence(infix[i])==precedence(s.top()))&&(infix[i]=='^'))
				{
					s.push(infix[i]);
				}
				else
				{
					while((!s.empty())&&( precedence(infix[i])<=precedence(s.top())))
					{
						postfix+=s.top();
						s.pop();
					}
					s.push(infix[i]);
				}
			}
		}
	}
	while(!s.empty())
	{
		postfix+=s.top();
		s.pop();
	}
	
	return postfix;
}

int main() 
{  

  	string infix_exp, postfix_exp;
  	cout<<"Enter a Infix Expression :"<<endl;
  	cin>>infix_exp;
  	stack <char> stack;
	cout<<"INFIX EXPRESSION: "<<infix_exp<<endl;
  	postfix_exp = InfixToPostfix(stack, infix_exp);
  	cout<<endl<<"POSTFIX EXPRESSION: "<<postfix_exp;
	  
	return 0;
}

YouTube video tutorial –