c語言棧實作括号比對

在文字處理軟體或編譯程式設計時，常常需要檢查一個字元串或一個表達式中的括号是否相比對?

比對思想：從左至右掃描一個字元串(或表達式)，則每個右括号将與最近遇到的那個左括号相比對。則可以在從左至右掃描過程中把所遇到的左括号存放到堆棧中。每當遇到一個右括号時，就将它與棧頂的左括号(如果存在)相比對，同時從棧頂删除該左括号。

算法思想：設定一個棧，當讀到左括号時，左括号進棧。當讀到右括号時，則從棧中彈出一個元素，與讀到的左括号進行比對，若比對成功，繼續讀入；否則比對失敗，傳回FLASE。另外,在算法的開始和結束時,棧都應該是空的.是以比對到最後還要判斷棧是否為空,若非空,則說明比對失敗.

代碼實作:

采用前面的順序棧結構來實作此題.

#include"sp_stack.c"


/* 輸入括号比對,其他字元不比對
 * 以空格結束輸入
 * 比對錯誤時直接退出
 * 比對成功,傳回true
 * 否則傳回false
*/

int match(char input[])
{
    char ch;
    char *str;
    int result,i = ;
    scanf("%c",&ch);
    /* 建立一個空棧 */
    sp_stack s = (sp_stack)malloc(sizeof(stack));
    s = stack_init(s);
    while(ch != ' ')
    {
        input[i++] = ch;
        /* 判斷輸入字元是否為括号{}, (), [] */
        if ( (ch == '{') || (ch == '(') || (ch == '['))
        {
            push(s, ch);
            get_top(s, str);
        }
        if (ch == '}' || ch == ']' || ch == ')')
        {
            pop(s, str);
            if (*str == ch)
            {
                result = true;
                scanf("%c", &ch);
                continue;
            }
            else
                return false;
        }
        scanf("%c", &ch);
    }
    if (stack_length(s) > )
        result = false;
    stack_destory(s);
    return result;    
}


int main()
{
    int i = ;
    char input[] = {'0'};
    if(match(input) == true)
    {
        printf("比對成功\n");
    }
    else
        printf("比對失敗\n");
    printf("輸入的字元串為:\n");
    for (i = ; i < ; i ++)
    {
        if(input[i])
        {
            printf("%c", input[i]);
        }
    }
    printf("\n");
    return ;
}