数据结构之SWUSTOJ1028: 特定字符序列的判断

题目：

此题关键思路：

 

代码：

#include
#include
#include
typedef struct Stack
{
	char* data;
	int top;//栈顶元素坐标
	int capacity;//栈的容量
}ST;
void STInit(ST* ps)
{
	ps->data = NULL;
	ps->top = 0;//ps->top=-1;
	//初始化时top给0，意味着top指向栈顶数据的下一个
	//初始化时top给1，意味着top指向栈顶数据
	ps->capacity = 0;//初始化容量给0
}
void STCreate(ST* ps)
{
	char x = 0;
	while (x != '#')
	{
		if (ps->top == ps->capacity)
		{
			int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//三目 *** 作符
			//如果ps->capacity等于0，那么就给4个字节的空间，如果不等于0就扩容两倍
			char* tmp = (char*)realloc(ps->data, sizeof(char)*newCapacity);
			if (tmp == NULL)//扩容失败退出程序
			{
				exit(-1);
			}
			ps->capacity = newCapacity;//把capacity换成新的
			ps->data = tmp;//data也指向新的空间
		}
		scanf("%c", &x);
		ps->data[ps->top] = x;
		ps->top++;
	}
}
ST STPop(ST* ps)
{
	ps->top = ps->top - 1;//先把#从栈中去除掉
	ST ListB;
	STInit(&ListB);
	while (ps->top!=0 && ps->data[ps->top-1] != '@')
	{
		if (ListB.top == ListB.capacity)
		{
			int newCapacity = ListB.capacity == 0 ? 4 : ListB.capacity * 2;
			char* tmp = (char*)realloc(ListB.data, sizeof(char)*newCapacity);
			if (tmp == NULL)
			{
				exit(-1);
			}
			ListB.data = tmp;
			ListB.capacity = newCapacity;
		}
		ListB.data[ListB.top] = ps->data[ps->top - 1];
		ListB.top++;
		ps->top--;
	}
	ps->top--;//while循环结束后再减一下top，把@从栈中除掉
	return ListB;
}
bool STJudge(ST* psA, ST* psB)
{
	while (psA->top != 0 && psB->top != 0)
	{
		if (psA->data[psA->top - 1] != psB->data[psB->top - 1])
		{
			return false;//一旦有不相等的就返回false
		}
		else
		{
			psA->top--;
			psB->top--;//迭代条件
		}
	}
	if (psA->top == 0 && psB->top == 0)//都为空栈结束时返回true
		return true;
	else
		return false;
}
int main()
{
	ST List;
	STInit(&List);//栈初始化
	STCreate(&List);//栈创建
	ST ret;
	STInit(&ret);//创建一个ret栈
	ret=STPop(&List);
	bool a;
	a=STJudge(&List, &ret);
	if (a == true)
		printf("yes!");
	else
		printf("no!");
	return 0;
}