lei.h

包括树的构造

#include <iostream>
#include <string>
#include "Stack.h"
using namespace std;
template<class T>
class MidOrder
{
public:
	void Input(){cin>>str;}
	MidOrder<T>&Push();
	MidOrder<T>&EraseError();//和那个程序中定义的一样。没变！
	void Output();
protected:
private:
	string str;//输入的字符串
	Stack<T> numstack;//原始数据栈
	Stack<char> signstack;//原始符号栈
	Stack<char> res_signstack;//用来中转的符号栈
	Stack<string> num_signstack;//最后要输出的栈，既有符号，又有数字，所以定义成string型的堆栈方便
};
int *numorsign;//用来标记每一位该输出什么，是符号还是数据。后面再说
int PRI(char sign)//优先级的计算
{
	if (sign=='*'||sign=='/'||sign=='%')return 2;
	if(sign=='+'||sign=='-')return 1;
	return 0;
}
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());
		if(str.length()==0)break;
	}
	if(str.length()==0)throw OutOfBounds();
	return *this;
}
template<class T>
MidOrder<T>&MidOrder<T>::Push()
{	
	EraseError();
	int len=str.length();
	numorsign=new int[len];
	for (int i=0;i<len;)//从左向右扫描，遇到数据就压入原始数据栈，遇到符号就压入原始符号栈
	{
		if (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='('))//和以前处理的思路一样
		{
			T num;
			string one_num;//把数放入这个变量中，比如456.234得把它当作一个数据放在一起
			int m=1;//以后用来控制输入大小的，后面讲
			while (str[i]>47&&str[i]<58||str[i]=='-'&&(i==0||str[i-1]=='(')||str[i]=='.')//对应的条件和那个文件一样
			{
				one_num.append(&str[i],1);//这是系统自带的函数，在one_num的后面增加从str[i]开始的一个字符
			    i++;
				m++;//比如，123.456，m来记录数的位数+1，因为m的初值为1，此例中m=8
			}
			num=atof(&one_num[0]);//系统函数，将char型的转换成float型的，将one_num转换成一个float型的放到num中去。还有像atoi(转换成int),itoa(int转换成char)等等
			numstack.Add(num);//将num压栈
			numorsign[i-1]=m;//为后面输出顺序作铺垫，说明第i个字符是数字还是符号，顺便纪录数字的长度为m-1
			cout<<"将"<<num<<"压入数据栈一。"<<endl;
		}
		else //否则是符号入原始符号栈
		{
			signstack.Add(str[i]);
			cout<<"将"<<str[i]<<"压入符号栈一。"<<endl;
			numorsign[i]=1;
			i++;
		}
	}
	cout<<"------------------------------------"<<endl;
	for(i=len-1;i>=0;i--)//相当于从表达式的右边往左边扫描
	{
		if(numorsign[i]>1)//第i个数是数据，从原始数据栈中弹出数据直接压入num_signstack
		{
			if (!numstack.IsEmpty())//有可能原始符号栈不为空时原始数据栈已经为空
			{
	    		T num;
	    	    string midstr;
				midstr.resize(numorsign[i]-1);//这里就用到了numorsign[i]的值，比如遇到了123.45，那么numorsign[i]=7，给midstr分配这样大的空间，可以节省空间，不然得定义一个很大的数能容纳很多位数的midstr;
	    	    numstack.Delete(num);
				sprintf(&midstr[0],"%g",num);
	    	    num_signstack.Add(midstr);
				cout<<"将"<<num<<"从数据栈一中弹出压入数据栈二。"<<endl;
			}
		}
		else if(numorsign[i]==1)//否则第i个字符为符号，
			if (!signstack.IsEmpty())//同样，有可能原始数据栈不为空时原始符号栈已经为空
			{
		    	char sign;
    		    signstack.Delete(sign);//从原始符号栈弹出符号
				cout<<"将"<<sign<<"从符号栈一弹出，";
	    		if (res_signstack.IsEmpty())//如果中转符号栈为空，sign直接入栈
				{
	    			res_signstack.Add(sign);
					cout<<"将"<<sign<<"压入符号栈二。"<<endl;
				}
				//不为空
    		    else if (sign==')')//遇到“）”也直接入栈
				{
    				res_signstack.Add(sign);
					cout<<"将"<<sign<<"压入符号栈二。"<<endl;
				}
	        	else if (sign=='(')//遇到“（”
				{
		    		string midstr;
	    		    midstr.resize(1);
		    	    while (res_signstack.Top()!=')')//弹出中转符号栈里的符号进入num_signstack，直到遇到“）”
					{
			    		res_signstack.Delete(midstr[0]);
			    		num_signstack.Add(midstr);
						cout<<"将"<<midstr[0]<<"从符号栈二弹出,压入数据栈二。"<<endl;
					}
			    	res_signstack.Delete(midstr[0]);//弹出中转符号栈里的“）”
					cout<<"将"<<midstr[0]<<"从符号栈二弹出。"<<endl;
				}
				else if (PRI(sign)>=PRI(res_signstack.Top()))//优先级比中转符号栈栈顶符号高或等，直接入中转符号栈
				{
	    			res_signstack.Add(sign);
					cout<<"将"<<sign<<"压入符号栈二。"<<endl;
				}
		        else if (PRI(sign)<PRI(res_signstack.Top()))//优先级比中转符号栈栈顶符号低，弹出中转符号栈中的符号进入num_signstack，直到遇到优先级和sign相等或比sign小
				{
			    	string midstr;
		        	midstr.resize(1);
	        		while (!res_signstack.IsEmpty()&&PRI(sign)<PRI(res_signstack.Top()))
					{
			        	res_signstack.Delete(midstr[0]);
		    	    	num_signstack.Add(midstr);
						cout<<"将"<<midstr[0]<<"从符号栈二弹出,压入数据栈二。"<<endl;
					}
					res_signstack.Add(sign);//把sign压栈
					cout<<"将"<<sign<<"压入符号栈二。"<<endl;
				}
			}
	}
	while (!res_signstack.IsEmpty())//如果中转符号栈不为空，则将其一一弹出并压入num_signstack
	{
		string midstr;
		midstr.resize(1);
		res_signstack.Delete(midstr[0]);
		num_signstack.Add(midstr);
		cout<<"将"<<midstr[0]<<"从符号栈二弹出,压入数据栈二。"<<endl;
	}
	delete []numorsign;
	return *this;
}
template<class T>
void MidOrder<T>::Output()
{
	while (!num_signstack.IsEmpty())
	{
		string mid_str;
		num_signstack.Delete(mid_str);
		cout<<"  "<<mid_str;
	}
	cout<<endl;
}