判断出栈入栈序列的合法性

问题描述：

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

1) 下面所示的序列中哪些是合法的？

a. IOIIOIOO     b. IOOIOIIO     c. IIIOIOIO     d. IIIOOIOO

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

问题解答：

1) A、D合法，而B、C不合法。在B中，先入栈1次，再连续出栈2次，错误。在 C中，入栈和出栈次数不一致，会导致最终的栈不空。A、D均为合法序列，请自行模拟。注意：在操作过程中，入栈次数一定大于或等于出栈次数；结束时，栈一定为空。

2) 设被判定的操作序列已存入一维数组A中。算法的基本设计思想：依次逐一扫描入栈出栈序列（即由"I"和"O"组成的字符串），每扫描至任一位置均需检查出栈次数（即 “O”的个数）是否小于入栈次数（"I"的个数)，若大于则为非法序列。扫描结束后，再判断入栈和出栈次数是否相等，若不相等则不合题意，为非法序列。

int Judge(char A[]) {
    //判断字符数组A中的输入输出序列是否是合法序列。如是，返回true,否则返回false
    i=0;
    j=k=0;  //i为下标，j和k分别为字母I和O的个数
    while (A[i]!='\0') {    //未到字符数组尾
        switch(A[i]){
            case 'I' ; j++; break;  //入栈次数增 1
            case 'O' : k++;
                    if (k>j ) { printf ("序列非法\n") ; exit (0) ; }
        }
        i++;  //不论A[i]是“I”或“0”，指针i均后移
    }    //while
    if (j!=k) {
        printf ("序列非法\n" );
        return false;
    }else{
        printf ("序列合法\n");
        return true;
    }
}

另解：入栈后，栈内元素个数加1；出栈后，栈内元素个数减1，因此，可以将判定一组出入栈序列是否合法，转化为一组+1、-1组成的序列，它的任意前缀子序列的累加和不小于0 (每次出栈或入栈操作后判断)，则合法；否则，非法。