牛骨文教育服务平台(让学习变的简单)

问题描述

假设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]!=""){
        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!
");
    }else{
        printf("The subsquence legal!
");
    }

    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!="
");
}
//判断合法性
int JudgeLegal(SqStack *s)
{
    int i=0;
    int j=0;
    int k=0;
    while(s->data[i]!=""){
        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;
    }
}