筆試題：C語言使用順序棧判斷字符串中的括號有效性

一、背景介紹

通過鍵盤輸入一個包括 '(' 和 ')' 的字符串string ，判斷字符串是否有效。要求設計算法實現檢查字符串是否有效，有效的字符串需滿足以下條件：
A. 左括號必須用相同類型的右括號閉合。
B. 左括號必須以正確的順序閉合。
C. 每個右括號都有一個對應的相同類型的左括號。

我們可以利用 順序棧（Sequence Stack）來解決這個問題，因為棧結構可以有效地跟蹤括號的匹配關系。順序棧是一個靜態實現的棧數據結構，它通過數組實現棧的各項操作，具有較高的時間和空間效率。

本文將介紹如何使用順序棧來判斷括號是否有效，以下是解決該問題的詳細步驟。

二、算法設計

解決括號匹配問題的基本思路如下：

入棧操作：
- 當遇到左括號 ( 時，將其壓入棧中。
出棧操作：
- 當遇到右括號 ) 時，從棧中彈出棧頂元素。
- 如果棧為空，表示沒有對應的左括號，返回無效。
- 如果彈出的棧頂元素是左括號 (，繼續判斷下一個字符。
結束后檢查棧是否為空：
- 如果棧不為空，說明有未匹配的左括號，返回無效。
- 如果棧為空，表示所有括號均有效，返回有效。

版本：

/**
 * @file name : SeqenceIsStrVaild.c
 * @brief     : 通過鍵盤輸入一個包括 '(' 和 ')' 的字符串string ，判斷字符串是否有效。要求設計算法實現檢查字符串是否有效，有效的字符串需滿足以下條件：
A. 左括號必須用相同類型的右括號閉合。
B. 左括號必須以正確的順序閉合。
C. 每個右括號都有一個對應的相同類型的左括號。
 * @author    : qrshxc@163.com
 * @date      : 2025/04/26
 * @version   : 1.0
 * @note      : 
 * CopyRight (c)  2025-2026   qrshxc@163.com   All Right Reseverd
 */

三、順序棧的實現

順序棧是一種通過數組實現的棧數據結構，通常需要維護三個基本操作：入棧、出棧、檢查棧是否為空。

1. 順序棧的定義

我們首先定義順序棧的結構體 SeqStack_t，包括棧底指針、棧容量和棧頂指針。

c復制編輯typedef char DataType_t; // 棧數據類型

// 順序棧結構體定義
typedef struct SequenceStack
{
    DataType_t *bottom;  // 記錄順序棧棧底地址
    unsigned int size;   // 記錄順序棧棧容量大小
    int top;             // 記錄順序棧棧頂元素的下標
} SeqStack_t;

2. 順序棧的基本操作

順序棧的基本操作包括：棧創建、入棧、出棧、判斷棧是否為空。

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

// 順序棧的數據類型
typedef char DataType_t;

// 順序棧的結構體定義
typedef struct SequenceStack
{
    DataType_t *bottom;  // 記錄順序棧棧底地址
    unsigned int size;   // 記錄順序棧棧容量大小
    int top;             // 記錄順序棧棧頂元素的下標
} SeqStack_t;

/**
 * @name      SeqStack_create
 * @brief     創建順序棧并對順序棧進行初始化
 * @param     size 順序棧的大小
 * @return
 *      @retval    manager 順序棧的管理結構體
 * @date      2025/04/24
 * @version   1.0
 * @note      Manager->Addr  --->  [Size*sizeof(DataType_t)]
 */
SeqStack_t *SeqStack_create(unsigned size)
{
    // 1. 利用 calloc 為棧的管理結構體分配內存
    SeqStack_t *manager = (SeqStack_t *)calloc(1, sizeof(SeqStack_t));
    // 錯誤處理：如果內存分配失敗
    if (manager == NULL) {
        perror("calloc memory for manager failed!");
        exit(-1); // 程序異常終止
    }

    // 2. 利用 calloc 為棧底（數組）分配內存
    manager->bottom = (DataType_t *)calloc(size, sizeof(DataType_t));
    // 錯誤處理：如果內存分配失敗
    if (manager->bottom == NULL) {
        perror("calloc memory for bottom failed!");
        free(manager);
        exit(-1);
    }

    // 3. 初始化棧的容量和棧頂指針
    manager->size = size;
    manager->top = -1; // 棧頂指針初始化為 -1，表示棧為空

    return manager;
}

/**
 * @name      SeqStack_IsFull
 * @brief     判斷順序棧是否已滿
 * @param     manager 順序棧的管理結構體
 * @return
 *      @retval true 棧已滿
 *      @retval false 棧未滿
 * @date      2025/04/24
 * @version   1.0
 * @note      判斷棧的棧頂是否已經達到了棧的容量
 */
bool SeqStack_IsFull(SeqStack_t *manager)
{
    // 如果棧頂元素的下標等于棧的容量減1，說明棧已滿
    return manager->top + 1 == manager->size ? true : false;
}

/**
 * @name      SeqStack_Push
 * @brief     入棧
 * @param     data 插入的元素
 * @return
 *      @retval true 入棧成功
 *      @retval false 入棧失敗
 * @date      2025/04/24
 * @version   1.0
 * @note      判斷棧是否已滿，如果沒滿則將數據壓入棧頂
 */
bool SeqStack_Push(SeqStack_t *manager, DataType_t data)
{
    // 判斷順序棧是否已滿
    if (SeqStack_IsFull(manager)) {
        printf("SequenceStack is full!\n");
        return false;
    }
    // 如果棧未滿，則將數據壓入棧頂
    manager->bottom[++manager->top] = data;
    return true;
}

/**
 * @name      SeqStack_IsEmpty
 * @brief     判斷順序棧是否為空
 * @param     manager 順序棧的管理結構體
 * @return
 *      @retval true 棧為空
 *      @retval false 棧不為空
 * @date      2025/04/24
 * @version   1.0
 * @note      判斷棧的棧頂指針是否為 -1，表示棧為空
 */
bool SeqStack_IsEmpty(SeqStack_t *manager)
{
    return (manager->top == -1) ? true : false;
}

/**
 * @name      SeqStack_Pop
 * @brief     出棧
 * @param     manager 順序棧的管理結構體
 * @return
 *      @retval temp 出棧的值
 * @date      2025/04/24
 * @version   1.0
 * @note      判斷棧是否為空，如果棧不為空，則彈出棧頂元素
 */
DataType_t SeqStack_Pop(SeqStack_t *manager)
{
    DataType_t temp = 0; // 用于存儲出棧的元素

    // 判斷順序棧是否為空
    if (SeqStack_IsEmpty(manager)) {
        printf("SequenceStack is empty!\n");
        return -1; // ?？諘r返回特殊錯誤值
    }

    // 彈出棧頂元素并更新棧頂指針
    temp = manager->bottom[manager->top--];
    return temp;
}

/**
 * @name      SeqStack_IsStrVaild
 * @brief     判斷字符串中的括號是否有效，支持小括號 '(' 和 ')'
 * @param     manager 順序棧的管理結構體
 * @param     str 待檢查的字符串
 * @return
 *      @retval true 字符串有效
 *      @retval false 字符串無效
 * @date      2025/04/24
 * @version   1.0
 * @note      遍歷字符串，遇到左括號壓棧，遇到右括號彈棧，判斷括號是否匹配
 */
bool SeqStack_IsStrVaild(SeqStack_t *manager, const char *str)
{
    char *pstr = (char *)str; // 備份str地址

    // 遍歷字符串中的每個字符
    while (*pstr != '\0') {
        if (*pstr == '(') {  // 如果是左括號 '(', 入棧
            SeqStack_Push(manager, '(');
        } else if (*pstr == ')') {  // 如果是右括號 ')', 出棧
            if (SeqStack_IsEmpty(manager)) {  // 判斷棧是否為空
                return false;  // ?？諘r，表示沒有左括號匹配
            }
            SeqStack_Pop(manager);  // 彈出棧頂元素（左括號）
        }
        pstr++;  // 移動到下一個字符
    }

    // 如果棧不為空，表示有未匹配的左括號
    return SeqStack_IsEmpty(manager);
}

/**
 * @name      SeqStack_Print
 * @brief     從頭到尾遍歷順序棧的元素
 * @param     manager 順序棧的管理結構體
 * @return
 *      @retval    
 * @date      2025/04/24
 * @version   1.0
 * @note      遍歷棧中的元素并打印
 */
void SeqStack_Print(SeqStack_t *manager)
{
    for (int i = 0; i <= manager->top; ++i) {
        printf("Stack Element[%d] = %d\n", i, manager->bottom[i]);  // 打印順序棧單元數據
    }
}

int main(int argc, char const *argv[])
{
    // 創建一個順序棧，棧大小為5
    SeqStack_t *stack = SeqStack_create(5);

    // 測試用例 1
    const char *str1 = "(())";
    if (SeqStack_IsStrVaild(stack, str1)) {
        printf("字符串 \"%s\" 是有效的。\n", str1);
    } else {
        printf("字符串 \"%s\" 是無效的。\n", str1);
    }

    // 測試用例 2
    const char *str2 = "(()";
    if (SeqStack_IsStrVaild(stack, str2)) {
        printf("字符串 \"%s\" 是有效的。\n", str2);
    } else {
        printf("字符串 \"%s\" 是無效的。\n", str2);
    }

    // 清理棧的內存
    free(stack->bottom); // 釋放棧底的內存
    free(stack); // 釋放棧的管理結構體內存

    return 0;
}

3. 判斷括號是否有效

使用順序棧來檢查括號是否匹配有效，我們在遍歷字符串的過程中，遇到左括號時壓棧，遇到右括號時彈棧。

c復制編輯// 判斷括號匹配是否有效
bool SeqStack_IsStrVaild(SeqStack_t *manager, const char *str)
{
    const char *pstr = str;
    while (*pstr != '\0') {
        if (*pstr == '(') {
            SeqStack_Push(manager, '(');  // 左括號入棧
        } else if (*pstr == ')') {
            if (SeqStack_IsEmpty(manager)) {
                return false;  // 棧空時表示沒有左括號匹配
            }
            SeqStack_Pop(manager);  // 彈出棧頂元素（左括號）
        }
        pstr++;
    }

    // 如果棧不為空，表示有未匹配的左括號
    return SeqStack_IsEmpty(manager);
}

四、測試用例

接下來，我們通過幾個測試用例來驗證我們的實現。

c復制編輯int main()
{
    SeqStack_t *stack = SeqStack_create(100);  // 創建棧，容量為100

    // 測試用例 1
    const char *str1 = "(())";
    if (SeqStack_IsStrVaild(stack, str1)) {
        printf("字符串 \"%s\" 是有效的。\n", str1);
    } else {
        printf("字符串 \"%s\" 是無效的。\n", str1);
    }

    // 測試用例 2
    const char *str2 = "(()";
    if (SeqStack_IsStrVaild(stack, str2)) {
        printf("字符串 \"%s\" 是有效的。\n", str2);
    } else {
        printf("字符串 \"%s\" 是無效的。\n", str2);
    }

測試結果：

測試用例 1：(()) 輸出：字符串 "(())" 是有效的。
測試用例 2：(() 輸出：字符串 "(()" 是無效的。

字符串 "(())" 是有效的。
字符串 "(()" 是無效的。

五、總結

通過使用順序棧，我們能夠高效地判斷一個字符串中的括號是否有效。棧的先進后出（LIFO）特性使得我們能夠從棧中彈出并檢查每個左括號是否匹配相應的右括號。該方法可以擴展到更復雜的括號類型（如 {} 和 []），并適用于其他類似的匹配問題。

本文通過順序棧的實現展示了如何處理括號匹配問題，希望對你有所幫助。

posted @ 2025-04-28 16:45 九思0404 閱讀(26) 評論(0) 收藏舉報

刷新頁面返回頂部

qrshxc