栈操作序列合法性判断算法及代码实现

假设以'I'和'O'分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由'I'和'O'组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1) 下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO

(2) 通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。

(1) 合法序列为A和B，非法序列为C和D。

(2) 算法：

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

实现代码如下：

bool isLegalSequence(char seq[], int n) {
    stack<char> 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();
}