Sunday, August 29, 2010

C Program to convert an infix expression to prefix expression

#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 30
#define OPERAND 10
#define OPERATOR 20
#define LEFTPARA 30
#define RIGHTPARA 40

typedef struct prestk
{
    int top;
    char stack[MAX];
}stack;

void init(stack*);
void push(stack*,char);
char pop(stack*);
int getprec(char);
int gettype(char);
void main()
{
    stack stk;
    char inf[MAX],ch,pre[MAX];
    int l,i,k=0,pr;
    fflush(stdin);
    clrscr();

    init(&stk);
    printf(" Enter the infix expression : ");
    gets(inf);
    l=strlen(inf);
    for(i=l-1;i>=0;i--)
    {
        switch(gettype(inf[i]))
        {
             case OPERAND : pre[k++]=inf[i];
             break;
             case OPERATOR: pr=getprec(inf[i]);
             while(pr<getprec(stk.stack[stk.top])&&stk.top!=-1)
             pre[k++]=pop(&stk);
             push(&stk,inf[i]);
             break;
             case RIGHTPARA:push(&stk,inf[i]);
             break;
             case LEFTPARA    : while((ch=pop(&stk)!=')'))
                                 {pre[k++]=ch;}
                                 break;
         }
    }

    while(stk.top!=-1)
    pre[k++]=pop(&stk);
    pre[k]='\0';
    strrev(pre);
    puts(pre);
    getch();
}

void init(stack *st)
{
  st->top=-1;
}

void push(stack *st,char c)
{
  st->top++;
  st->stack[st->top]=c;
}

char pop(stack *st)
{
    char c;
    c=st->stack[st->top];
    st->top--;
    return c;
}

int getprec(char c)
{
    switch(c)
    {
        case ')' : return 0;
        case '+' :
        case '-' : return 1;
        case '*' :
        case '/' :
        case '%' : return 2;
        case '$' : return 3;
    }
}

int gettype(char c)
{
     switch(c)
     {
     case '+':
     case '-':
     case '*':
     case '/':
     case '$':
     case '%': return OPERATOR;
     case '(': return LEFTPARA;
     case ')': return RIGHTPARA;
     default : return OPERAND;
     }
}


No comments:

Post a Comment