判断操作是否合法（栈和队列）
时间： 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;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。