求助

小甲鱼的二师兄

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. 
   
4. /* 辅助函数：打印栈内容，形如 [1, 3, 4]（自底向顶） */
   
5. static void print_stack(const int *st, int top) {
   
6.     putchar('[');
   
7.     for (int i = 0; i <= top; ++i) {
   
8.         if (i) printf(", ");
   
9.         printf("%d", st[i]);
   
10.     }
    
11.     putchar(']');
    
12. }
    
13. 
    
14. /* 核心模拟：当 print_ops=1 时打印过程，=0 时仅判断合法性 */
    
15. static int simulate_and_maybe_print(const int *b, int n, int print_ops) {
    
16.     int *st = (int *)malloc(sizeof(int) * (n > 0 ? n : 1));
    
17.     if (!st) {
    
18.         fprintf(stderr, "内存分配失败\n");
    
19.         exit(1);
    
20.     }
    
21. 
    
22.     int top = -1;       // 栈顶指针，-1 表示空
    
23.     int nextPush = 1;   // 下一个要入栈的数（1..n）
    
24. 
    
25.     for (int i = 0; i < n; ++i) {
    
26.         int target = b[i];
    
27. 
    
28.         // 不断入栈，直到栈顶等于 target 或者所有元素都已入栈
    
29.         while (nextPush <= n && (top == -1 || st[top] != target)) {
    
30.             st[++top] = nextPush;
    
31.             if (print_ops) {
    
32.                 printf("入栈 %d | 栈=", nextPush);
    
33.                 print_stack(st, top);
    
34.                 putchar('\n');
    
35.             }
    
36.             ++nextPush;
    
37.         }
    
38. 
    
39.         // 若此时栈顶是 target，则弹出；否则无法实现
    
40.         if (top != -1 && st[top] == target) {
    
41.             --top;
    
42.             if (print_ops) {
    
43.                 printf("出栈 -> %d | 栈=", target);
    
44.                 print_stack(st, top);
    
45.                 putchar('\n');
    
46.             }
    
47.         } else {
    
48.             free(st);
    
49.             return 0; // 非法
    
50.         }
    
51.     }
    
52. 
    
53.     free(st);
    
54.     return 1; // 合法
    
55. }
    
56. 
    
57. int main(void) {
    
58.     int n;
    
59.     if (scanf("%d", &n) != 1) return 0;
    
60.     if (n < 0) return 0;
    
61. 
    
62.     int *b = (int *)malloc(sizeof(int) * (n > 0 ? n : 1));
    
63.     if (!b) {
    
64.         fprintf(stderr, "内存分配失败\n");
    
65.         return 1;
    
66.     }
    
67. 
    
68.     for (int i = 0; i < n; ++i) {
    
69.         if (scanf("%d", &b[i]) != 1) {
    
70.             free(b);
    
71.             return 0;
    
72.         }
    
73.     }
    
74. 
    
75.     // 先仅判定合法性
    
76.     int ok = simulate_and_maybe_print(b, n, 0);
    
77. 
    
78.     if (!ok) {
    
79.         printf("否：该 b 序列不是以 1..n 为进栈序列的合法出栈序列。\n");
    
80.     } else {
    
81.         printf("是：该 b 序列可以由进栈序列 1..n 通过单栈操作得到。\n");
    
82.         printf("操作过程：\n");
    
83.         // 再次模拟，并打印全过程
    
84.         simulate_and_maybe_print(b, n, 1);
    
85.     }
    
86. 
    
87.     free(b);
    
88.     return 0;
    
89. }

复制代码