判断出栈入栈序列的合法性
问题描述:
假设以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 (每次出栈或入栈操作后判断),则合法;否则,非法。