expression.h

算术表达式求值,数据结构课程设计,非常实用,适合学生

/********************************************************
此头文件用于将中缀表达式转换成后缀表达式
调用了求子串函数strstr和堆栈
strstr在string头文件中，堆栈定义在SeqStack头文件中
*********************************************************/

char Proceed(char x1,char x2)
{
	char Result;
	char MidString[2];

	Result='<';
	MidString[0]=x2;
	MidString[1]=0;

	//x1比x2大。比较中利用了求子串函数strstr()
	if(((x1=='+'||x1=='-')&&strstr("+-)#",MidString)!=NULL)||
		((x1=='*'||x1=='/')&&strstr("+-*/)#",MidString)!=NULL)||
		(x1==')'&&strstr("+-*/)#^",MidString)!=NULL)||
		(x1=='^'&&strstr("+-*/)#^",MidString)!=NULL))
		Result='>';

	//x1等于x2
	else if((x1=='('&&x2==')')||(x1=='#'&&x2=='#'))
		Result='=';

	//x1和x2取值出错
	else if((x1=='('&&x2=='#')||(x1==')'&&x2=='(')||(x1=='#'&&x2==')'))
		Result=' ';

	//当3种情况都不是时为x1小于x2
	return Result;
}

int Postfix(char *Expression,char *res)
{
	char x1,x2;
	int j=0,i=0;
	SeqStack<char> s;

	s.Push('#');
	x2=Expression[j];
	x1=s.Peek();

	while(1)
	{
		if(x2!='+'&&x2!='-'&&x2!='*'&&x2!='/'&&x2!='('&&x2!=')'&&x2!='#'&&x2!='^')
		{
			res[i]=x2;
			i++;		
			x2=Expression[++j];
		}
		else if(Proceed(x1,x2)=='<')
		{
			s.Push(x2);
			x1=s.Peek();
			x2=Expression[++j];
		}
		else if(Proceed(x1,x2)=='>')
		{
			x1=s.Pop();
			res[i]=x1;
			i++;		
			x1=s.Peek();
		}
		else if(Proceed(x1,x2)=='='&&x1=='('&&x2==')')
		{
			s.Pop();
			x1=s.Peek();
			x2=Expression[++j];
		}
		else if(Proceed(x1,x2)=='='&&x1=='#'&&x2=='#')
		{
			res[i]='#';			
			return 1;
		}
		else if(Proceed(x1,x2)==' ')
		{
			break;
		}
	}
	cout<<"中缀表达式语法有错!"<<endl;
	return 0;
}