calculation.txt

c数据结构中用做表达式计算的c源代码 能够实现运算符的优先级

}SqStack;

void InitStack (SqStack &S)	      
{   
	//构造一个空栈s
	S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
	if(!S.base) exit (-1);										
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;				
}

bool GetTop (SqStack S,SElemType  &e)
{	
	//若栈不空，则用e返回s的栈顶元素，并返回OK；否则返回ERROR;
	if(S.top==S.base)
		return false;
	e=*(S.top-1);
	return true;
}

bool Push(SqStack &S,SElemType e)
{	
	//插入元素e为新的栈顶元素
	if(S.top-S.base>=S.stacksize)
	{							
		S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
			if(!S.base)			
				exit(-1);		
			S.top=S.base+S.stacksize;
			S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
	return true;
}

bool  Pop(SqStack &S,SElemType &e)
{
	//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
	if(S.top==S.base)
		return false;
	e=*--S.top;				
	return true ;
}

char Precede(char a ,char b)
{
	//比较a，b的优先级，返回PR
	char PR;
	switch(b)
	{
		case'+':						
		case'-':if(a=='('||a=='#')
				   PR='<';
			    else
				   PR='>';
			    break;
		case'*':						
		case'/':if(a=='*'||a=='/'||a==')')
				   PR='>';
			    else
			   	   PR='<';
			    break;
		case'(':if(a==')')
				{
				  cout<<"括号匹配错误!"<<endl;
			      exit(-1);
				}
			    else
				  PR='<';
			    break;
		case')':if(a=='(')
		          PR='=';
			    else if(a=='#')
				      {
				         cout<<"error!没有左括号"<<endl;
			             exit (-1);
				      }
			         else
				       PR='>';
			    break;
		case'#':  switch(a)
				  {
		             case'#':   PR='=';
				                break;
		             case'(':   cout<<"error!没有右括号"<<endl;
				                exit(-1);
			         default:   PR='>';
				  }break;
	}
	return PR;
}
                   
bool In(char a)
{
	//判断a是否为运算符
	switch(a)
	{
	case'+':
	case'-':
	case'*':
	case'/':
	case'(':
	case')':
	case'#':
		return true;
	default:
		return false;
	}
}

SElemType Operate( SElemType a, SElemType theta,SElemType b )
{
	//根据不同的theta进行不同的运算
	char n=char(theta);
	switch(n)    
	{
	case'+':   return a+b;
	case'-':   return a-b;
	case'*':   return a*b;
	default:
		if(b!=0)
			return a/b;
		else
		{
			cout<<"error!除数不能为零"<<endl;
			exit(-1);
		}
	}
}

SElemType EvaluateExpression()
{
	//算术表达式求值的算符优先算法、设OPTR和OPND分别为运算符栈和运算数栈
	SqStack OPTR,OPND;
	char c;
	char Number[10];
	SElemType a,b,d,e;
	InitStack(OPTR);
	InitStack(OPND);
	Push(OPTR,'#');
	c=getchar();
	GetTop(OPTR,e);
	while(c!='#'||e!='#')
	{
		if(In(c))
		{
			switch(Precede(e,c))
		   {
			case'<':			
				Push(OPTR,c);
				c=getchar();
				break;
			case'=':				
				Pop(OPTR,e);
				c=getchar();
				break;
			case'>':				
				Pop(OPTR,e);
				Pop(OPND,b);
				Pop(OPND,a);
				Push(OPND,Operate(a,e,b));
				break;
			}
		}
		else if(c>='0'&&c<='9'||c=='.')
		{
			int i=0;
			while(c>='0'&&c<='9'||c=='.')
			{
				Number[i]=c;
				i++;
				c=getchar();
			}
			Number[i]='\0';
			d=atof(Number);
			Push(OPND,d);
		}
		else
		{
			cout<<"error!输入错误!"<<endl;
			exit(-1);
		}
		GetTop(OPTR,e);
	}
	GetTop(OPND,e);
	return e;
}

int main()
{
	SElemType  result;
	cout<<"请输入表达式以#号结束!"<<endl;
	result=EvaluateExpression();
	cout<<"运算结果:"<<result<<endl;
	return 0;
}