dazuoye1.cpp

这是一个使用堆栈来实现的表达式的大作业,要文档,可以联系我.

#include<iostream.h>
#include<malloc.h>
#include<math.h>
typedef struct{                          //建立一个字符的堆栈
	char *base;
	char *top;
	int stacksize;
}SqStack;
void InitStack(SqStack &s)
{
	s.base=(char *)malloc(100*sizeof(char));
	s.top=s.base;
	s.stacksize=100;
}
int StackEmpty(SqStack &s)
{
	if(s.base==s.top)
		return 1;
	return 0;
}
void Push(SqStack &s, char e){
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(char *)realloc(s.base, (s.stacksize+10)*sizeof(char));
		s.top=s.base+s.stacksize;
		s.stacksize+=10;
	}
	*s.top++=e;
}
int Pop(SqStack &s,char &e)
{
	if(s.top==s.base) return 0;
	e=*--s.top;
	return 1;
}


typedef struct{                   //建立一个数据的堆栈
	int *base;
	int *top;
	int stacksize;
}Stackinti;
void InitStacki(Stackinti &s)
{
	s.base=(int *)malloc(100*sizeof(int));
	s.top=s.base;
	s.stacksize=100;
}
void Pushi(Stackinti &s, int e){
	if(s.top-s.base>=s.stacksize)
	{
		s.base=(int *)realloc(s.base, (s.stacksize+10)*sizeof(int));
		s.top=s.base+s.stacksize;
		s.stacksize+=10;
	}
	*s.top++=e;
}
int Popi(Stackinti &s,int &e)
{
	if(s.top==s.base) return 0;
	e=*--s.top;
	return 1;
}
//主函数
int main()
{
	int a,i=0,num,quan;
	bool boolean;
	
	while(!(i==2&&num==0))    //判断是否退出测试数据
	{
    	char b,e;
        SqStack  zi;
	    Stackinti shu;
	    InitStacki(shu);
        InitStack(zi);
		int j,sum=0,m,n;
    	cin>>quan;         //根节点到叶节点的权值之和
		 boolean=false;
		a=0;
		i=1;
		cin>>b;
		Push(zi,b);
		while(!StackEmpty(zi))    //判断一组数据是否输完
		{
		    if(i%2==0)       
			{
	           cin>>b;
			   if(b=='(')
		       Push(zi,b);    //'('进栈
			   else if(b==')')
			   {
				   Pop(zi,e);   //如果是')'，则'('出栈
				   a++;
			   }
			}
		    else
			{
			   cin>>num;         //读入一个节点的权值
			   if(num!=0)           //如果是数字，则进栈
			   {
				   Pushi(shu,num);        
				   sum+=num;           
			   }
			   else              //如果输入是')'，则'('出栈
			   {
				   a++; 
				   if(i%4==2)
					   m=i;
				   else if(i%4==0)
					   n=i;
			       Pop(zi,b);  
			   }
			}
		    if (a%3==0)               //判断是否是到了另一个叶子节点了
			{
			   if(quan==sum&&abs(n-m)==2)
			   boolean=true;
			   else
			   {
		    	Popi(shu,num);
			    sum-=num;
			   }
			}
			cout<<"haha"<<endl;
		    i++;
		}
       if(boolean)
	       cout<<"yes"<<endl;
       else
	      cout<<"no"<<endl;
	}
  return 0;
}