判断操作是否合法(栈和队列)

时间: 1ms        内存:128M

描述:

假设以I和O分别表示进栈和出栈操作,栈的初态和终态均为空,进栈和出栈的操作序列可表示为仅由I和O组成的序列。

顺序栈的定义为

typedef struct
{
    ElemType data[SizeMax];
    int top;
}SqStack;
 
编写一个算法,判断栈中的序列是否合法!若合法则返回1,否则返回0.
需编写的算法为:int judge(SqStack *s);

输入:

输入为一个字符串,表示进栈出栈的操作序列,该序列存储在栈中。

输出:

若操作序列合法则输出“Yes”,否则输出"No"。

示例输入:

IOIIOIOO

示例输出:

Yes

提示:

参考答案(内存最优[1092]):

#include<stdio.h>
#include<string.h>
typedef struct s
{
    char a[100];
    int top;
}node;
int judge(char str[],int n)
{
    node s;
    s.top=-1;
    int i;
    for(i=0;i<n;i++)
    {
        if(str[i]=='I')
        {
            s.top++;
            s.a[s.top]=str[i];
        }
        else if(str[i]=='O'&&s.top!=-1)
        {
            s.top--;
        }
        else
        {
            return 0;
            break;
        }
    }
    if(s.top==-1)return 1;
    else return 0;
}
int main()
{
    char str[100];
    while(~scanf("%s",str))
    {
    int n;
    n=strlen(str);
    if(judge(str,n))printf("Yes\n");
    else printf("No\n");
    }

    return 0;
}

参考答案(时间最优[0]):


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SizeMax 105
typedef char ElemType;
typedef struct
{
    ElemType data[SizeMax];
    int top;
}SqStack;
void InitStack(SqStack *&s)
{
    s=(SqStack*)malloc(sizeof(SqStack));
    s->top=-1;
}
bool Push(SqStack *&s,ElemType c)
{
    if(s->top==SizeMax-1)return false;
    s->top++;
    s->data[s->top]=c;
    return true;
}int judge(SqStack *s)
{
    int t=0;
    for(int i=0;i<=s->top;i++)
    {
        if(s->data[i]=='I')t++;
        else t--;
        if(t<0)return 0;
    }
    if(t==0)return 1;
    else return 0;
}
void DestroyStack(SqStack *&s)
{
    free(s);
}
int main()
{
    SqStack *s=NULL;
    InitStack(s);
    char c[SizeMax];
    gets(c);
    for(int i=0;i<(int)strlen(c);i++)
        Push(s,c[i]);
    if(judge(s))printf("Yes\n");
    else printf("No\n");
    DestroyStack(s);
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。