廣義表創建與打印完整實現：C語言遞歸解析S表達式

廣義表創建與打印完整實現：C語言遞歸解析S表達式

廣義表定義

廣義表是線性表的推廣，元素可以是原子或子表。表示法：(a, (b, c), d)。
節點結構採用「標識域 + 聯合體」：

typedef enum { ATOM, LIST } ElemTag;
typedef struct GLNode {
    ElemTag tag;                 // 0=原子, 1=子表
    union { char atom; struct GLNode *hp; }; // 原子值 / 子表頭指針
    struct GLNode *tp;           // 尾指針（指向下一個元素）
} GList;

核心難點：提取子串 Getsubs

輸入字串去掉最外層括號後為 Subs，需按頂層逗號分割：
Subs = "S1, S2, ..., Sn" → 依次取出 hstr = S1，剩餘 Subs = "S2, ..., Sn"。
關鍵：遇逗號時括號深度為 0才真正分割。

void Getsubs(char str[], char hstr[]) {
    int i=0, j=0, k=0; // k = 未匹配左括號數
    while (str[i] && (str[i]!=',' || k)) {
        if (str[i]=='(') k++;
        else if (str[i]==')') k--;
        if (str[i]!=',' || k) { hstr[j++] = str[i++]; }
    }
    hstr[j] = '\0';
    if (str[i]==',') i++;
    // 將 str 移至剩餘部分
    int r=0; while (str[i]) str[r++] = str[i++]; str[r]='\0';
}

遞歸創建 GListCreate

GList *GListCreate(char str[]) {
    GList *G;
    if (!strlen(str) || !strcmp(str, "()")) return NULL; // 空表
    if (strlen(str) == 1) { // 原子
        G = (GList*)malloc(sizeof(GList));
        G->tag = ATOM; G->atom = *str; G->tp = NULL; return G;
    }
    // 子表：去掉外層 ()
    G = (GList*)malloc(sizeof(GList));
    G->tag = LIST;
    char subs[100], hstr[100];
    strncpy(subs, str+1, strlen(str)-2); subs[strlen(str)-2] = '\0';
    GList *p = G, *q;
    while (strlen(subs)) {
        Getsubs(subs, hstr);
        GList *r = GListCreate(hstr); // 遞歸建子表/原子
        p->hp = r;
        q = p;
        if (strlen(subs)) {
            p = (GList*)malloc(sizeof(GList));
            p->tag = LIST;
            q->tp = p;
        }
    }
    q->tp = NULL;
    return G;
}

遞歸打印 GListPrint

void GListPrint(GList *G) {
    printf("(");
    while (G) {
        GList *p = G->hp, *q = G->tp;
        if (p && !p->tag && q) { printf("%c,", p->atom); G = q; }
        else if (p && !p->tag) { printf("%c", p->atom); break; }
        else {
            if (!p) printf("()");
            else GListPrint(p);
            if (q) printf(",");
            G = q;
        }
    }
    printf(")");
}

測試驗證

輸入： (a,(b,c),d)
輸出： (a,(b,c),d)

程式正確處理巢狀子表、空表 ()、單原子等情況。

編譯與運行

gcc -o glist glist.c
./glist
# 輸入字元數: 9
# 輸入廣義表: (a,(b,c),d)

總結

廣義表是理解遞歸數據結構、解析器設計的經典模型。掌握 Getsubs 分割邏輯與「頭尾指針」鏈表結構，可擴展至 Lisp 風格語言解析、XML/JSON 簡易解析器等。