process.cpp

功能较全的表达式求值程序 C代码。mian是主函数

int hashtable[MAX_SIGNAL];
int infix[MAX_SIGNAL];
int postfix[MAX_SIGNAL];
int inlength;
int postlength;
int parentcount;
int signalcount;

char *getpassword()
{
	char c;
	int  cnt = 0;
    while( (c = getch())!= '\r')
	{
		if(c=='\b')
		{
			printf("\b \b");
			cnt--;
		}
		else 
		{
			pass[cnt++] = c;
			putchar(ECHOCHAR);
		}
		if (cnt == MAX_PASSWORD)
		{
			break;
		}
	}
	putchar('\n');
    return pass;
}

Value_type fac(Value_type x)
{
	Value_type value=1;
	if(x<0)
		return INT_MAX;
	else if(x<1)
		return 1;
	else
	{
		for(Value_type f=x;f>0;f--)
			value=value*f;
	}
	return value;
}

int Hash(char *name)
{
	int h=name[0]%MAX_SIZE;
	while(1)
	{
		if(hashtable[h]==-1)
			break;
		else if(strcmp(string[hashtable[h]].name ,name)==0)
			break;
		else
		{
			if(name[1]=='\0')
				h+=31;
			else
				h+=name[1];
			h%=MAX_SIZE;
		}
	}
	return abs(h);
}

void MakeHashTable( )
{
	int i;
	for(i=0;i<MAX_SIZE;i++)
		hashtable[i]=-1;
	for(i=1;i<=MAX_OPERATION;i++)
		hashtable[Hash(string[i].name )]=i;
}

Kind_type Kind(int h)
{
	return (string[h].kind );
}

int Priority(int h)
{
	return (string[h].info .pri );
}

int Leading( )
{
	int k;
	if(inlength<=-1)
		return 1;
	else
		return (k=Kind(infix[inlength]))==LEFT||k==SINGLE||k==BINARY;
}

void PutToken(int h)
{
	inlength++;
	infix[inlength]=h;
}

void PutToken1(int h)
{
	postlength++;
	postfix[postlength]=h;
}

int ExtractWord(char str[],int pos,char *word)
{
	int i;
	char *pw=word;
	for(i=pos;isalpha(str[i])||isdigit(str[i]);i++)
		*pw++=tolower(str[i]);
	*pw='\0';
	return i;
}

int FindWord(char str[],int pos)
{
	int h;
	char word[MAX_SIGNAL];
	pos=ExtractWord(str,pos,word);
	h=hashtable[Hash(word)];
	if(h!=-1)
	{
		if(Leading()==1)
		{
			if(Kind(h)==BINARY)
			{
				for(int i=0;i<28;i++)
					printf(" ");
				printf("二元运算符位置不正确!\n");				
				return -1;
			}
			else
				PutToken(h);
		}
		else
		{
			if(Kind(h)!=BINARY)
			{
				for(int i=0;i<28;i++)
					printf(" ");
				printf("应为二元运算符!\n");				
				return -1;
			}
			else
				PutToken(h);
		}
		return pos;
	}
	else
	{
		for(int i=0;i<28;i++)
			printf(" ");
		printf("标识符不正确!\n");		
		return -1;
	}
}

int FindNumber(char str[],int pos)
{
	if(Leading()==0)
	{
		for(int i=0;i<28;i++)
			printf(" ");
		printf("常数的位置不正确!\n");	
		return -1;
	}
	else
	{
		string[++signalcount].kind =OPERAND;
		string[signalcount].info .val =atof(&str[pos]);
		strcpy(string[signalcount].name ,"number");
		PutToken(signalcount);
		for(;isdigit(str[pos])||str[pos]=='.';pos++);
		return pos;
	}
}

