第2章第1节练习题1 判断栈的操作次序是否合法
最后更新于：2022-04-01 19:51:34
## 问题描述
> 假设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
#include
#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;
}
}
~~~
';