# 相同序列(栈和队列)

试写一个算法，识别依次读入的一个以@为结束符的字符序列是否为形如‘序列1&序列2’模式的字符序列。其中序列1和序列2中都不含字符‘&’，且序列2是序列1的逆序列。输出YES或者NO。

a+b&b+a

YES

``1+3&3-1``

``NO``

``````#include<stdio.h>
#include<malloc.h>
#define SEN 100

struct sqstack
{
char *base;
char *top;
int size;
};

struct sqstack *initEmptyStack()   /*构建空輚*/
{
struct sqstack *p;
p=(struct sqstack *)malloc(sizeof(struct sqstack));
if(p!=NULL)
{
p->base=(char *)malloc(sizeof(struct sqstack)*SEN);
if(p->base!=NULL)
{
p->top=p->base;
p->size=SEN;
return p;
}
}
else
free(p);
return NULL;
}

int push(struct sqstack *p,char a)         /*入栈*/
{
*p->top++=a;
return 0;
}

int gettop(struct sqstack *p)             /*取栈顶元素*/
{
if(p->base!=p->top)
return *(p->top-1);
return 0;
}

int pop(struct sqstack *p)              /*出栈*/
{
return *(--p->top);
}

int main()
{
char c,a;
int t=0;
struct sqstack *p;
p=initEmptyStack();
while(scanf("%c",&c)&&c!='\n')
{
if(c!='&'&&t==0)
push(p,c);
else
t=1;
if(c!='&'&&t==1)
{
a=gettop(p);
if(c!=a)
{
printf("NO\n");
return 0;
}
else
pop(p);
}
}
if(p->base!=p->top)
printf("NO\n");
else
printf("YES\n");
return 0;
}``````

``````#include<stdio.h>
#include<malloc.h>
#define SEN 100

struct sqstack
{
char *base;
char *top;
int size;
};

struct sqstack *initEmptyStack()   /*构建空輚*/
{
struct sqstack *p;
p=(struct sqstack *)malloc(sizeof(struct sqstack));
if(p!=NULL)
{
p->base=(char *)malloc(sizeof(struct sqstack)*SEN);
if(p->base!=NULL)
{
p->top=p->base;
p->size=SEN;
return p;
}
}
else
free(p);
return NULL;
}

int push(struct sqstack *p,char a)         /*入栈*/
{
*p->top++=a;
return 0;
}

int gettop(struct sqstack *p)             /*取栈顶元素*/
{
if(p->base!=p->top)
return *(p->top-1);
return 0;
}

int pop(struct sqstack *p)              /*出栈*/
{
return *(--p->top);
}

int main()
{
char c,a;
int t=0;
struct sqstack *p;
p=initEmptyStack();
while(scanf("%c",&c)&&c!='\n')
{
if(c!='&'&&t==0)
push(p,c);
else
t=1;
if(c!='&'&&t==1)
{
a=gettop(p);
if(c!=a)
{
printf("NO\n");
return 0;
}
else
pop(p);
}
}
if(p->base!=p->top)
printf("NO\n");
else
printf("YES\n");
return 0;
}``````