## 问题描述 > 假设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; } } ~~~