lei.h

包括树的构造

#include <iostream>
#include <string>
#include "Stack.h"
using namespace std;
template<class T>
class MidOrder             //运算符
{
public:
	MidOrder(){}
	~MidOrder(){}
	void Input(){cin>>str;}
	MidOrder<T>&EraseError();//除去输入中误输入的字符，比如aaa2+3擦去aaa
	bool Count(T x,T y,char sign,T& result);//计算x sign y,结果放入result，sign=+、-、*、/
	T Distribute(); //分配入栈
protected:
private:
	string str;//输入的字符串
	Stack<T> NumStack;//数据栈
	Stack<char> SignStack;//符号栈
};
template<class T>
MidOrder<T>&MidOrder<T>::EraseError()
{
	int len=str.length();
	while ((str[0]<48||str[0]>57)&&str[0]!='-'&&str[0]!='(')
	{
		str.erase(str.begin());//erase---擦去str第一个字符,是系统自带的函数
		if(str.length()==0)break;
	}
	if(str.length()==0)throw OutOfBounds();//对应于输入aaaaaa这种情况
	return *this;
}
template<class T>
bool MidOrder<T>::Count(T x,T y,char sign,T& result)
{
	switch(sign)
	{
	case '+':result=x+y;
		break;
	case '-':result=x-y;
		break;
	case '*':result=x*y;
	    break;
	case '/':if(y==0)throw OutOfBounds();result=x/y;
	    break;
//	case '%':result=x%y;         //只有当T是int才用这行
	//	break;
	default: return false;
	    break;
	}
	return true;
}
int PRI(char sign)//计算sign的优先级
{
	if (sign=='*'||sign=='/'||sign=='%')return 2;
	if(sign=='+'||sign=='-')return 1;
	return 0;
}
template<class T>
T MidOrder<T>::Distribute()
{
	EraseError();//擦去不正确的输入
	cout<<str<<endl;//输出实际要计算的表达式
	for (int i=0;i<str.length();)
	{
		if (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='('))//读入的是数字。str[i]=='-'&&i==0对应输入的第一个数是负数，str[i]=='-'&&str[i-1]=='('对应的是在表达式中的(-8+9)这种情况
		{
			T num;
			string one_num;
			while (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='(')||str[i]=='.')
			{
				one_num.append(str[i],1);//////////&str[i]
			    i++;
			}
			num=atof(&one_num[0]);//系统函数，将字符串one_num转换成一个T型的数
			NumStack.Add(num);
			cout<<"把"<<num<<"压入数据栈!"<<endl;
			continue;
		}
		if (SignStack.IsEmpty()||str[i]=='(')
		{
			SignStack.Add(str[i]);
			i++;
			cout<<"把"<<str[i-1]<<"压入符号栈!"<<endl;
			continue;
		}
		if (str[i]==')')
		{
			char sign;
			while (SignStack.Top()!='(')
			{
				SignStack.Delete(sign);
				cout<<"弹出"<<sign<<"."<<endl;
				T x,y,res;
				NumStack.Delete(x);
				cout<<"弹出"<<x<<"."<<endl;
				NumStack.Delete(y);
				cout<<"弹出"<<y<<"."<<endl;
				Count(y,x,sign,res);
				NumStack.Add(res);
				cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
			}
			SignStack.Delete(sign);
			cout<<"将符号"<<sign<<"压入符号栈!"<<endl;
			i++;
			continue;
		}
		if (PRI(str[i])>PRI(SignStack.Top()))
		{
			SignStack.Add(str[i]);
			cout<<"把"<<str[i]<<"压入符号栈!"<<endl;
			i++;
			continue;
		}
		else 
		{
			char sign;
			SignStack.Delete(sign);
			cout<<"弹出"<<sign<<"."<<endl;
			T x,y,res;
			NumStack.Delete(x);
			cout<<"弹出"<<x<<"."<<endl;
			NumStack.Delete(y);
			cout<<"弹出"<<y<<"."<<endl;
			Count(y,x,sign,res);
			NumStack.Add(res);
			cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
			SignStack.Add(str[i]);
			cout<<"把"<<str[i]<<"压入符号栈!"<<endl;
			i++;
			continue;
		}
	}
	while (!SignStack.IsEmpty())
	{
		char sign;
		SignStack.Delete(sign);
		cout<<"弹出"<<sign<<"."<<endl;
		T x,y,res;
		NumStack.Delete(x);
		cout<<"弹出"<<x<<"."<<endl;
		NumStack.Delete(y);
		cout<<"弹出"<<y<<"."<<endl;
		Count(y,x,sign,res);
		NumStack.Add(res);
		cout<<"将计算的结果"<<res<<"压入数据栈!"<<endl;
	}
	return NumStack.Top();
}