expression final.cpp

编译原理的算符优先表达式求值程序

#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<string.h>
//--------------------------------------------------------------------------
#define MaxCharNum						2048
#define MaxNodeNum						1024


#define ProcessSuccessful               0
#define NumberFormatError               1 
#define UnidentifiableCharIncluded      2
#define UnsupportedOperatorIncluded     3
#define UnmatchableExpression           4

#define ValMask                         0x1000 

#define OP_ParenthesisL                 0x0000 
#define OP_ParenthesisR                 0x0001 
#define OP_Not                          0x0002
#define OP_Mul                          0x0003
#define OP_Div                          0x0004
#define OP_Add                          0x0005
#define OP_Minus                        0x0006
#define OP_Equals                       0x0007
#define OP_HashKey                      0x0008

#define ValLong                         0x1010
#define ValFloat                        0x1020

//--------------------------------------------------------------------------
struct TerminalNode{
	int		category;
	float	val;
};

//--------------------------------------------------------------------------
char OperatorName[]={'(',')','!','*','/','+','-','=','#'};
int priority[9][9]={{-1,0,-1,-1,-1,-1,-1,-1,2},
					{2,1,1,1,1,1,1,1,1},
					{-1,1,-1,1,1,1,1,1,1},
					{-1,1,-1,1,1,1,1,1,1},
					{-1,1,-1,1,1,1,1,1,1},
					{-1,1,-1,-1,-1,1,1,1,1},
					{-1,1,-1,-1,-1,1,1,1,1},
					{-1,1,-1,-1,-1,-1,-1,1,1},
					{-1,2,-1,-1,-1,-1,-1,-1,0}};

//--------------------------------------------------------------------------
int isOperator(char);
int GetTerminalList(char *exp,TerminalNode *tlist,int &point);
int getResult(TerminalNode *tlist,int terminalNum,int &retval);

//--------------------------------------------------------------------------
int main(int argc, char* argv[]){
	int		retval,terminalNum;
	char	exp[MaxCharNum];			//inputed string
	TerminalNode	tlist[MaxNodeNum];	//array of terminal characters
	while(1){
		gets(exp);
		if(!strcmp(exp,"q")) break;		//inputed "q", then quit
		if(!strcmp(exp,"")) continue;	//inputed nothing, go on
		switch(GetTerminalList(exp,tlist,terminalNum)){
			case NumberFormatError:
				printf("Number format error.\n");
				continue;
			case UnidentifiableCharIncluded:
				printf("Unidentifiable character included.\n");
				continue;
			case UnsupportedOperatorIncluded:
				printf("Unsupported operator included.\n");
				continue;
			case ProcessSuccessful:
				printf("Process successful.\n");
		}

		switch(getResult(tlist,terminalNum,retval)){
			case ProcessSuccessful:
				if(tlist[0].category==ValLong)
					printf("The result of this expression is %ld\n",(long)tlist[0].val);
				else printf("The result of this expression is %g\n",tlist[0].val);
				break;
			case UnmatchableExpression:
				printf("Error: Unmatchable expression.\n");
				printf("       at: %d\n",retval);	//display the position of the error
				break;
		}
	}
	return 0;
}
//--------------------------------------------------------------------------
int isOperator(char ch){
	for(int i=0;i<8;i++)
		if(ch==OperatorName[i]) return i;
	return -1;
}

