Saturday, November 8, 2008

convertion of infix exp to postfix

Write a C Program to convert and print a given valid parenthesized infix arithmetic expression to postfix expression .The expression consists of single character operands and the binary operators + (plus), -(minus), *(multiply) and /(divide).

Program:

#include"stdio.h"
#include"conio.h"

#define MAX 30 /*definition section*/
#define TRUE 1
#define FALSE 0

struct stack /*stack declaration*/
{
int top;
char items[MAX];
};
void postfix (char *,char *); /*function prototype declarations*/
char pop(struct stack *s);
void push (struct stack *s,char);
int empty(struct stack *);
char stacktop(struct stack *);
int prcd(char);

void main()
{
char infix[MAX],post[MAX];
clrscr();
printf("\n Enter the infix expression:");
scanf("%s",infix); /*reading the infix expression*/
postfix(infix,post);
printf("\n The equivalent postfix expression is %s",post);
getch();
}

void push(struct stack *s,char ele) /*push function definition*/
{
if(s->top==MAX-1)
{
printf("\n stack overflow");
exit(1);
}
else
s->items[++(s->top)]=ele;
}

char pop(struct stack *s) /*pop function definition*/
{
int x;
if(empty(s)) /*empty function call*/
{
printf("\n stack underflow");
getch();
exit(1);
}
else
{
x=s->items[s->top--];
return x;
}
}

int empty(struct stack *s) /*empty function definition*/
{
if(s->top==-1)
return(TRUE);
else
return(FALSE);
}

void postfix(char infix[],char post[]) /*postfix function definition*/
{
int infixpos=0,postpos=0;
struct stack stk;
char symb;
stk.top=-1;
push(&stk,'#');
while(infix[infixpos]!='\0')
{
symb=infix[infixpos];
switch(symb)
{
case'(':
push(&stk,symb);
break;
case')':
while(stacktop(&stk)!='(')
{
post[postpos++]=pop(&stk);
}
pop(&stk);
break;
case'$':
case'*':
case'/':
case'+':
case'-':
/* prcd function call */
while(prcd(stacktop(&stk))>=prcd(symb)) /*prcd function call*/
{
post[postpos++]=pop(&stk);
}
push(&stk,symb);
break;
default:post[postpos++]=symb;
}
infixpos++;
}
while(stacktop(&stk)!='#')
{
post[postpos++]=pop(&stk);
}
post[postpos]='\0';
}


int prcd(char symb) /*prcd function definition*/
{
int p;
switch(symb)
{
case'$':
p=3;
break;
case'/':
case'*':
p=2;
break;
case'+':
case'-':
p=1;
break;
case'(':
p=0;
break;
case'#':
p=-1;
break;
}
return p;
}

char stacktop(struct stack *ps) /*stacktop function definition*/
{
int x;
if(empty(ps))
{
printf("\n stack underflow");
getch();
exit(1);
}

else
{
x=ps->items[ps->top];
return x;
}
}

No comments:

Post a Comment