数据结构 — 3.模式匹配

时间:2025-02-15 17:36:26

【问题描述】试编写一个算法,识别依次读入的一个以@为结束符的字符序列是否为形如"序列1&序列2"模式的字符序

列. 其中序列1和序列2中都不含字符'&',且序列2是序列1的逆序.例如,"a+b&b+a"是属于该模式的字符序列则输

出yes,而"1+3&3-1"则输出no.

【样例输入】a+b&b+a@

【样例输出】yes


/* 
	顺序栈
*/

#include<>
#include<>

//栈容量
#define MAXSIZE 1024

//顺序栈
typedef struct
{
	char *base;
	char *top;
	int n;
}SqStack;

/*
	SqStack_Push
*/
int SqStack_Create(SqStack &a){
	
	//分配内存
	char m;
	 = (char*)malloc(MAXSIZE*sizeof(char));
	
	//判断内存是否分配成功
	if(!)
	exit(1);
	
	//初始化
	 = a .base;
	 = MAXSIZE;
	
	//入栈
	m = getchar();
	while(m != '&'){
	
		//是否超栈容量
		if( >= ){
			 += ;
			 = (char*)realloc(,*sizeof(char));
		}
		
		//入栈
		++;
		* = m;
		
		m = getchar();
		}
		return 0;
}

int SqStack_Pop(SqStack a){

	char x;
	x=getchar();
	
	//出栈操作
	while(!= && x!='@'){
	
		if(x!=*){
		
			printf("no");
			return 0;
			
		}
			--;
			x=getchar();
	}
	
	if(==)
		printf("yes");
	else 
		printf("no");
	return 0;
} 

//主函数
int main()
{
	SqStack L;
	SqStack_Create(L);
	SqStack_Pop(L);
	return 0;
}