#include <stdio.h>
#include <string.h>
#include <ctype.h>
#define N 80
typedef enum {FALSE, TRUE} bool;
#include "stack.h"
#include "queue.h"
#define NOPS 7
char operators [] = "()^/*+-";
int priorities[] = {4,4,3,2,2,1,1};
char associates[] = " RLLLL";
char t[N]; char *tptr = t; // this is where prefix will be saved.
int getIndex( char op ) {
/*
* returns index of op in operators.
*/
int i;
for( i=0; i<NOPS; ++i )
if( operators[i] == op )
return i;
return -1;
}
int getPriority( char op ) {
/*
* returns priority of op.
*/
return priorities[ getIndex(op) ];
}
char getAssociativity( char op ) {
/*
* returns associativity of op.
*/
return associates[ getIndex(op) ];
}
void processOp( char op, queue *q, stack *s ) {
/*
* performs processing of op.
*/
switch(op) {
case ')':
printf( "\t S pushing )...\n" );
sPush( s, op );
break;
case '(':
while( !qEmpty(q) ) {
*tptr++ = qPop(q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
while( !sEmpty(s) ) {
char popop = sPop(s);
printf( "\tS popping %c...\n", popop );
if( popop == ')' )
break;
*tptr++ = popop;
}
break;
default: {
int priop; // priority of op.
char topop; // operator on stack top.
int pritop; // priority of topop.
char asstop; // associativity of topop.
while( !sEmpty(s) ) {
priop = getPriority(op);
topop = sTop(s);
pritop = getPriority(topop);
asstop = getAssociativity(topop);
if( pritop < priop || (pritop == priop && asstop == 'L')
|| topop == ')' ) // IMP.
break;
while( !qEmpty(q) ) {
*tptr++ = qPop(q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
*tptr++ = sPop(s);
printf( "\tS popping %c...\n", *(tptr-1) );
}
printf( "\tS pushing %c...\n", op );
sPush( s, op );
break;
}
}
}
bool isop( char op ) {
/*
* is op an operator?
*/
return (getIndex(op) != -1);
}
char *in2pre( char *str ) { /*
* returns valid infix expr in str to prefix.
*/
char *sptr;
queue q = {NULL};
stack s = NULL;
char *res = (char *)malloc( N*sizeof(char) );
char *resptr = res;
tptr = t;
for( sptr=str+strlen(str)-1; sptr!=str-1; -sptr ) {
printf( "processing %c tptr-t=%d...\n", *sptr, tptr-t );
if( isalpha(*sptr) ) // if operand.
qPush( &q, *sptr );
else if( isop(*sptr) ) // if valid operator.
processOp( *sptr, &q, &s );
else if( isspace(*sptr) ) // if whitespace.
;
else {
fprintf( stderr, "ERROR:invalid char %c.\n", *sptr );
return "";
}
}
while( !qEmpty(&q) ) {
*tptr++ = qPop(&q);
printf( "\tQ popping %c...\n", *(tptr-1) );
}
while( !sEmpty(&s) ) {
*tptr++ = sPop(&s);
printf( "\tS popping %c...\n", *(tptr-1) );
}
*tptr = 0;
printf( "t=%s.\n", t );
for( -tptr; tptr!=t-1; -tptr ) {
*resptr++ = *tptr;
}
*resptr = 0;
return res;
}
int main() {
char s[N];
puts( "enter infix freespaces max 80." );
gets(s);
while(*s) {
puts( in2pre(s) );
gets(s);
}
return 0;
} |