#include <stdio.h> #include <conio.h> #include <string.h> #include <ctype.h> #define MAX 50 struct 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 ; elsereturn 0 ; } } /* displays the prefix form of given expr. */ void show ( struct infix pq ) { while ( *( pq.t ) ) { printf ( " %c", *( pq.t ) ) ; pq.t++ ; } }