pattern.cpp

设计一个算法

#include <iostream.h>
#include <fstream.h>
#include<cstring>
template<class T>
class Stack
{	
	friend bool  Parenthesis(char *str);
public:
	Stack(int Max=100);
	~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;//栈元素数组	
};
在上述的栈类Stack的定义中，栈元素存储在数组stack中。用top指向当前栈顶位置。栈的容量为Maxtop.
栈类Stack的构造函数容易实现如下：
template<class T>
Stack<T>::Stack(int Max)
{
	Maxtop=Max-1;
	stack=new T[Max];
	top=-1;
}
栈顶元素存储在Stack[top]中：
template<class T>
T Stack<T>::Top() const
{
	if(Empty()) throw OutOfBounds();
	else return stack[top];
}
新栈顶元素x应存储在stack[top+1]中：
template<class T>
Stack<T>&Stack<T>::Push(const T& x)
{

	stack[++top]=x;
	return *this;
}
删除栈顶元素后，新栈顶元素存在stack[top-1]中：
template<class T>
Stack<T>&Stack<T>::Pop(T& x)
{
	x=stack[top--];
	return *this;
}
bool Parenthesis(char *str)
{
	Stack<int>S(100);
    int j,n=strlen(str);//定义n为字符串的长度（不包括“\0”字符）
	for( int i=1;i<=n;i++)
	{
		if(str[i-1]!='#') S.Push(i);
		else break;
	}
	i--;
	if(i<n/2 || i>n/2)  
		return false;
	else
		for(i=n/2+2;i<=n;i++)
		{
			if(str[i-1]==str[n-i])
				S.Pop(j);
		}
	if(S.Empty()) return true;
	else return false;
}
int main()
{  
	char *m=new char[100];		
	bool a;
	int i,n;//定义n表示字符串的数目	
    ifstream in ("input.txt");
    ofstream out("output.txt");	
    in>>n;
	for(i=1;i<=n;i++)
	{
	     in>>m;
	        a= Parenthesis(m);
		if(a) out<<"Yes"<<endl;
		else  out<<"No"<<endl;
	}
	return 0;
}