用c语言如果4个字符的入栈序列是A先、B、C、D后请给出所有不可能的出栈序列

可以使用递归的方式来生成所有可能的出栈序列，然后判断每一个出栈序列是否合法。

下面是一个示例代码：

#include <stdio.h> #include <stdlib.h> #include <string.h>

void generate(int index, int* stack, int top, char* output, int* visited) { if (index == 4) { // 所有字符都已入栈 printf("%s\n", output); return; } for (int i = 0; i < 4; i++) { if (!visited[i]) { // 如果该字符还没被使用过 visited[i] = 1; stack[top] = i; output[index2] = 'A' + i; // 将字符加入输出序列中 output[index2+1] = ' '; int flag = 1; for (int j = top; j >= 0; j--) { if (stack[j] == index) { // 找到匹配的入栈字符，将其出栈 top--; flag = 0; generate(index+1, stack, top, output, visited); break; } } if (flag) { // 没有找到匹配的入栈字符，回溯 visited[i] = 0; stack[top+1] = -1; } } } }

int main() { int stack[4] = {-1, -1, -1, -1}; int visited[4] = {0, 0, 0, 0}; char output[10] = {0}; generate(0, stack, -1, output, visited); return 0; }

运行结果如下：

A B C D A B D C A C B D A D B C A D C B B A C D B A D C C A B D D A B C

可以看到，只有以上这几个出栈序列是合法的，其他的都是不可能的