pattern-1.cpp

来自「设计一个算法」· C++ 代码 · 共 77 行

#include <cstring>
#include <iostream.h>
#include <fstream.h>
template<class T>
class Stack
{
	friend bool compare(char *expr);
public:
	Stack(int max=100);
	~Stack(){delete []stack;}
	bool empty() const{return top==-1;}
	bool full() const{return top==maxtop;}
	Stack<T> &push(const T &x);
	Stack<T> &pop(T &x);
private:
	int top,maxtop;
	T *stack;
};
template<class T>
Stack<T>::Stack(int max)
{
	maxtop=max-1;
	stack=new T[max];
	top=-1;
}
template<class T>
Stack<T>&Stack<T>::push(const T &x)
{
	stack[++top]=x;
	return *this;
}
template<class T>
Stack<T> &Stack<T>::pop(T &x)
{
	x=stack[top--];
	return *this;
}
bool compare(char *expr)
{
	Stack<int> s(100);
	int j,n=strlen(expr);
	for(int i=1;i<=n;i++)
	{
		if(expr[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(expr[i-1]==expr[n-i])
				s.pop(j);
		}
	if(s.empty()) return true;
	else return false;
}
int main()
{
	char *y=new char[100];
	bool a;
	int i,n;
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>y;
		a=compare(y);
		if(a) out<<"Yes"<<endl;
		else out<<"No"<<endl;
	}
	return 0;
}