//--------------------------------------------------------------------------
int GetTerminalList(char *exp,TerminalNode *tlist,int &pos){
	int		point=0,spos=0,chartype;
	char	buffer[256];

	tlist[0].category = OP_HashKey;
	pos = 1;

	while(exp[spos] != 0){
		if( isspace(exp[spos]) ){	//tab, space, enter and so on
			spos++;
			continue;
		}
		else if( (chartype=isOperator(exp[spos])) != -1){	//operator
			if(chartype==OP_Equals)                             //++
				if( isOperator(exp[spos+1])==OP_Equals )	spos++;
			spos++;
			tlist[pos].category = chartype;
		}
		else if( isdigit(exp[spos]) ){	//digit
			point = 0;
			tlist[pos].category = ValLong;
			while(isdigit(exp[spos++])) buffer[ point++ ] = exp[spos-1];
			if(exp[spos-1] == '.'){
				tlist[pos].category = ValFloat;
				buffer[point++] = '.';
				while(isdigit(exp[spos++])) buffer[point++] = exp[spos-1];
			}
			if(exp[spos-1]=='e'||exp[spos-1]=='E'){
				tlist[pos].category = ValFloat;
				buffer[point++] = 'e';
				if(exp[spos]=='+' || exp[spos]=='-'){
					buffer[point++] = exp[spos];
					spos++;
				}
				if(!isdigit(exp[spos])) return NumberFormatError;
				while(isdigit(exp[spos++])) buffer[point++]=exp[spos-1];
			}
			buffer[point]=0;
			tlist[pos].val = (float)atof(buffer);
			spos--;
		}
		else return UnidentifiableCharIncluded;

		//---------------------Display the information of the character-----
		if( (tlist[pos].category&ValMask) == 0 )
			printf("Category: Operator  Value: %10c\n",OperatorName[tlist[pos].category]);
		else{
			if(tlist[pos].category==ValLong)
				printf("Category: Long      Value: %10ld\n",(long)tlist[pos].val);
			else printf("Category: Float     Value: %10g\n",tlist[pos].val);
		}
		pos++;
	}

	tlist[pos].category=OP_HashKey;
	pos++;
	return ProcessSuccessful;
}

//--------------------------------------------------------------------------
int getResult(TerminalNode *tlist,int terminalNum,int &pos){
	TerminalNode *stack = tlist;
	int point,i;

	stack[0]=tlist[0];
	point=pos=1;
	while(pos<terminalNum){
		if(tlist[pos].category&ValMask){	//digit
			if(stack[point-1].category&ValMask)
				return UnmatchableExpression;
			stack[point++]=tlist[pos++];
			continue;
		}
		for(i=point-1;i>=0;i--)
			if(!(stack[i].category&ValMask)) break;

		switch(priority[ stack[i].category ][ tlist[pos].category ]){
													// get priority
			case 0:		//equal
				if(i==point-1) return UnmatchableExpression;	//no constant on the right side of the terminal character
				stack[i]=stack[i+1];
				point--;
				pos++;
				break;
			case -1:	//less
				stack[point++]=tlist[pos++];	//push in stack
				break;
			case 1:		//greater
				if(i==point-1) return UnmatchableExpression;	//no constant on the right side of the terminal character
				switch(stack[i].category){
					case OP_Add:	//addition			
						if( !(stack[i-1].category&ValMask) ){
							stack[i]=stack[i+1];		//positive number
							point--;
							break;
						}
						stack[i-1].val+=stack[i+1].val;
						if(stack[i-1].category!=stack[i+1].category)
							stack[i-1].category=ValFloat;  //get category
						point-=2;
						break;
					case OP_Minus:	//minus
						if( !(stack[i-1].category&ValMask) ){
							stack[i]=stack[i+1];		//negative number
							stack[i].val=-stack[i].val;
							point--;
							break;
						}
						stack[i-1].val-=stack[i+1].val;
						if(stack[i-1].category!=stack[i+1].category)
							stack[i-1].category=ValFloat;  //get category
						point-=2;
						break;
					case OP_Mul:	//multiplication
						if( !(stack[i-1].category&ValMask) )	return UnmatchableExpression;
						stack[i-1].val*=stack[i+1].val;
						if(stack[i-1].category!=stack[i+1].category)
							stack[i-1].category=ValFloat;
						point-=2;
						break;
					case OP_Div:	//division
						if( !(stack[i-1].category&ValMask) )	return UnmatchableExpression;
						stack[i-1].val/=stack[i+1].val;
						if(stack[i-1].category!=stack[i+1].category)
							stack[i-1].category=ValFloat;
						point-=2;
						break;
					case OP_Equals:	//==
						if( !(stack[i-1].category&ValMask) )	return UnmatchableExpression;
						stack[i-1].val=(stack[i-1].val==stack[i+1].val);
						stack[i-1].category=ValLong;
						point-=2;
						break;
					case OP_Not:	// !
						stack[i]=stack[i+1];
						stack[i].val=!stack[i].val;
						point--;
						break;
				}
				break;
			case 2:		//no relationship
				return UnmatchableExpression;
		}

	}
	if(pos==0) return UnmatchableExpression;
	return ProcessSuccessful;
}
/////////////////////////////////////////////////////////////////