int FindSymbol(char str[],int pos)
{
	int h,k;
	char word[MAX_SIGNAL];
	word[0]=str[pos];
	word[1]='\0';
	pos++;
	if((h=hashtable[Hash(word)])==-1)
	{
		for(int i=0;i<28;i++)
			printf(" ");
		printf("表达式中存在无法识别的字符!\n");		
		return -1;
	}
	else if(Leading()!=0)
	{
		if(Kind(h)==RIGHT)
		{
			for(int i=0;i<28;i++)
				printf(" ");
			printf("不应当为右括号!\n");			
			return -1;
		}
		else if(Kind(h)!=BINARY)
			PutToken(h);
		else
		{
			if(strcmp(word,"+")==0);
			else if(strcmp(word,"-")==0)
				PutToken(hashtable[Hash("~")]);
			else
			{
				for(int i=0;i<28;i++)
					printf(" ");
				printf("二元运算符不正确!\n");			
				return -1;
			}
		}
	}
	else
	{
		if(Kind(h)==BINARY||Kind(h)==RIGHT)
			PutToken(h);
		else
		{
			for(int i=0;i<28;i++)
				printf(" ");
			printf("二元运算符不正确!\n");		
			return -1;
		}
	}
	
	if((k=Kind(h))==LEFT)
		parentcount++;
	else if(k==RIGHT)
		if(--parentcount<0)
		{
			for(int i=0;i<28;i++)
				printf(" ");
			printf("右括号太多!\n");		
			return -1;
		}
		return pos;
}

void GetToken(int &h)
{
	inlength++;
	h=infix[inlength];
}

void GetToken1(int &h)
{
	postlength++;
	h=postfix[postlength];
}

void Translate( )
{
	int St[MAX_STACK];
	int top=-1;
	int h,h1;
	Kind_type type;
	postlength=-1;
	inlength=-1;
	int endright;
	do{
		GetToken(h);
		switch(type=Kind(h))
		{
		case OPERAND:
			PutToken1(h);
			break;
		case LEFT:
			top++;
			St[top]=h;
			break;
		case RIGHT:
			h=St[top];
			top--;
			while(top>-1&&Kind(h)!=LEFT)
			{
				PutToken1(h);
				h=St[top];
				top--;
			}
			break;
		case SINGLE:
		case BINARY:
			endright=0;
			do{
				if(top==-1)
					endright=1;
				else if(Kind(St[top])==LEFT)
					endright=1;
				else if(Priority(St[top])<Priority(h))
					endright=1;
				else if(Priority(St[top])==Priority(h)&&Priority(h)==MAX_PRIORITY)
					endright=1;
				else
				{
					h1=h;
					endright=0;
					h=St[top];
					top--;
					PutToken1(h);
					h=h1;
				}
			}while(endright==0);
			top++;
			St[top]=h;
			break;
		case END:
			while(top>-1)
			{
				h=St[top];
				top--;
				PutToken1(h);
			}
			break;
		}
	}while(type!=END);
	PutToken1(0);
}

int ProcessExpress(char *instring)
{
	int len,pos;
	inlength=-1;
	parentcount=0;
	signalcount=MAX_OPERATION;
	len=strlen(instring);
	instring[len]='\0';
	for(pos=0;pos<len;)
	{
		if(instring[pos]==' ')
			pos++;
		else if(isalpha(instring[pos]))
			pos=FindWord(instring,pos);
		else if(isdigit(instring[pos])||instring[pos]=='.')
			pos=FindNumber(instring,pos);
		else
			pos=FindSymbol(instring,pos);
		if(pos==-1)
			return 0;
	}
	if(parentcount!=0)
	{
		for(int i=0;i<28;i++)
			printf(" ");
		printf("括号不匹配!\n");		
	}
	PutToken(0);
	return 1;
}

void DispInfix( )
{
	int i;
	for(i=0;i<20;i++)
		printf(" ");	
	for(i=0;i<=inlength;i++)
	{
		if(strcmp(string[infix[i]].name ,"number")==0)
			printf(" %g",string[infix[i]].info .val );
		else
			printf(" %s",string[infix[i]].name );
	}//变换前
	printf("\n");
	for(i=0;i<20;i++)
		printf(" ");		
	for(i=0;i<=inlength;i++)
		printf(" %d",infix[i]);
	printf("\n");//变换后
}

