C 語言鏈棧實現：進制轉換與字符匹配完整方案

題目需求

基於鏈式棧結構，實現任意進制轉換（如十進制轉二進制、八進制、十六進制）及字符匹配（如括號匹配）功能。

鏈棧核心代碼完善

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

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef char ElemType; // 通用元素類型

typedef struct StackNode {
    ElemType data;
    struct StackNode *next;
} StackNode, *LinkStackPtr;

typedef struct {
    LinkStackPtr top;
    int count;
} LinkStack;

// 初始化
Status InitStack(LinkStack *S) {
    S->top = NULL;
    S->count = 0;
    return OK;
}

// 入棧
Status Push(LinkStack *S, ElemType e) {
    LinkStackPtr p = (LinkStackPtr)malloc(sizeof(StackNode));
    if (!p) return ERROR;
    p->data = e;
    p->next = S->top;
    S->top = p;
    S->count++;
    return OK;
}

// 出棧
Status Pop(LinkStack *S, ElemType *e) {
    if (S->top == NULL) return ERROR;
    LinkStackPtr p = S->top;
    *e = p->data;
    S->top = p->next;
    free(p);
    S->count--;
    return OK;
}

// 獲取棧頂
Status GetTop(LinkStack S, ElemType *e) {
    if (S.top == NULL) return ERROR;
    *e = S.top->data;
    return OK;
}

// 判空
Status StackEmpty(LinkStack S) {
    return S.top == NULL ? TRUE : FALSE;
}

功能一：任意進制轉換（十進制轉 N 進制）

void ConvertBase(long num, int base) {
    LinkStack S;
    InitStack(&S);
    char digits[] = "0123456789ABCDEF";
    
    if (num == 0) {
        printf("0");
        return;
    }
    
    while (num > 0) {
        Push(&S, digits[num % base]);
        num /= base;
    }
    
    ElemType e;
    while (!StackEmpty(S)) {
        Pop(&S, &e);
        printf("%c", e);
    }
    printf("\n");
}

功能二：括號匹配檢測

Status BracketMatch(char *exp) {
    LinkStack S;
    InitStack(&S);
    ElemType ch, topElem;
    
    for (int i = 0; exp[i] != '\0'; i++) {
        ch = exp[i];
        switch (ch) {
            case '(':
            case '[':
            case '{':
                Push(&S, ch);
                break;
            case ')':
                if (StackEmpty(S) || (Pop(&S, &topElem), topElem != '(')) return FALSE;
                break;
            case ']':
                if (StackEmpty(S) || (Pop(&S, &topElem), topElem != '[')) return FALSE;
                break;
            case '}':
                if (StackEmpty(S) || (Pop(&S, &topElem), topElem != '{')) return FALSE;
                break;
        }
    }
    return StackEmpty(S) ? TRUE : FALSE;
}

主函數測試

int main() {
    // 1. 進制轉換測試
    printf("123 轉二進制: "); ConvertBase(123, 2);
    printf("123 轉八進制: "); ConvertBase(123, 8);
    printf("123 轉十六進制: "); ConvertBase(123, 16);
    
    // 2. 括號匹配測試
    char *exp1 = "{[()()]}";
    char *exp2 = "{[(])}";
    printf("%s %s\n", exp1, BracketMatch(exp1) ? "匹配" : "不匹配");
    printf("%s %s\n", exp2, BracketMatch(exp2) ? "匹配" : "不匹配");
    
    return 0;
}

關鍵點總結

• 棧的後進先出（LIFO）特性天然適配「逆序輸出」（進制轉換）和「最近配對」（括號匹配）。
• 鏈式存儲無大小限制，適合未知數據量場景。
• 模塊化設計：將棧操作封裝為獨立 ADT，業務邏輯調用接口，降低耦合。

擴展方向

• 表達式求值（中綴轉後綴 + 棧計算）。
• 迷宮求路（回溯法配合棧記錄路徑）。
• 遞歸算法的非遞歸實現（如漢諾塔、深度優先搜索）。