Open-Source Internship opportunity by OpenGenus for programmers. Apply now.
Reading time: 30 minutes | Coding time: 15 minutes
To convert Infix expression to Postfix expression, we will use the stack data structure. By scanning the infix expression from left to right,if we get any operand, simply add it to the postfix form, and for the operator and parenthesis, add them in the stack maintaining the precedence of them.
Infix Expression : Infix Expression contains operator in-between every pair of operands,Expression of the form a op b.
Postfix expression: Postfix Expression contains operator followed for every pair of operands,Expression of the form a b op.
Why postfix representation of the expression?
- Infix expressions are readable and solvable by humans because of easily distinguishable order of operators,but compiler doesn't have integrated order of operators.
- Hence to solve the Infix Expression compiler will scan the expression multiple times to solve the sub-expressions in expressions orderly which is very in-efficient.
- To avoid this traversing, Infix expressions are converted to Postfix expression before evaluation.
Algorithm
- Step 1 : Scan the Infix Expression from left to right.
- Step 2 : If the scanned character is an operand, append it with final Infix to Postfix string.
- Step 3 : Else,
- Step 3.1 : If the precedence order of the scanned(incoming) operator is greater than the precedence order of the operator in the stack (or the stack is empty or the stack contains a β(β or β[β or β{β), push it on stack.
- Step 3.2 : Else, Pop all the operators from the stack which are greater than or equal to in precedence than that of the scanned operator. After doing that Push the scanned operator to the stack. (If you encounter parenthesis while popping then stop there and push the scanned operator in the stack.)
- Step 4 : If the scanned character is an β(β or β[β or β{β, push it to the stack.
- Step 5 : If the scanned character is an β)βor β]β or β}β, pop the stack and and output it until a β(β or β[β or β{β respectively is encountered, and discard both the parenthesis.
- Step 6 : Repeat steps 2-6 until infix expression is scanned.
- Step 7 : Print the output
- Step 8 : Pop and output from the stack until it is not empty.
Example
Infix Expression : 3+4*5/6
Step 1 : Initially Stack is Empty ans the very first literal of Infix Expression is '3' which is operand hence push it on output stack.
Stack :
Output : 3
Step 2 : Next literal of expression is + which is operand, hence needed to be pushed on stack but intially stack is empty hence literal will directly pushed on to stack.
Stack : +
Output : 3
Step 3 : Further 4 is an operand should be pushed on stack.
Stack : +
Output : 3 4
Step 4 : Next literal is * which is an operator, as stack is not empty, priority should be checked of instack operator(top of stack) and of incoming operator i.e * as priority of instack operator is less than incoming operator, * will be pushed on to stack.
Stack : + *
Output : 3 4
Step 5 : Next literal is 5 which is an operand, hence should be pushed on to output stack.
Stack : + *
Output : 3 4 5
Step 6 : Next literal is / which is an operator, as stack is not empty, priority should be checked of instack operator(top of stack) i.e * and of incoming operator i.e /, as priority of / and * are equal hence * will be poped out of stack and will be stored on output stack and operator / will be stored on stack.
Stack : + /
Output : 3 4 5 *
Step 7 : Next literal is 6 which is an operand, hence should be pushed on output stack.
Stack : + /
Output : 3 4 5 * 6
Step 8 : As now all litrals are traversed, despite stack is not empty, hence pop all litrals from stack and pushed it on to output stack.
Postfix Expression : 3 4 5 * 6 / +
Implementation
#include <iostream>
#include <stack>
class InfixToPostfix
{
public:
InfixToPostfix(const std::string &expression) : expression_(expression) { }
int getPrecedenceOfOperators(char);
std::string convertInfixToPostfix();
private:
std::string expression_;
};
int InfixToPostfix::getPrecedenceOfOperators(char ch)
{
if(ch == '+' || ch == '-')
return 1;
if(ch == '*' || ch == '/')
return 2;
if(ch == '^')
return 3;
else
return 0;
}
std::string InfixToPostfix::convertInfixToPostfix()
{
std::stack <char> stack1;
std::string infixToPostfixExp = "";
int i = 0;
while(expression_[i] != '\0')
{
//if scanned character is open bracket push it on stack
if(expression_[i] == '(' || expression_[i] == '[' || expression_[i] == '{')
stack1.push(expression_[i]);
//if scanned character is opened bracket pop all literals from stack till matching open bracket gets poped
else if(expression_[i] == ')' || expression_[i] == ']' || expression_[i] == '}')
{
if(expression_[i] == ')')
{
while(stack1.top() != '(')
{
infixToPostfixExp = infixToPostfixExp + stack1.top();
stack1.pop();
}
}
if(expression_[i] == ']')
{
while(stack1.top() != '[')
{
infixToPostfixExp = infixToPostfixExp + stack1.top();
stack1.pop();
}
}
if(expression_[i] == '}')
{
while(stack1.top() != '{')
{
infixToPostfixExp = infixToPostfixExp + stack1.top();
stack1.pop();
}
}
stack1.pop();
}
//if scanned character is operator
else if(expression_[i] == '+' || expression_[i] == '-' || expression_[i] == '*' || expression_[i] == '/' || expression_[i] == '^')
{
//very first operator of expression is to be pushed on stack
if(stack1.empty()) {
stack1.push(expression_[i]);
} else{
/*
* check the precedence order of instack(means the one on top of stack) and incoming operator,
* if instack operator has higher priority than incoming operator pop it out of stack&put it in
* final postifix expression, on other side if precedence order of instack operator is less than i
* coming operator, push incoming operator on stack.
*/
if(getPrecedenceOfOperators(stack1.top()) >= getPrecedenceOfOperators(expression_[i]))
{
infixToPostfixExp = infixToPostfixExp + stack1.top();
stack1.pop();
stack1.push(expression_[i]);
}
else
{
stack1.push(expression_[i]);
}
}
}
else
{
//if literal is operand, put it on to final postfix expression
infixToPostfixExp = infixToPostfixExp + expression_[i];
}
i++;
}
//poping out all remainig operator literals & adding to final postfix expression
if(!stack1.empty())
{
while(!stack1.empty())
{
infixToPostfixExp = infixToPostfixExp + stack1.top();
stack1.pop();
}
}
return infixToPostfixExp;
}
int main()
{
InfixToPostfix p("a+b*c/d-q");
std::cout << "\nPostfix expression : " << p.convertInfixToPostfix();
}
Complexity
The time and space complexity of Conversion of Infix expression to Postfix expression algorithm is :
- Worst case time complexity:
Ξ(n^2) - Average case time complexity:
Ξ(n^2) - Best case time complexity:
Ξ(n^2) - Space complexity:
Ξ(n)
where N is the number of literals in Infix Expression
-
Complexity of algorithm in both worst and best case is O(n^2), as expression is iterated two times simultaneously, firstly for scanning the infix expression and secondly while poping out of stack.
Eg : a + b - d
* As in above Infix expression, O(n) will be the complexity for scanning each literal, while at the same time we pop the literals from stack, hence the complexity of algorithm is O(n*n) i.e : O(n^2). -
For storing Infix expression of n literals the space complexity is O(n) and for stack to hold atmost n literals the space complexity is O(n), hence
* Total space complexity is O(n+n) = O(2n) i.e : O(n)
