数据结构 — 3.模式匹配

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

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

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

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

【样例输出】yes

/* 
  顺序栈
*/

#include<stdio.h>
#include<stdlib.h>

//栈容量
#define MAXSIZE 1024

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

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

int SqStack_Pop(SqStack a){

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

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