123.cpp

数据结构里的经典算法的模拟

enum Boolean{ False,True};
#include<iostream.h>
template <class T>class cal;
template <class T>class stack
{
	friend class cal<T>;
public:
	int tp;
	T a[100];
	stack<T> instack(stack<T> S);          //初始化栈
	stack<T> push(stack<T> S,T x);         //压
	stack<T> pop(stack<T> S);                     
	T top(stack<T> S);                     //
	int empty(stack<T> S);                  //是否为空
	void makeempty(stack<T> S);
	

};
stack<int>s;
stack<char>s3;
template <class T>
stack<T> stack<T>::instack(stack<T> S)              //初始化栈
{  
	S.tp=-1;
	return S;
}
template<class T>
stack<T> stack<T>::push(stack<T> S,T x)             //对来的压栈处理
{   
	S.tp++;                                     
	S.a[S.tp]=x;
	return S;
}
template<class T>
stack<T> stack<T>::pop(stack<T> S)                     //退栈处理函数
{   
	S.tp--;
	return S;
}
template <class T>
T stack<T>::top(stack<T> S)             //取栈顶元素
{   
	return S.a[S.tp];
}
template<class T>
int stack<T>::empty(stack<T> S)                //判断是否为空
{   
	if(S.tp==-1)
		return 1;
	else
		return 0;
}
template<class T>
void stack<T>::makeempty(stack<T> S)
{
	while(S.tp!=-1)
	{
		S=S.pop(S);
	}
}

template <class T>
class cal
{
private:
	Boolean gettwo(int&op1,int&op2);    //取两个操作数
	void compute(char op);                     //进行运算
public:
	cal(){};
	void enter(T num);                        //压num入栈
	void run(void);                             //后缀计算
	void clear(void);
	int predeence(char op);
	void change(char*s1,char*s2);

};
template <class T>
void cal<T>::enter(T num)
{   

	s=s.push(s,num);
}
template <class T>
Boolean cal<T>::gettwo(int&op1,int&op2)
{   
	if(s.empty(s)==1)
	{
		cout<<"取操作数出错"<<endl;
		return False;
	}
	op1=s.top(s);
	s=s.pop(s);
	if(s.empty(s)==1)
	{
		cout<<"取操作数出错 "<<endl;
		return False;
	}
	op2=s.top(s);
	s=s.pop(s);
	return True;
}
template <class T>
void cal<T>::compute(char op)
{   

	Boolean result;
	int op1,op2;
	result=gettwo(op1,op2);
	if(result==True)
		switch(op)
	{
case'+': s=s.push(s,op2+op1);
	cout<<"将左操作数 "<<op2<<"和右操作数 "<<op1<<"依次弹出并进行'+'运算"<<endl;
	cout<<"结果 "<<s.top(s)<<"送回栈继续"<<endl;
	break;
case'-': s=s.push(s,op2-op1);
	cout<<"将左操作数 "<<op2<<"和右操作数 "<<op1<<"依次弹出并进行'-'运算"<<endl;
	cout<<"结果 "<<s.top(s)<<"送回栈继续"<<endl;
	break;
case'*': s=s.push(s,op2*op1);
	cout<<"将左操作数 "<<op2<<"和右操作数 "<<op1<<"依次弹出并进行'*'运算"<<endl;
	cout<<"结果 "<<s.top(s)<<"送回栈继续"<<endl;
	break;
case'/': 
	if(op1==0.0)
	{
		cout<<"除数不能是0，出错了！"<<endl;
		s.makeempty(s);
	}
	else
		s=s.push(s,op2/op1);
	cout<<"将左操作数 "<<op2<<"和右操作数 "<<op1<<"依次弹出并进行'/'运算"<<endl;
	cout<<"结果 "<<s.top(s)<<"送回栈继续"<<endl;
	break;
	}
	else
		s.makeempty(s);
}
template <class T>
void cal<T>::run()
{   
	char c;
	int newoper;
	cout<<"请按顺序输入上面的后缀表达式以'='号结束:"<<endl;
	while(cin>>c,c!='=')
		switch(c){
case'+':
case'-':
case'*':
case'/':
	compute(c);
	break;
default:
	cin.putback(c);
	cin>>newoper;
	enter(newoper);
	break;
	}
	if(s.empty(s)!=1)
		cout<<"最后结果为: "<<s.top(s)<<endl;
}
template <class T>
void cal<T>::change(char*s1,char*s2)
{   
	s3=s3.push(s3,'=');
	int i=0,j=0;
	char ch=s1[i];
	while(ch!='=')
	{
		if(ch=='(')
		{
			s3=s3.push(s3,ch);
			ch=s1[++i];
		}
		else if(ch==' ')
			ch=s1[++i];
		else if (ch>='0'&&ch<='9')
		{
			while(ch>='0'&&ch<='9')
			{
				s2[j++]=ch;ch=s1[++i];
			}
			s2[j++]=' ';
		}
		else if (ch==')')
		{       
			    if(s3.top(s3)=='=')
				{
					cout<<"表达式错了!请重输入"<<endl;
					s3.makeempty(s3);
				}
				else
				{
					while(s3.top(s3)!='('&&s3.top(s3)!='=')
					{ 
						s2[j++]=s3.top(s3);
					    s3=s3.pop(s3);
					}
					if(s3.top(s3)=='=')
					{
						cout<<"不能这样输入表达式!请重输入"<<endl;
						break;
					}
					else
						s3=s3.pop(s3);

				}
		
				ch=s1[++i];
		}
		else if(ch=='+'||ch=='-'||ch=='*'||ch=='/')
		{   
			
			char w=s3.top(s3);
			while(predeence(w)>=predeence(ch))
			{
				s2[j++]=w;
				s3=s3.pop(s3);
				w=s3.top(s3);
			}
				s3=s3.push(s3,ch);
				ch=s1[++i];

		}		
		
	}
	ch=s3.top(s3);
	s3=s3.pop(s3);
	
		while(ch!='=')
		{
			if(ch=='(')
			{
				cout<<"表达式输入错误!请重输入 "<<endl;
			    s3.makeempty(s3);
			    break;
			}
		    else
			{
				s2[j++]=ch;
			    ch=s3.top(s3);
			    s3=s3.pop(s3);
			}
		}
		s2[j++]='\0';
	
	
}
template <class T>
int cal<T>::predeence(char op)
{
	switch(op)
	{
	case'+':
	case'-':
		return 1;
	case'*':
	case'/':
		return 2;
	case'(':
	case'=':
	default:
		return 0;
	}
}

void main()
{   

	s=s.instack(s);
	s3=s3.instack(s3);
	cal<char> s1;
	char a[30];
	char b[30];
	cout<<"请输入中缀表达式以'='号结束："<<endl;
	cin.getline(a,sizeof(a));
	s1.change(a,b);
    cout<<b;
	cout<<endl;
    s1.run();
	
}