假设以I和O分别表示入栈和出栈操作。栈的初态和终态均为空入栈和出栈的操作序列可表示为仅由I和O组成的序列称可以操作的序列为合法序列否则称为非法序列。1下面所示的序列中哪些是合法的？ A IOIIOIOO B IOOIOIIO C IIIOIOIO D IIIOOIOO2通过对1的分析写出一个算法判定所给的操作序列是否合法。若合法返回true否则返回fals

（1）合法序列为A和B，非法序列为C和D。 （2）算法：

1. 初始化一个空栈stack。
2. 遍历操作序列中的每个操作： a. 如果是入栈操作I，将其压入栈中。 b. 如果是出栈操作O，检查栈是否为空，如果为空则返回false，否则弹出栈顶元素。
3. 如果操作序列遍历完毕后栈为空，返回true，否则返回false。

实现代码如下：

bool isLegalSequence(char seq[], int n) { stack stack; for (int i = 0; i < n; i++) { if (seq[i] == 'I') { stack.push(seq[i]); } else if (seq[i] == 'O') { if (stack.empty()) { return false; } else { stack.pop(); } } } return stack.empty(); }