Infix to Postfix Conversion


Take an expression:

2+5-7*3

This is the infix form of the expression. In the postfix form, you have to put the operators after the operands. Like this,

25+73*-

This is the postfix transformation of the expression.

Now, let us use stacks to implement this transformation. The algorithm is as follows:

  1. First, we will scan the expression which is in infix form from left to right.
  2. Create a stack.
  3. Then, if the scanned character is an operand then add it to the postfix string.
  4. If scanned character is operator and stack is empty then push the operator on the stack.
  5. If scanned character is an operand and stack is not empty then compare precedence of operator with element on the top of stack. If the element on top of the stack has higher precedence than the current element, then pop the element on top of stack and display it in the postfix string. Repeat this step till stack is empty or the element on top of stack has lesser precedence than current element.
  6. After all characters are scanned and stack is not empty, then pop the elements from the stack one by one and add them to the postfix string.
  7. Return the postfix string.
  8. This is the algorithm.

Now, let us see how it will be implemented in a c++ program.

#include "iostream"
#include "string"

using namespace std;

class Stack
{

private:

int top;
 //string infix[100];
 //string postfix[100];
 string stack[50];

public:

Stack()
 {
 top=-1;
 }

void push(char op)
 {
 if(top<100)
 {
 stack[++top]=op;
 }

else
 {
 cout<<"Stack Full"<<endl;
 }
 }

String pop()
 {
 if(top==-1)
 {
 return "E";
 }

else
 {
 return[top--];
 }
 }

 int isEmpty()
 {
 if(top==-1;)
 {
 return 1;
 }
 else
 {
 return 0;
 }
 }

 String topStack()
 {
 if(top!=-1)
 {
 return stack[top];
 }
 else
 {
 return "E";
 }
 }

}

String readChar(String infix)
{
 static int index=0;
 return infix[index++];
}

int compare(int x, int y)
{
 if(x<=y)
 {
 return 1;
 }
 else
 {
 return 0;
 }
}

int priority(char s)
{
 switch(s)
 {
 case '+':
 case '-':
 return 1;
 case '*':
 case '/':
 return 2;
 }
}

int main()
{
 Stack stack;
 String infix;
 String postfix;
 string c;
 cout<<"Enter a string"<<endl;  cin>>infix;
 int len=infix.size();
 for(int i=0;i<len;i++)
 {
 c=readChar(infix);
 if(c!="+"||c!="-"||c!="*"||c!="/")
 {
 postfix.append(c);
 }
 else if(c="+"||c="-"||c="*"||c="/")
 {
 if(stack.isEmpty())
 {
 stack.push(c);
 }
 else
 {
 while(compare(priority(c),priority(stack.topStack())) && (!stack.isEmpty()))
 {
 postfix.append(stack.pop());
 }
 stack.push(c);
 }
 }
 }
}

This is the code to convert the infix expression to postfix. Please test it out and tell me if it doesn’t work for any test case.

Advertisements

One comment

  1. […] Evaluation of Prefix and Postfix expressions Postfix expressions are those in which the operand is written after the operators. Eg:-  a+b=>ab+ Prefix expression are the opposite Eg:- a+b=>+ab […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s