2419 - 判断序列(栈实现)

假设以I和O分别表示栈的入栈和出栈操作(入栈用I表示,出栈用O表示),栈的初始状态为空。已知规定由入栈和出栈操作组成的操作序列仅由I和O组成,又称可以操作的序列为合法序列,否则称为非法序列。现有一个只包含I和O两种字符的序列,请你判断序列是否合法。

如I、IO、III、IOIIOIOO均为合法序列;O、OI、IOO、IOOIOIIO为非法序列。

请你设计一个程序,判断给定的操作序列是否合法。

输入

一行I和O的操作序列,以回车结束输入。只包含I、O两种符号。

输出

一行英文字符:“YES”或“NO”。

样例

输入

IOIIOIOO

输出

YES

输入

IOOIOIIO

输出

NO

提示

【数据范围】

对于30%的数据满足:序列的长度小于等于100;

对于50%的数据满足:序列的长度小于等于1000;

对于100%的数据满足:序列的长度小于等于100000;

【样例1解释】

初始状态下,题目中已说明,栈中没有元素;

第一个字符I读入后,表示进栈一个元素,此时栈中有1个元素;

第二个字符O读入后,表示出栈一个元素,此时栈中没有元素;

第三个字符I读入后,表示进栈一个元素,此时栈中有1个元素;

第四个字符I读入后,表示进栈一个元素,此时栈中有2个元素;

第五个字符O读入后,表示出栈一个元素,此时栈中有1个元素;

第六个字符I读入后,表示进栈一个元素,此时栈中有2个元素;

第七个字符0读入后,表示出栈一个元素,此时栈中有1个元素;

第八个字符0读入后,表示出栈一个元素,此时栈中没有元素;

此时读入结束,栈中没有元素,序列可以操作,故序列为合法序列。

【样例1解释】

初始状态下,栈中没有元素;

第一个字符I读入后,表示进栈一个元素,此时栈中有1个元素;

第二个字符O读入后,表示出栈一个元素,此时栈中没有元素;

第三个字符O读入时,表示出栈一个元素,此时栈中没有元素依然执行出栈,操作不成功,直接报错,返回错误信息。

时间限制 3 秒
内存限制 128 MB
讨论 统计
上一题 下一题