bdashi.cpp

表达式求值

#include <stdio.h>

#include <iostream.h>
static int n=0;
//////////////////////////////////////////////
typedef struct{
	double *base;
	double *top;
	int stacksize;
}Int_SqStack;
////////////////////////////////////////////////
typedef struct{
	char *base;
	char *top;
	int stacksize;
}Char_SqStack;
//////////////// //////////////////////////////
void InitStack(Int_SqStack &S,int maxsize);
int Push(Int_SqStack &S,double e);
int Pop(Int_SqStack &S,double &e);
int StackEmpty(Int_SqStack S);
int Gettop(Int_SqStack S,double &ch);
void InitStack(Char_SqStack &S,int maxsize);
int Push1(Char_SqStack &S,char e);
int Pop(Char_SqStack &S,char &e);
int StackEmpty(Char_SqStack S);
int Gettop(Char_SqStack &S,char &ch);
int comp(char ch);
int precede(char c,char ch);
int In(char ch);
void Pass(char suffix[],char ch,int n);
double charToDouble(char a);
char doubleToChar(double a);
void transform(char suffix[],char exp[]);
double js(char suffix[]);
void zhengli(char exp[]);
//////////////////////////////////////////////
void InitStack(Int_SqStack &S,int maxsize){
	S.base = new double[maxsize];
	
	S.top = S.base;
	S.stacksize=maxsize;
}
int Push(Int_SqStack &S,double e){
	if(S.top-S.base>=S.stacksize)
		return 0;
	*S.top++=e;
	    return 1;
}
int Pop(Int_SqStack &S,double &e){
	if(S.top==S.base)
		return 0;
	e=*--S.top;
	    return 1;
}
int StackEmpty(Int_SqStack S){
	if(S.base==S.top)
		return 1;
	else return 0;
}

int  Gettop(Int_SqStack S,double &ch){
	if(S.base==S.top)
		return 0;
	ch=*(S.top-1);
	return 1;
}

/////////////////////////////////////////////
void InitStack(Char_SqStack &S,int maxsize){
	
	S.base = new char[maxsize];
	if(!S.base)cout<<"失败！"<<endl;
	S.top=S.base;
	S.stacksize=maxsize;
}
int Push(Char_SqStack &S,char e){
	
	if(S.top-S.base>=S.stacksize)
	return 0;
	
    *S.top++=e;
	return 1;
}
int Pop(Char_SqStack &S,char &e){
	if(S.top==S.base)
		return 0;
	e=*--S.top;
	    return 1;
}
int StackEmpty(Char_SqStack S){
	if(S.base==S.top)
		return 1;
	else return 0;
}


int Gettop(Char_SqStack &S,char &ch){
	if(S.base==S.top)
		return 0;
	ch=*(S.top-1);
	return 1;
}
//////////////////////////////////////////////////	
int comp(char ch){
	switch(ch){
	case '-':return 1;break;
    case '+':return 1;break;
	case '*':return 2;break;
	case '/':return 2;break;
	case '(':return 0;break;
	case '#':return -1;break;
	default: return -2;
	}
}
int precede(char c,char ch){
	if(comp(c)>=comp(ch))
		return 1;
	else return 0;
}
int In(char ch){
	if(ch=='-'||ch=='+'||ch=='*'||ch=='/'||
		ch=='('||ch==')'||ch=='#')
		return 1;
	else return 0;
}
void Pass(char suffix[],char ch,int i){

	suffix[i-1]=ch;
	
}
double charToDouble(char a){
	return (double)a-48;
}
char doubleToChar(double a){
	char b= (char)(a+48);
	return b;
}
////////////////////////////////////////////////

//////////////////////////////////////////////
void transform(char suffix[],char exp[]){
	Char_SqStack S;
	InitStack(S,50);
	char c;
	Push(S,'#');
	char *p=exp;
	char ch=*p;
    
	while(!StackEmpty(S)){
		if(!In(ch))
		{n++;Pass(suffix,ch,n);}
		else{
			switch(ch){
			case '(':Push(S,ch);break;
			case ')':Pop(S,c);
				while(c!='('){
				n++;	Pass(suffix,c,n);Pop(S,c);
				}
				break;
			default:
				
				while(Gettop(S,c)&&precede(c,ch)&&c!='#')
				{Pop(S,c);n++;Pass(suffix,c,n);}
				if(ch!='#')Push(S,ch);
				break;
			}
			}
		
		if(ch!='#'){p++;ch=*p;}
		else 
		{	while(Gettop(S,c)&&c!='#')
		{Pop(S,ch);n++;Pass(suffix,ch,n);}
		    Pop(S,c);n++;Pass(suffix,ch,n);
		}
	}

	

}
/////////////////////////////////////////////////////
double js(char suffix[]){
	double x,y;
	double z,c;
	int i=0;
	Int_SqStack s;
	InitStack(s,50);
	while(suffix[i]!='#'){
		if(suffix[i]>='0'&&suffix[i]<='9')
		{
			x=charToDouble(suffix[i]);
			Push(s,x);i++;
		}
		else
		{
			Pop(s,y);Pop(s,x);
			if(suffix[i]=='+')
			{ 
			   z=x+y;Push(s,z);i++;
			}
            if(suffix[i]=='-')
			{  
			   z=x-y;Push(s,z);i++;
			}
			if(suffix[i]=='*')
			{  
			   z=x*y;Push(s,z);i++;
			}
			if(suffix[i]=='/')
			{  
			   z=x/y;Push(s,z);i++;
			}
		}
	}
		Gettop(s,c);
		return c;
}


///////////////////////////////////////////////////
void main(){
	char suffix[50];
	char exp[50];
    
	
	
	cout<<"请输入您要计算的表达式(如:3+4-(6+9/2)+2*2#)"<<endl;
	
	
	int i=0;
	do{
		cin>>exp[i];i++;
		
	}while(exp[i-1]!='#');
	
	
     
    transform(suffix,exp);
    for(int j=0;j<i;j++)
	{
        cout<<suffix[j]<<"    ";  	
	
	}
    cout<<endl<<js(suffix)<<endl;
	
	

}