資料結構 — 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;
}