## 問題描述 > 假設I和O分別表示入棧和出棧操作。棧的初狀和終態均為空，入棧和出棧的操作序列可表示僅由I和O組成的序列，可以操作的序列稱為合法序列，否則稱為非法序列。 試寫一個算法完成對下列輸入序列的合法性的判斷。 A. IOIIOIOO B. IOOIOIIO C.IIIOIOIO D.IIIOOIOO ## 算法思想 > 將一個指定序列進行入棧，每掃描至任一位置均需檢測出棧次數（即O的個數）是否小于入棧的次數（即I的個數），若大于則為非法數列。掃描結束后再判斷入棧和出棧次數是否相等，若不相等，則為非法數列。 算法具體描述如下所示： ## 算法描述 ~~~ int JudgeLegal(SqStack *s) { int i=0; int j=0; int k= while(s->data[i]!='\0'){ switch(s->data[i]){ case 'I':j++;break; case 'O':k++; if(k>j){ return -1; } break; } i++; } if(j!=k){ return -1; }else{ return 0; } } ~~~ 具體代碼見附件。 ## 附件 ~~~ #include<stdio.h> #include<stdlib.h> #define MaxSize 100 typedef char ElemType; typedef struct{ ElemType data[MaxSize]; int top; }SqStack; void InitStack(SqStack*); void Push(SqStack*); int JudgeLegal(SqStack*); int main(int argc,char* argv[]) { SqStack s; InitStack(&s); Push(&s); int Flag=JudgeLegal(&s); if(Flag){ printf("The subsqence illegal!\n"); }else{ printf("The subsquence legal!\n"); } return 0; } //初始化棧 void InitStack(SqStack *s) { s->top=-1; } //入棧 void Push(SqStack *s) { ElemType x; do{ scanf("%c",&x); s->data[++s->top]=x; }while(x!='\n'); } //判斷合法性 int JudgeLegal(SqStack *s) { int i=0; int j=0; int k=0; while(s->data[i]!='\0'){ switch(s->data[i]){ case 'I':j++;break; case 'O':k++;if(k>j){return -1;}break; } i++; } if(j!=k){ return -1; }else{ return 0; } } ~~~