相同序列(栈和队列)

相同序列(栈和队列)

时间： 1ms        内存：1000M

描述：

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

输入：

a+b&b+a

输出：

YES

示例输入：

1+3&3-1

示例输出：

NO

提示：

参考答案（内存最优[752]）：

#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; 
}

参考答案（时间最优[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; 
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。