您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> C 語言問答

經典C語言練習：棧應用、數字變換與排列組合問題詳解

編輯：C 語言問答

前言

在C語言學習過程中，棧（Stack）作為核心數據結構，其應用場景極廣。本文將深入剖析三道經典的C語言練習題，涵蓋代數表達式合法性驗證、數字變換生成計數、以及棧排列組合總數計算，幫助讀者掌握棧的實戰技巧與遞歸、動態規劃等核心算法思想。

一、基於棧的代數表達式合法性驗證

問題描述

輸入一個以 '#' 結尾的字符串，判斷其是否為合法的代數表達式。合法表達式需滿足：運算元為單字母，運算符為 + - * /，括號可為 ()、[]、{} 且必須配對，且不允許出現非法字符（如連續字母 "ab" 或未定義變量 "d"）。

核心邏輯與實現

採用棧結構處理括號匹配，同時建立狀態機驗證語法規則：

字符合法性檢查：遍歷字符串，若出現非字母、非運算符、非括號、非結束符 '#' 的字符，報錯類型 ①。
括號匹配：遇到左括號入棧，遇到右括號檢查棧頂是否為對應左括號，不匹配或棧為空則報錯類型 ②；遍歷結束棧非空亦報錯 ②。
語法結構驗證：維護「期待運算元」或「期待運算符」狀態。表達式開始及左括號後、運算符後期待運算元；運算元後、右括號後期待運算符或右括號/結束符。狀態轉移違規報錯類型 ③。

代碼框架示例

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

#define MAX_LEN 100

typedef struct { char data[MAX_LEN]; int top; } Stack;

void init(Stack *s) { s->top = -1; }
int empty(Stack *s) { return s->top == -1; }
void push(Stack *s, char c) { s->data[++(s->top)] = c; }
char pop(Stack *s) { return s->data[(s->top)--]; }
char top(Stack *s) { return s->data[s->top]; }

int is_match(char l, char r) {
    return (l=='(' && r==')') || (l=='[' && r==']') || (l=='{' && r=='}');
}

int main() {
    char expr[MAX_LEN];
    fgets(expr, MAX_LEN, stdin);
    // 移除換行符並補全結束符處理邏輯
    // ... 實現上述狀態機與棧邏輯 ...
    return 0;
}

二、數字變換規則下的生成數計數

問題描述

給定一個大整數 n (n < 10^30) 和 k 條變換規則 (k ≤ 15)，規則形如 "x → y" 表示數字 x 可替換為 y (y ≠ 0)。從原始數字出發，任意應用規則 0 次或多次，求能生成多少個不同的整數。

解題思路：圖論與連通分量

將 0-9 十個數字視為圖的節點，規則 "x → y" 視為有向邊。由於規則可重複應用，問題轉化為：從原數字每一位出發，在有向圖中可達到的節點集合。各位數字變換相互獨立，總生成數為各位可達節點數的乘積。

算法步驟

構建鄰接表表示有向圖。
對每個數字 0-9，用 DFS/BFS 或 Floyd-Warshall 算法計算其可達節點集合（含自身）。
將大整數 n 作為字符串處理，對每一位字符 c，查找其可達集合大小 size[c]。
結果為所有 size[c] 的乘積（注意大整數乘法，可用高精度或輸出為字符串）。

關鍵代碼片段

// 假設 reachable[d][v] 表示數字 d 能否到達 v
// 使用 Floyd-Warshall 計算傳遞閉包
for (int k = 0; k < 10; ++k)
    for (int i = 0; i < 10; ++i)
        for (int j = 0; j < 10; ++j)
            reachable[i][j] |= reachable[i][k] && reachable[k][j];

// 統計各位可選數
long long count[10] = {0};
for (int d = 0; d < 10; ++d)
    for (int v = 0; v < 10; ++v)
        if (reachable[d][v]) count[d]++;

// 高精度乘法計算總數
// ... 實現大整數乘法 ...

三、棧排列組合總數：卡特蘭數應用

問題描述

輸入序列 1, 2, ..., n (n ≤ 18)，通過棧的 push/pop 操作生成輸出序列。求所有可能的輸出序列總數。

數學模型

這是經典的棧排列問題，其解為第 n 個卡特蘭數：

C_n = (1/(n+1)) * C(2n, n) = (2n)! / ((n+1)! n!)

遞歸關係：C₀=1, C_n+1 = Σ_i=0..n C_iC_n-i。

高精度計算實現

n=18 時 C₁₈ = 477638700，超過 32 位整數範圍，需用 64 位長整型或高精度。動態規劃預計算前 18 項：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    // 使用 unsigned long long 足夠存儲 C_18
    unsigned long long cat[19] = {1};
    for (int i = 1; i <= n; ++i) {
        cat[i] = 0;
        for (int j = 0; j < i; ++j)
            cat[i] += cat[j] * cat[i-1-j];
    }
    printf("%llu\n", cat[n]);
    return 0;
}