switch.cpp

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

#include<iostream>
#include<fstream>
using namespace std;
template<class T>
class Stack
{
	public:
		Stack(int n);
		~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 n)
{
	MaxTop=n-1;
	stack=new T[MaxTop];
	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;
};
int main()
{
	ifstream in ("input.txt");
	ofstream out ("output.txt");
    if(in.fail())
	{
		out<<"the input.txt is not exist!";
		exit(1);
	}
	int n;
	in>>n;
	if(n%2!=0) 
	{
		out<<"error!"<<endl<<"请重新输入数值!";
		exit(1);
	}
	int *L;
	L=new int[n+1];
	for(int i=1;i<=n/2;i++)
	{
		int p,q;
		in>>p>>q;
		L[p]=q;
		L[q]=p;
	}
	Stack<int> S(n);
	for(int j=1;j<=n;j++)
	{   if(S.Empty())
		   S.Push(j);
		else
		{
		  int r=S.Top();
		  if(L[r]==j||L[j]==r)
			S.Pop(r);
		  else S.Push(j);
		}
	}
	if(S.Empty()) out<<"Yes"<<endl;
	else out<<"No"<<endl;
    in.close();
    out.close();
	return 0;
}