问答题假设以S和X分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S和X组成的序列表示(如SXSX)。(1)试指出判别给定序列是否合法的一般规则。(2)两个不同合法序列(对同一输入序列)能否得到相同的输出元素序列?如能得到，请举列说明。【东南大学1992二(10分)】

【正确答案】正确答案：(1)通常有两条规则。第一是给定序列中S的个数和X的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S的个数要大于或等于X的个数。(2)可以得到相同的输出元素序列。例如，输入元素为A，B，C，则两个输入的合法序列ABC和BAC均可得到输出元素序列ABC。对于合法序列ABC，我们使用本题约定的SXSXSX操作序列；对于合法序列BAC，我们使用SSXXSX操作序列。

【答案解析】