假设以I和O分别表示入栈和出栈操作 栈的初态和终态均为空。入栈和出栈的操作序列表示为仅由I和O组
序列,表示,操作
已帮助 人
假设以I和O分别表示入栈和出栈操作，栈的初态和终态均为空。入栈和出栈的操作序列表示为仅由I和O组成的序列。 "(1)下面所示的序列中哪些是合法的？(2分) A.IOIIOIOO B.IOOIOIIO C.IIIOIOIO D.IIIOOIOO" (2)通过对(1)的分析，给出判断一个给定序列是否合法的算法思想。 (4分)【哈尔滨工业大学2005四、2(6分)】【武汉大学2000五、2(12分)】
请帮忙给出正确答案和分析，谢谢！
-
正确答案：(1)A和D是合法的。(2)设立一个字符栈从左到右对IO序列做如下处理。遇I就入栈遇O就出栈。若遇O出栈前栈空则序列不合法退出算法。若序列处理完但是栈不空序列不合法。只有序列处理完且栈空序列才是合法序列。
(1)A和D是合法的。(2)设立一个字符栈,从左到右对IO序列做如下处理。遇I就入栈,遇O就出栈。若遇O出栈前栈空,则序列不合法,退出算法。若序列处理完但是栈不空,序列不合法。只有序列处理完且栈空,序列才是合法序列。