infix to prefix code example

Example 1: infix to prefix in c

# include <stdio.h># include <string.h># define MAX 20void infixtoprefix(char infix[20],char prefix[20]);void reverse(char array[30]);char pop();void push(char symbol);int isOperator(char symbol);int prcd(symbol);int top=-1;char stack[MAX];main() {	char infix[20],prefix[20],temp;	printf("Enter infix operation: ");	gets(infix);	infixtoprefix(infix,prefix);	reverse(prefix);	puts((prefix));}//--------------------------------------------------------void infixtoprefix(char infix[20],char prefix[20]) {	int i,j=0;	char symbol;	stack[++top]='#';	reverse(infix);	for (i=0;i<strlen(infix);i++) {		symbol=infix[i];		if (isOperator(symbol)==0) {			prefix[j]=symbol;			j++;		} else {			if (symbol==')') {				push(symbol);			} else if(symbol == '(') {				while (stack[top]!=')') {					prefix[j]=pop();					j++;				}				pop();			} else {				if (prcd(stack[top])<=prcd(symbol)) {					push(symbol);				} else {					while(prcd(stack[top])>=prcd(symbol)) {						prefix[j]=pop();						j++;					}					push(symbol);				}				//end for else			}		}		//end for else	}	//end for for	while (stack[top]!='#') {		prefix[j]=pop();		j++;	}	prefix[j]='\0';}////--------------------------------------------------------void reverse(char array[30]) // for reverse of the given expression {	int i,j;	char temp[100];	for (i=strlen(array)-1,j=0;i+1!=0;--i,++j) {		temp[j]=array[i];	}	temp[j]='\0';	strcpy(array,temp);	return array;}//--------------------------------char pop() {	char a;	a=stack[top];	top--;	return a;}//----------------------------------void push(char symbol) {	top++;	stack[top]=symbol;}//------------------------------------------int prcd(symbol) // returns the value that helps in the precedence {	switch(symbol) {		case '+':		        case '-':		        return 2;		break;		case '*':		        case '/':		        return 4;		break;		case '$':		        case '^':		        return 6;		break;		case '#':		        case '(':		        case ')':		        return 1;		break;	}}//-------------------------------------------------int isOperator(char symbol) {	switch(symbol) {		case '+':		        case '-':		        case '*':		        case '/':		        case '^':		        case '$':		        case '&':		        case '(':		        case ')':		        return 1;		break;		default:		        return 0;		// returns 0 if the symbol is other than given above	}}

Example 2: infix to prefix using cpp linked list program

#include <stdio.h>#include <conio.h>#include <string.h>#include <ctype.h>#define MAX 50struct infix{	char target[MAX] ;	char stack[MAX] ;	char *s, *t ;	int top, l ;} ; void initinfix ( struct infix * ) ;void setexpr ( struct infix *, char * ) ;void push ( struct infix *, char ) ;char pop ( struct infix * ) ;void convert ( struct infix * ) ;int priority ( char c ) ;void show ( struct infix ) ; void main( ){	struct infix q ;	char expr[MAX] ;	clrscr( ) ;	initinfix ( &q ) ;	printf ( "\nEnter an expression in infix form: " ) ;	gets ( expr ) ;	setexpr ( &q, expr ) ;	convert ( &q ) ;	printf ( "The Prefix expression is: " ) ;	show ( q ) ;	getch( ) ;}/* initializes elements of structure variable */void initinfix ( struct infix *pq ){	pq -> top = -1 ;	strcpy ( pq -> target, "" ) ;	strcpy ( pq -> stack, "" ) ;	pq -> l = 0 ;}/* reverses the given expression */void setexpr ( struct infix *pq, char *str ){	pq -> s = str ;	strrev ( pq -> s ) ;	pq -> l = strlen ( pq -> s ) ;	*( pq -> target + pq -> l ) = '\0' ;	pq -> t = pq -> target + ( pq -> l - 1 ) ;}/* adds operator to the stack */void push ( struct infix *pq, char c ){	if ( pq -> top == MAX - 1 )		printf ( "\nStack is full.\n" ) ;	else	{		pq -> top++ ;		pq -> stack[pq -> top] = c ;	}}/* pops an operator from the stack */char pop ( struct infix *pq ){	if ( pq -> top == -1 )	{		printf ( "Stack is empty\n" ) ;		return -1 ;	}	else	{		char item = pq -> stack[pq -> top] ;		pq -> top-- ;		return item ;	}}/* converts the infix expr. to prefix form */void convert ( struct infix *pq ){	char opr ;	while ( *( pq -> s ) )	{		if ( *( pq -> s ) == ' ' || *( pq -> s ) == '\t' )		{			pq -> s++ ;			continue ;		}		if ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )		{			while ( isdigit ( *( pq -> s ) ) || isalpha ( *( pq -> s ) ) )			{				*( pq -> t ) = *( pq -> s ) ;				pq -> s++ ;				pq -> t-- ;			}		}		if ( *( pq -> s ) == ')' )		{			push ( pq, *( pq -> s ) ) ;			pq -> s++ ;		}		if ( *( pq -> s ) == '*' || *( pq -> s ) == '+' || *( pq -> s ) == '/' || *( pq -> s ) == '%' || *( pq -> s ) == '-' || *( pq -> s ) == '$' )		{			if ( pq -> top != -1 )			{				opr = pop ( pq ) ;				while ( priority ( opr ) > priority ( *( pq -> s ) ) )				{					*( pq -> t ) = opr ;					pq -> t-- ;					opr = pop ( pq ) ;				}				push ( pq, opr ) ;				push ( pq, *( pq -> s ) ) ;			}			else				push ( pq, *( pq -> s ) ) ;				pq -> s++ ;		}		if ( *( pq -> s ) == '(' )		{			opr = pop ( pq ) ;			while ( opr != ')' )			{				*( pq -> t ) = opr ;				pq -> t-- ;				opr = pop ( pq ) ;			}			pq -> s++ ;		}	}	while ( pq -> top != -1 )	{		opr = pop ( pq ) ;		*( pq -> t ) = opr ;		pq -> t-- ;	}	pq -> t++ ;}/* returns the priotity of the operator */int priority ( char c ){	if ( c == '$' )		return 3 ;	if ( c == '*' || c == '/' || c == '%' )		return 2 ;	else	{		if ( c == '+' || c == '-' )			return 1 ;		else			return 0 ;	}}/* displays the prefix form of given expr. */void show ( struct infix pq ){	while ( *( pq.t ) )	{		printf ( " %c", *( pq.t ) ) ;		pq.t++ ;	}}

Tags:

Misc Example