void DispPostfix()
{
	int i;
	for(i=0;i<20;i++)
		printf(" ");	
	for(i=0;i<=postlength;i++)
	{
		if(strcmp(string[postfix[i]].name ,"number")==0)
			printf(" %g",string[postfix[i]].info .val );
		else
			printf(" %s",string[postfix[i]].name );
	}//变换前
	printf("\n");

	for(i=0;i<20;i++)
		printf(" ");	
	for(i=0;i<=postlength;i++)
		printf(" %d",postfix[i]);
	printf("\n");//变换后
}

Value_type DoBinary(int h,Value_type x,Value_type y)
{
	switch(h)
	{
	case 21:
		return (x+y);
		break;		
	case 22:
		return (x-y);
		break;		
	case 23:
		return (x*y);
		break;	
	case 24:
		if(y!=(Value_type)0)
			return (x/y);
		else
			return INT_MAX;			
		break;		
	case 25:
		if(y!=(Value_type)0)
			return (fmod(x,y));
		else
			return INT_MAX;		
		break;
	case 26:
		return (pow(x,y));
		break;
	default:		
		return INT_MAX;
		break;
	
	}
}

Value_type DoUnary(int h,Value_type x)
{
	switch(h)
	{
	case 3:
		return (-x);
		break;
	case 4:
		return (fabs(x));
		break;	
	case 5:
		if(x>=0)
			return (sqrt(x));
		else
			return INT_MAX;
		break;
	case 6:
		return (exp(x));
		break;
	case 7:
		if(x>0)
			return (log(x));
		else
			return INT_MAX;
		break;
	case 8:
		if(x>0)
			return (log10(x));
		else
			return INT_MAX;
		break;	
	case 9:
		return (sin(x));
		break;		
	case 10:
		return (cos(x));
		break;	
	case 11:
		if(cos(x)==0)
			return INT_MAX;
		else
			return (sin(x)/cos(x));
		break;	
	case 12:
		if(sin(x)==0)
			return INT_MAX;
		else 
			return (cos(x)/sin(x));
		break;
	case 13:
		if(x>1||x<-1)
			return INT_MAX;		
		else 
			return (asin(x));
		break;
	case 14:
		if(x>1||x<-1)			
			return INT_MAX;		
		else 
			return (acos(x));
		break;
	case 15:
		return (atan(x));
		break;
	case 16:
		return (sinh(x));
		break;
	case 17:
		return (cosh(x));
		break;
	case 18:
		return (tanh(x));
		break;
	case 19:
		if(sinh(x)==0)
			return INT_MAX;
		else 
			return (cosh(x)/sinh(x));
		break;
	case 20:		
		return (fac(x));
		break;		
	}
}
Value_type GetValue(int h)
{
	if(Kind(h)!=OPERAND)
		return INT_MAX;
	else
		return (string[h].info .val );
}

Value_type EvaluatePostfix( )
{
	Kind_type type;
	int h;
	Value_type x,y;
	double St[MAX_STACK];
	int top=-1;
	postlength=-1;
	do{
		GetToken1(h);
		switch(type=Kind(h))
		{
		case OPERAND:
			top++;
			St[top]=GetValue(h);
			break;
		case SINGLE:
			x=St[top];
			top--;
			top++;
			St[top]=DoUnary(h,x);
			break;
		case BINARY:
			y=St[top];
			top--;
			x=St[top];
			top--;
			top++;
			St[top]=DoBinary(h,x,y);
			break;
		case END:
			x=St[top];
			top--;
			if(top>-1)
			{
				for(int i=0;i<28;i++)
					printf(" ");
				printf("表达式不正确!\n");				
			}			
			break;
		}
	}while(type!=END);
	return (x);
}