C語言數據結構實戰：棧實現程序符號匹配檢測（編譯器前端核心邏輯）

問題背景

編譯器前端需檢查源代碼中成對符號（() [] {} <> '' ""）是否正確匹配。利用棧的後進先出特性，可線性掃描一次完成檢測。

算法流程

1. 逐字符掃描源代碼字符串。
2. 遇到左符號（( [ { < ' "）壓棧。
3. 遇到右符號（) ] } > ' "）彈棧頂，比對是否匹配：
   　　- 棧空或不匹配 → 報錯位置。
   　　- 匹配 → 繼續掃描。
4. 掃描結束：棧為空且無錯誤 → 編譯成功；否報錯（遺漏右符號）。

代碼實現（鏈式棧）

輔助函數

int isLeft(char c) { 
    return c=='('||c=='['||c=='{'||c=='<'||c=='\''||c=='\"'; 
} 
int isRight(char c) { 
    return c==')'||c==']'||c=='}'||c=='>'||c=='\''||c=='\"'; 
} 
int match(char left, char right) { 
    return (left=='(' && right==')') || 
           (left=='[' && right==']') || 
           (left=='{' && right=='}') || 
           (left=='<' && right=='>') || 
           (left=='\'' && right=='\'') || 
           (left=='\"' && right=='\"'); 
}

主檢測邏輯

int scan(const char* code) { 
    LinkStack* st = LinkStack_Create(); 
    int i = 0; 
    while (code[i] != '\0') { 
        if (isLeft(code[i])) { 
            LinkStack_Push(st, (void*)(code + i)); // 壓入字符地址 
        } else if (isRight(code[i])) { 
            char* top = (char*)LinkStack_Pop(st); 
            if (!top || !match(*top, code[i])) { 
                printf("Mismatch at pos %d: '%c'\n", i, code[i]); 
                LinkStack_Destroy(st); 
                return 0; 
            } 
        } 
        ++i; 
    } 
    if (LinkStack_Top(st) == NULL) { 
        puts("編譯成功：所有符號匹配"); 
    } else { 
        puts("錯誤：存在未閉合的左符號"); 
    } 
    LinkStack_Destroy(st); 
    return 1; 
}

測試用例

int main() { 
    const char* code = 
        "#include <stdio.h> " 
        "int main() { " 
        "    int a[5][5]; " 
        "    int (*p)[5] = a; " 
        "    printf(\"%d\", &a[3][3] - &p[3][3]); " 
        "} "; 
    scan(code); 
    return 0; 
}

鏈式棧核心操作（復用單向鏈表）

typedef struct Node { void* data; struct Node* next; } Node; 
typedef struct { Node* top; int size; } LinkStack; 

LinkStack* LinkStack_Create() { 
    LinkStack* s = (LinkStack*)malloc(sizeof(LinkStack)); 
    s->top = NULL; s->size = 0; return s; 
} 
void LinkStack_Push(LinkStack* s, void* val) { 
    Node* n = (Node*)malloc(sizeof(Node)); 
    n->data = val; n->next = s->top; s->top = n; s->size++; 
} 
void* LinkStack_Pop(LinkStack* s) { 
    if (!s->top) return NULL; 
    Node* n = s->top; void* val = n->data; 
    s->top = n->next; free(n); s->size--; return val; 
} 
void* LinkStack_Top(LinkStack* s) { return s->top ? s->top->data : NULL; } 
void LinkStack_Destroy(LinkStack* s) { 
    while (s->top) LinkStack_Pop(s); free(s); 
}

避坑指南

• 字符串字面量中的轉義字符（\"、\'）需正確處理，掃描時視為單字符。
• 註釋、字符串常量內的括號應忽略（本簡化版未處理，完整編譯器需詞法分析配合）。
• 壓棧存儲字符地址而非字符值，利用鏈式棧 void* 通用性，避免拷貝開銷。

總結

棧是處理巢狀結構匹配的天然數據結構，本例演示了編譯器詞法/語法分析階段的核心邏輯之一。擴展方向：支持多行、錯誤恢復、語法高亮等。本文出自 CSDN 博客「yygydjkthh」系列。