用 C 语言找出不可能的出栈序列

可以使用递归的方式实现，对于每个字符，有两种情况：入栈或出栈。因此，可以用一个数组记录每个字符的状态（入栈或出栈），然后递归尝试所有可能的状态组合，找出不可能的出栈序列。

具体实现如下：

#include <stdio.h>

#define MAX_SIZE 10

int stack[MAX_SIZE]; // 栈
int top = -1; // 栈顶指针

void push(int x) { // 入栈
    stack[++top] = x;
}

int pop() { // 出栈
    return stack[top--];
}

int is_possible(int n, int *state, int *output, int k) {
    if (k == n) { // 如果所有字符都处理完了，检查输出序列是否合法
        int i, j;
        int temp[MAX_SIZE]; // 临时栈，用于检查输出序列是否合法
        int top_temp = -1; // 临时栈顶指针
        for (i = 0, j = 0; i < n; i++) {
            if (state[i] == 0) { // 如果是入栈状态，将字符入栈
                temp[++top_temp] = output[j++];
            } else { // 如果是出栈状态，检查栈顶元素是否等于当前字符，如果不等于则输出序列不合法
                if (top_temp < 0 || temp[top_temp--] != output[j++]) {
                    return 0;
                }
            }
        }
        return 1; // 输出序列合法
    }
    state[k] = 0; // 将当前字符设置为入栈状态
    if (is_possible(n, state, output, k + 1)) { // 递归处理下一个字符
        return 1; // 如果后面的字符都可以输出，则当前状态合法
    }
    state[k] = 1; // 将当前字符设置为出栈状态
    if (is_possible(n, state, output, k + 1)) { // 递归处理下一个字符
        return 1; // 如果后面的字符都可以输出，则当前状态合法
    }
    return 0; // 如果所有状态都不合法，则当前状态不合法
}

int main() {
    int n = 4; // 字符个数
    char input[] = 'ABCD'; // 入栈序列
    int output[] = {4, 3, 2, 1}; // 不可能的出栈序列
    int state[MAX_SIZE] = {0}; // 入栈出栈状态数组
    int i;
    printf('不可能的出栈序列：\n');
    do {
        for (i = 0; i < n; i++) {
            if (state[i] == 0) { // 如果是入栈状态，将字符入栈
                push(input[i]);
            } else { // 如果是出栈状态，将栈顶元素出栈，并与当前字符比较
                int x = pop();
                if (x != output[i]) { // 如果不相等，则说明当前状态不合法，退出循环
                    break;
                }
            }
        }
        if (i == n) { // 如果所有字符都处理完了，且栈为空，则说明当前状态合法
            printf('%d %d %d %d\n', output[0], output[1], output[2], output[3]);
        }
    } while (next_permutation(output, output + n)); // 生成下一个排列
    return 0;
}

输出结果为：