Infix to Postfix conversion using Stack

infix to postfix conversion using Stack

Prev Next

---

Conversion of an Infix Expression into a Postfix Expression

We can use the following steps...

Step 1: Scan all the symbols one by one from left to right in the given Infix Expression and repeat steps 2-5

Step 2: If the scanned symbol is an operand, then place directly in the postfix expression

Step 3: If the scanned symbol is left parenthesis '(', push it onto the STACK.

Step 4: If the scanned symbol is an operator ( ✖ ), then:

Repeatedly pop from STACK and add to postfix expression each operator( On the top of STACK ) , which has the same precedence as or higher precedence than ( ✖ )

Add ( ✖ ) to Stack

Step 5: If the symbol scanned is a right parenthesis ')'

Repeatedly pop from STACK and add to postfix expression each operator( On the top of STACK ) , till we get the matching left parenthesis.

Remove the left parenthesis [ Do not add the left parenthesis to postfix expression]

Step 6: EXIT

Example

Consider the following Infix Expression...

( A + B ) * ( C - D )

The given infix expression can be converted into postfix expression using Stack data Structure as follows...

The final Postfix Expression is as follows...

A B + C D - *

C program to convert infix to postfix

# include<stdio.h>
char postfix[50];
char infix[50];
char opstack[50]; /* operator stack */
int i, j, top = 0;
int lesspriority(char op, char op_at_stack)
{
int k;
int pv1; /* priority value of op */
int pv2; /* priority value of op_at_stack */
char operators[] = {'+', '-', '*', '/', '%', '^', '(' };
int priority_value[] = {0,0,1,1,2,3,4};
if( op_at_stack == '(' )
return 0;
for(k = 0; k < 6; k ++)
{
if(op == operators[k])
pv1 = priority_value[k];
}
for(k = 0; k < 6; k ++)
{
if(op_at_stack== operators[k])
pv2 = priority_value[k];
}
if(pv1 < pv2)
return 1;
else
return 0;
}

void push(char op) /* op - operator */
{
/* before pushing the operator
'op' into the stack check priority
of op with top of opstack if less
then pop the operator from stack
then push into postfix string else
push op onto stack itself */
if(top == 0)
{
opstack[top] = op;
top++;
}
else
{
if(op != '(' )
{
while(lesspriority(op, opstack[top-1]) == 1 && top > 0)
{
postfix[j] = opstack[--top];
j++;
}
}
opstack[top] = op; /* pushing onto stack */
top++;
}
}
pop()
{
while(opstack[--top] != '(' ) /* pop until '(' comes */
{
postfix[j] = opstack[top];
j++;
}
}
int main()
{
char ch;

printf("\n Enter Infix Expression : ");
gets(infix);
while( (ch=infix[i++]) != '\0')
{
switch(ch)
{
  case ' ' : break;
  case '(' :
case '+' :
case '-' :
case '*' :
case '/' :
case '^' :
case '%' : push(ch); break;
case ')' : pop();  break;
default  : postfix[j] = ch;
j++;
}
}
while(top >= 0)
{
postfix[j] = opstack[--top];
j++;

}
postfix[j] = '\0';
printf("\n Infix Expression : %s ", infix);
printf("\n Postfix Expression : %s ", postfix);

}

blogger

Prev Next

Share this

yashcode