pattern.cpp

FZU 大二 的数据结构与算法 老师出的题目的优秀作业 第2到第5章

#include<iostream.h>
#include<fstream.h>
#include<string.h>
ifstream in("input.txt");	
ofstream out("output.txt");


class NoMem{
public:
	NoMem(){}
};

class OutOfBounds{
public:
	OutOfBounds(){}
};

template<class T>
class Stack{
	public:
		Stack(int Max=10);
		~Stack(){delete[]stack;}
		bool Empty()const{return top==-1;}
		bool Full()const{return top==MaxTop;}
		T Top()const;
		Stack<T>&Push(const T& x);
		Stack<T>&Pop(T& x);
	private:
		int top;
		int MaxTop;
		T*stack;
};

template<class T>
Stack<T>::Stack(int Max)
{
	MaxTop=Max-1;
	stack=new T[Max];
	top=-1;
}

template<class T>
T Stack<T>::Top()const
{
	if(Empty())throw OutOfBounds();
	else return stack[top];
}

template<class T>
Stack<T>&Stack<T>::Push(const T& x)
{
	if(Full())throw NoMem();
	stack[++top]=x;
	return *this;
}

template<class T>
Stack<T>&Stack<T>::Pop(T& x)
{
	if(Empty())throw OutOfBounds();
	x=stack[top--];
	return *this;
}

const int M=100;
void Pattern(char *str)
{
	Stack<char>S(M);
    int n=strlen(str);
    
	for(int i=0;i<(n-1)/2;i++)//注释中代码是后来添加的，因为整个字符串除了中间可以有#，其它都不可以出现#.
		/*if(str[i]=='#')
		{
			out<<"No"<<endl;
		    return;
		}
		else*/
		S.Push(str[i]);//将#前面的那个子串存在栈S中
	for(int k=(n-1)/2+1;k<n&&S.Empty()!=1;k++)//与后面的另一个子串进行比较
		if(str[k]==S.Top())
			S.Pop(str[k]);
		else
		{
			
			out<<"No"<<endl;
			break;
		}
	if(S.Empty())
		{
			
	        out<<"Yes"<<endl;
		}
	
}


void main()
{
	int n;

	in>>n;
	 char**str=new char*[M];//创建一个动态二维数组
	 for(int k=0;k<M;k++)
		 str[k]=new char[M];
	for(int i=0;i<n;i++)
	{
		in>>str[i];
	}

	for(i=0;i<n;i++)
	{
		int m=strlen(str[i]);

		/*if(m%2==1)*///说明一下：注释里的代码是后来自己觉得应该改进的，才添加进去的。
		{
			if(str[i][(m-1)/2]=='#')//先确定#是否在中间位置，这一步可以排除很多不可能的情况。
			{
				Pattern(str[i]);
			}
	        else
			{
				out<<"No"<<endl;
			}
		}
		/*else
			 out<<"No"<<endl;*/
		      
	}

	for(k=0;k<M;k++)
		  delete[]str[k];
	  delete[]str;
	  str=0;
}