Infix to Prefix Program in C

Previous
Next
#include<stdio.h>
#include<string.h>

#define LP 10
#define RP 20
#define OPERATOR 30
#define OPERAND 40

#define RPP 0
#define AP 1
#define SP 1
#define MP 2
#define DP 2
#define REMP 2
#define NONE 9

void InfixToPrefix();
int getType(char);
int getPrecedence(char);
void push(char);
char pop();

char infix[50],stack[40],prefix[50];
int top;

int main()
{
	char ch;
	do
	{
		top=-1;
		printf("Enter an Infix expression : ");
		gets(infix);
		strrev(infix);
		
		InfixToPrefix();
		strrev(prefix);
		
		printf("Prefix expression : %s\n",prefix);
		printf("Do you want to convert one more (y\\n) : ");
		ch=getche();
		
	}while(ch=='y');
	return 0;
}
void InfixToPrefix()
{
	int i,p,l,type,prec;
	char next;
	
	i=p=0;
	l=strlen(infix);
	
	while(i<l)
	{
		type=getType(infix[i]);
		switch(type)
		{
			case RP:	push(infix[i]);
					break;
			case LP:	while((next=pop())!=')')
					{
						prefix[p]=next;
						++p;
					}
					break;
			case OPERAND:	prefix[p]=infix[i];
						 ++p;
						 break;
			case OPERATOR:	prec=getPrecedence(infix[i]);
						 while((top>-1)&&(prec<getPrecedence(stack[top])))	
						 {
						 	prefix[p]=pop();
						 	++p;
						 }
						 push(infix[i]);
						 break;
		}
		++i;
	}
	while(top>-1)
	{
		prefix[p]=pop();
		++p;
	}
}
int getType(char sym)
{
	switch(sym)
	{
		case '(':	return LP;
		case ')':	return RP;
		case '+':
		case '-':
		case '*':
		case '/':
		case '%':	return OPERATOR;
		default:	return OPERAND;
	}
}
int getPrecedence(char sym)
{
	switch(sym)
	{
		case ')':	return RPP;
		case '+':	return AP;
		case '-':	return SP;
		case '*':	return MP;
		case '/':	return DP;
		case '%':	return REMP;
		default:	return NONE;
	}
}
void push(char sym)
{
	++top;
	stack[top]=sym;
}
char pop()
{
	char sym;
	sym=stack[top];
	--top;
	return sym;
}
Previous
Next

Add Comment

Courses Enquiry Form