Showing posts with label Program - Infix to Postfix conversion. Show all posts
Showing posts with label Program - Infix to Postfix conversion. Show all posts

Saturday 31 March 2012

Program - Infix to Postfix conversion


Infix to Postfix conversion
A+B  -> Infix
AB+  -> Postfix
+AB  -> Prefix

Algorithm


Step-1  Initialize the stack

Step-2 Scan the leftmost symbol in the given infix expression and denote is as the current input symbol.

Step-3 Repeat through step-6 while infix expression

Step-4 Remove and output all stack symbols whose precedence values are greater than or equal to the precedence of the current input symbol.

Step-5 Push the current input symbol onto the stack.

Step-6 Scan the leftmost symbol in the infix expression and let it be the current symbol.


Program To convert infix to postfix

//postfix program

#include<stdio.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<stdlib.h>

#define Maxlen 64

static char infix [Maxlen+1], stack[Maxlen], postfix[Maxlen+1];


static int top;
//symbol type

#define Operator (-10)
#define Operand (-20)
#define LeftParen (-30)
#define RightParen (-40)

static char *symbols = "()+-*/";

//symbol precedence

#define LeftParenPrec 0   // (
#define AddPrec 1   // +
#define SubPrec 1  //  -
#define MultPrec 2  //  *
#define DivPrec 2  // /
#define RemPrec 2  // %
#define None 999  // all else


void infix_to_postfix(void);

void push(char symbol);
char pop(void);

int get_type(char);
int grt_prec(char);
int white_space(char);


void main()
{
          char ans;
          clrscr();

          do
          {
                   top=-1;       //reset stack
                   printf("\nInfix (up to %d chars ) : ",Maxlen);
                   gets(infix);


                   infix_to_postfix();

                   printf("\n Infix : %s",infix);
                   printf("\n Postfix : %s",postfix);

                  


                   printf("\n do you want to continue  (y/n) : ");
                   ans=getchar();

          }while(ans== 'y' || ans=='Y');

}

// function infix to postfix conversion

void infix_to_postfix(void)
{
          int i,p,len,type,precedence;
          char next;

          // i for infix  and  p for postfix

          i=p=0;
          len=strlen(infix);
         
//loop through input string

          while(i<len)
          {
                   if(!white_space(infix[i]))
                   {
                             type=get_type(infix[i]);
                             switch(type)
                             {

                                      //push left parenthesis onto stack

                                      case LeftParen:
                                      push(infix[i]);
                                      break;

                                      //pop stack until matching left parenthesis

                                      case RightParen:
                                                while((next=pop())!='(')
                                                {
                                                          postfix[p++] = next;
                                                }
                                                break;

                                      case Operand:
                                                postfix[p++] = infix[i];
                                                break;

                                      /* pop stack until first operator of higher
                                                precedence and then stack this operator */

                                      case Operator:
                                                precedence = get_prec(infix[i]);

                                      // anything on stack to pop

                                      while(top > -1 && precedence <= get_prec(stack[top]))
                                                postfix[p++] = pop();
                                       push(infix[i]);
                                      break;

                             }
                   }

                   i++;       // next symbol in infix expression
          }

          //pop any remaining operators

          while(top > -1)
          {
                   postfix[p++] = pop();
          }
          postfix[p] = '\0';        //ensure astring
          getch();

}

// function to find operator type

int get_type(char symbol)
{
          switch(symbol)
          {
                   case '(':
                             return (LeftParen);
                   case ')':
                             return (RightParen);
                   case '+':
                   case '-':
                   case '%':
                   case '*':
                   case '/':
                             return (Operator);
                   default :
                             return (Operand);

          }

}

// find precedence of the operator

int get_prec(char symbol)
{
          switch(symbol)
          {
                   case '+':
                             return (AddPrec);
                   case '-':
                             return (SubPrec);
                   case '*':
                             return (MultPrec);
                   case '/':
                             return (DivPrec);
                   case '%':
                             return (RemPrec);
                   case '(':
                             return (LeftParenPrec);
                   default:
                             return (None);
          }

}


//function push

void push(char symbol)
{
                   // check for overflow
          if(top > Maxlen)
                   //full_stack();
                   printf("\n Stack is full");
          else
                   stack[++top] = symbol;
}

// function pop

char pop(void)
{
          //  check for underflow

          if(top <= -1)
          {
                   printf("\n Stack is empty");
                   return ' ';
          }
          else
                   return(stack[top--]);
}

//   function white space checking

int white_space(char symbol)
{

          return(symbol == ' ' || symbol == '\t' || symbol == '\0');

}


Posted By : Ruchita Pandya